Home > 12月, 2007

2007.12.16

libLBFGS 1.3 released

libLBFGSは,いつの間にかバージョンが 1.3 になりました.今道様よりご指摘いただいた,サンプルプログラムのバグ修正がメインです.これに伴い,lbfgs関数の引数が1つ追加されました.また,Microsoft Visual Studio 2005 や GCC でビルドするためのファイル,README も追加しておきました.

2007.12.03

サイトのデザインを更新

トップページ以下のデザインを変更しました.発表文献を自動生成するシステムが壊れていたせいで,なかなかページの更新ができませんでしたが,ようやくシステムを修正したので,サイトの情報も最新のものに更新しました.発表文献のページは,bibtexからhtmlに変換するソフトウェア (bibtex2html) を使って自動生成させていたのですが,日本語がうまく取り扱えないので,bibtex -> Bibtex XML -> DockBook XML -> HTML という経路で自動生成するようにしました.これから忙しい時期になってきますが,また暇をみてコンテンツを充実させたいところです.

libLBFGS 1.1 released

ベクトル x に対し,スカラーを返す凸関数 f(x) とその偏微分が与えられるときに, f(x) の値を最小にするような x を求める強力な手法として,準ニュートン法の一種であるL-BFGS 法が有名です.自然言語処理の分野では,L-BFGSは最大エントロピー法 (Maximum Entropy) や条件付き確率場 (CRF) など,log-linearモデルのパラメータを効率的に求めるための常套手段となっています.log-linearモデルは,目的関数 f(x) として確率モデルにおける学習データの対数尤度(の符号を反転したもの),偏微分として各素性の学習モデルにおける出現頻度と確率モデルにおける出現頻度(期待値)の差とおいて,パラメータ(素性の重み)をL-BFGS 法で簡単に導出します.「L-」が付かないBFGS法の詳細については,こちらが分かりやすいです.L-BFGSは,BFGS法の肝であるヘッセ行列の逆行列の反復計算による推定を,過去 (m+1) 回以前のことはきっぱりと忘れ,過去 m 回以内の計算結果だけから推定するという,粋な手法です.

L-BFGS法のC/C++言語の実装には,

などがありますが,基本的にJ. Nocedal氏のオリジナルの実装をCに移植したものがほとんどです.元々がFortranのため,関数インタフェース,変数の使い回し(配列の要素が1から始まる),構文(gotoが多用される)など,C言語らしくないコードになっていることがあり,読みづらくメンテナンス性が低くなっています.

私が公開しているlibLBFGSは,J. Nocedal氏のFortranのコードに基づいていますが,元論文や参考文献を漁りつつ,自分の解釈を加えながら手作業でC言語に移植したため,読みやすいコードになっているはずです.その他,

  • コールバック・インタフェース採用
  • スレッドセーフ(関数内のstatic変数を駆除)
  • クロスプラットフォーム対応(MSVCとgccのどちらでもコンパイルできます)
  • floatとdoubleの型を#defineマクロで簡単に切り替え可能
  • SSE/SSE2による最適化

など,独自の改良も加えてあります.

一昨日リリースしたバージョン1.1では,G. Andrew氏らが提案したOrthant-wise L-BFGSを実装しました.Orthant-wise L-BFGSは,従来不可能だったL1正則化によるパラメータ推定をL-BFGSで可能にするというもので,岡野原氏の解説が分かりやすいです.L-BFGSから見たL1正則化は,目的関数として f(x) に (変数ベクトル x の1ノルム) × C を加えたものを最小化するという問題です.libLBFGS 1.1では,L1正則化の係数(C)を設定すると,自動的にOrthant-wise L-BFGSを有効にし, f(x) とその偏微分の値を自動的に修正します.

libLBFGSのサイトでは,サンプルプログラムやソースコードが掲載されています.配布ライセンスはMITライセンスですので,お気軽にお使いください.