対数線形モデルとエントロピー最大化の関係

昔の勉強ノートを引っ張りだしてくるシリーズ.

機械学習の対数線形モデルが最大エントロピー法とも呼ばれる,みたいな記述は頻繁に目にするし,統計力学のボルツマン分布の話とか考慮すれば,なんとなくそうなってそうな気はするけど,実際どうなの?というのを (たんに好奇心を満たすために) 調べてみた.実用上は何の意味ないと思う.

対数尤度関数に L1 正則化項を加えるタイプの目的関数を使った場合,もはやエントロピーは最大化されない,とかそういうわりとどうでもいいことがわかったりするかもしれない.

概要

「言語処理のための機械学習入門 (→ amazon) 」などに出てくるタイプの対数線形モデルの係数の最尤推定量が,エントロピーを「ある制約条件下」で最大化した場合のラグランジュ未定乗数に対応することを説明する (クロス表の対数線形モデルとはたぶん別物).

ただし,記号が煩雑になるのを避けるため,対数線形モデルとほぼ同一の構造を持ち,記号が煩雑でない条件付きロジットモデルがエントロピー最大化と等価であることを見る.

本文の最後に対数線形モデルと等価なエントロピー最大化問題を示す.多少ややこしくなるが,同じ方針で証明可能.
“対数線形モデルとエントロピー最大化の関係”の続きを読む

線形制約の矛盾判定アルゴリズム

最適化アルゴリズムを実装する際など、さまざまな場面で遭遇する、線形な制約式
\begin{align*}Ax\ge b\hspace{20pt} A \;:\; m\times n\text{ matrix}\end{align*}
を満たすベクトル x が存在するかどうかを判定する問題について考えてみます。

行列 A を正方行列として、連立一次方程式 Ax=b が一意解をもつか、という問題設定ならば行列 A がフルランクであるかどうかが問題になりますが、今考えている問題設定では A のランクは関係ありません(つまり行列がランク落ちしていても解が存在することもあるし、フルランクでも解が存在しないこともあります)。

実践的な方法として、線形計画法のソルバーが利用可能であるならば、
\begin{align*}\text{maximize}\hspace{10pt} \sum_i\; x_i\end{align*}
\begin{align*}\text{subject to}\hspace{10pt} Ax\ge b\end{align*}
という問題を解いてみて “Model is infeasible” な例外が出なければOKとする方法が簡単でしょう。

ここではもう一歩踏み込んで「システマティックに矛盾を検出するアルゴリズム」について考えてみます。

“線形制約の矛盾判定アルゴリズム”の続きを読む

lp_solve で set_presolve したときの目的関数のリセット

以前、lp_solve で set_presolve したときの解の取得というエントリーを書きました。set_presolve は LP を解くための前処理の設定です。これが設定されると solve 関数の実行の際にいくつかの変数が配列から消去されてしまうため、インデックスの対応関係が崩れてしまいます。
前回のエントリーでは solve をした後に、インデックスの対応関係の崩れた lprec オブジェクトからどのように解を取り出せばよいのかについてでした。

今回のエントリーは「lprec オブジェクトのリサイクル」についてです。どういう状況を想定しているかというと、一度 solve が実行された lprec オブジェクトに対して

  • 制約条件はそのままで
  • 目的関数のみを変更する

という、一見すこしマニアックな設定です(実はこの状況は線形制約のシンプルな凸最適化アルゴリズムである、Frank-Wolfe 法を適用する場合に出現します)。

lp_solve ライブラリには set_obj_fn という関数がありますが、前述の理由でこの関数は一度 solve が実行された lprec オブジェクトに対しては使用することができません。

“lp_solve で set_presolve したときの目的関数のリセット”の続きを読む

lp_solve で set_presolve したときの解の取得

lp_solve は C/C++ から使える高性能の線形計画(LP)ソルバーだ。添え字の設定などに多少癖はあるが、中規模程度の問題ならほとんど問題なく利用できるし、なによりフリーなのがうれしい。

この lp_solve には、あらかじめ自明な解や一次従属な制約条件を取り除いてくれるset_presolve という前処理のための関数がある。前処理を行うかどうかは任意(デフォルトではしない)が、することを選択した場合は注意が必要だ。

解は get_variables という関数で取得できるが、前処理されて消去された変数はアルゴリズムの実行時には効率を優先するためにメモリから消されてしまうため、そのままではオリジナルの問題の変数の添え字に正しく対応する値を返してくれない。

“lp_solve で set_presolve したときの解の取得”の続きを読む