本ソフトウェアは,最大エントロピーモデル (Maximum entropy model) [1] のパラメータ推定を行なうプログラムです. 事象(event)を学習データとし,学習データの尤度を最適化するパラメータを出 力します. 以下のような機能をサポートしています.
上記を満たすIAマシン,もしくは同等スペックのSparcマシンでの使用を推奨します. 入力データのサイズによっては,さらにメモリ・ハードディスクが必要となります. (基本的には,入力データに比例するサイズの記憶領域を必要とします)
g++ 3.2.3,g++ 4.0.3 で動作を確認しました.
以下のステップでコンパイルし,インストールします. (以下の例で,% はシェルのプロンプトを表します.)
% ./configureデフォルトでは /usr/local/ 以下に実行ファイルがインストールされま すが,他のディレクトリ($DIR とする)にインストールしたい時は,以下 のようにオプションを指定してください.
% ./configure --prefix=$DIRまた,--prefix 以外にも以下のオプションに対応しています.
オプション | デフォルト | 有効な値 | 効果 |
---|---|---|---|
--enable-debug | no | 0 〜 5 または no | デバッグメッセージを表示する/しないを設定します.数が大き いほどたくさんのメッセージを表示します. |
--enable-profile | no | 0 〜 5 または no | プロファイル(各関数の実行時間の測定)をする/しないを設定し ます.数が大きいほどたくさんの関数のプロファイルをとります. |
% makeコンパイルが終了すると ./src/ ディレクトリに amis という実行ファイル が作成されます.
% make install
以上により,/usr/local/bin/amis がインストールされます.
Amis を起動するには,設定ファイル(後述)を引 数として,amis を実行します.
% amis [設定ファイル]引数を省略すると,デフォルトでは amis.conf を設定ファイルとして読み込み ます.amis.conf が読み込めないときは,エラーとなり 終了します. 起動時にオプションを指定することもできます.
設定ファイルには,設定項目の名前とその値の組を記述します.具体的には, 以下のようになります.
DATA_FORMAT Amis FEATURE_TYPE integer MODEL_FILE example.model EVENT_FILE example.event OUTPUT_FILE example.output LOG_FILE example.log ESTIMATION_ALGORITHM BFGS NUM_ITERATIONS 1000 REPORT_INTERVAL 1 PRECISION 6
オプションを指定する場合は、
% amis -e foo.event -a BFGSMAP [設定ファイル]のようになります.
各設定は,以下の優先順位で有効になります.
指定できるオプションは以下の通りです.この他のオプションは,"--help" で 詳しい説明が表示されますが,正しく動かない機能もあるので注意してください.
設定項目 | 実行時オプション | デフォルト値 | 有効な値 | 効果 |
---|---|---|---|---|
BC_LOWER | --bc-lower | 1.0 | 0以上の実数 | BLMVMBC,BLMVMBCMAPで使われる,不等式制約の下限. 論文[8]のBが,この値の逆数に設定される. (0に近いほど,結果は一様分布に近づく) |
BC_UPPER | --bc-upper | 1.0 | 0以上の実数 | BLMVMBC,BLMVMBCMAPで使われる,不等式制約の上限. 論文[8]のAが,この値の逆数に設定される. (0に近いほど,結果は一様分布に近づく) |
DATA_FORMAT | --data-format,-d | Amis | Amis,AmisTree,AmisFix | データファイルの形式 |
ESTIMATION_ALGORITHM | --estimation-algorithm,-a | GIS | GIS,GISMAP,BFGS,BFGSMAP,BLMVMBC,BLMVMBCMAP | 推定アルゴリズム |
EVENT_FILE [1] [2] ... [n] | --event-file,-e | amis.event | ファイル名のリスト | 入力イベントファイルのリスト.「-」を指定すると,対応する番号に標準入力をとる. オプションの場合は複数指定しても良い |
EVENT_FILE_COMPRESSION | --event-file-compression | raw,gz,bz2 | 入力イベントファイルの圧縮 | |
EVENT_ON_FILE | --event-on-file | false | 真偽値 | 計算の際イベントをファイル上に保持する(イベントがメモリに乗り切らないときに使用) |
EVENT_ON_FILE_NAME | --event-on-file-name | amis.event.tmp | ファイル名 | EVENT_ON_FILEで使われるファイル名 |
FEATURE_TYPE | --feature-type,-f | binary | binary,integer,real | 素性関数の値のタイプ.動作速度に影響する. |
FEATURE_WEIGHT_TYPE | --feature-weight-type,-w | alpha | lambda,alpha | モデルファイル,参照確率ファイルの入出力の際の素性の重みのタイプ. |
FILTER_INACTIVE_FEATURES | --filter-inactive-features | false | 真偽値 | PRECISIONの範囲で無視しうる素性を出力しない |
FIXMAP_FILE [1] [2] ... [n] | --fixmap-file,-x | amis.fixmap | ファイル名のリスト | AmisFix形式の,イベントファイルの書式設定ファイルのリスト.「-」を指定すると,対応する番号に標準入力をとる. オプションの場合は複数指定しても良い |
FIXMAP_FILE_COMPRESSION | --fixmap-file-compression | raw,gz,bz2 | FIXMAP_FILEの圧縮 | |
LOG_FILE | --log-file,-l | amis.log | ファイル名 | 推定の経過の出力先 |
MAP_SIGMA | --map-sigma,-s | 1 | 実数 | GISMAP,BFGSMAP,BLMVMBCMAPで使われる,事前分布の標準偏差 (0に近いほど,結果は一様分布に近づく) |
MEMORY_SIZE | --memory-size | 5 | 整数 | BFGS,BLMVMにおける,使用メモリ量. |
MODEL_FILE [1] [2] ... [n] | --model-file,-m | amis.model | ファイル名のリスト | 入力モデルファイルのリスト.「-」を指定すると,対応する番号に標準入力をとる. オプションの場合は複数指定しても良い |
MODEL_FILE_COMPRESSION | --model-file-compression | raw,gz,bz2 | 入力モデルファイルの圧縮 | |
NUM_ITERATIONS | --num-iterations,-i | 200 | 整数 | 推定アルゴリズムの反復回数 |
OUTPUT_FILE | --output-file,-o | amis.output | ファイル名 | 出力モデルファイルのファイル名 |
OUTPUT_FILE_COMPRESSION | --output-file-compression | raw,gz,bz2 | 出力モデルファイルの圧縮 | |
PARAMETER_TYPE | --parameter-type | alpha | alpha,lambda | 内部で計算に使うパラメタのタイプ.alphaだと高速に,lambdaだと頑健に動作する |
PRECISION | --precision,-p | 6 | 整数 | 推定結果の有効桁数 |
REFERENCE_DISTRIBUTION | --reference | false | 真偽値 | 参照分布の使用 |
REFERENCE_FILE [1] [2] ... [n] | --reference-file | amis.ref | ファイル名のリスト | 参照分布のファイル名 |
REPORT_INTERVAL | --report-interval,-r | 1 | 整数 | 推定経過の出力の間隔 |
amis を利用するには,上で述べた設定ファイルの他に, モデルファイル, イベントファイル を用意する必要があります.それぞれについて以下で説明します.
各ファイルにおいて,# から行末まではコメントとして無視されます.コメント はスペースと同等の扱いとなります.各トークンはスペースまたはタブで区切 られ,改行文字が行の終りを表します.また,コロン(:)は特別な文字として 認識されます.これらの特別な文字をトークンの一部として使いたい時は,バッ クスラッシュ(\)でエスケープしてください.バックスラッシュ自身は \\ で 表します.
モデルファイルは,素性関数の名前と,それに対応する重みの初期値を与えるファイルです.
素性名 初期値 素性名 初期値 素性名 初期値 ...
一行が一素性に対応し,各行には素性名と素性の重みの初期値を,スペースまたはタブで区切って記述します. 素性名には,スペース,タブ,コロン(:),シャープ(#)以外の文字ならなんでも使えます. 初期値は C スタイルの実数で記述します. 初期値は正の実数(FEATURE_WEIGHT_TYPEがlambdaなら任意の実数) ならいくつでも構いませんが, 普通は 1.0 (FEATURE_WEIGHT_TYPEがlambdaなら0.0)にします.
イベントファイルでは,学習データとなる事象のリストを与えます. 最大エントロピー法における事象は,観測事象(observed event)と補完事象(complement event)からなります. 補完事象には,観測事象以外の,想定される選択肢を列挙します. 各々の事象は,観測事象と補完事象の和集合のなかから,観測事象を選びとることと見なすことが出来ます. 実際には,観測事象,補完事象ともに,そこで観測された素性を列挙することによって記述します.
イベントファイルの形式は,Amis形式,AmisFix形式,およびAmisTree形式から選ぶことが出来ます. AmisFix形式は一定数のラベル集合から,分類対象に付与するラベルを選ぶ問題に使います. AmisTree形式は feature forest に対するパラメータ推定アルゴリズムを利用する時に使います. Amis形式とAmisTree形式は,理論的には同等の表現力を持ちますが, feature forestがコンパクトに記述できるような問題では, 速度,メモリともにAmisTree形式のほうが大幅に高効率となります. AmisFix形式は,表現力が制限されますが,単純な分類問題ではAmis形式に比べて消費メモリが少なくなります. ただし,速度はAmis形式のほうが速くなる可能性があります.
event_1 1 素性 素性 素性 ... 0 素性 素性 素性 ... 0 素性 素性 素性 ... 0 素性 素性 素性 ... ... event_2 0 素性 素性 素性 ... 1 素性 素性 素性 ... 0 素性 素性 素性 ... ... ...ただし,「素性」の部分には,
素性名を書きます. FEATURE_TYPEでintegerやrealを指定した場合は
素性名:素性の値を書くこともできます.
空行で分けられたブロックが一つの事象に対応します.一行目には,事象の名 前を記述します.事象名には,上述した特殊文字以外の任意の文字が使えます. 事象名は,推定には影響を与えないので,意味のない文字列でも構いません. 次の行からは,各行に観測事象または補完事象を記述します.行の先頭には, その事象の観測回数を記述します.観測事象の場合は正の数,補完事象の場合 は0になります.一つの事象につき観測事象は一つしか記述できません. 観測回数の後ろに,発火した素性を列挙します. 素性は,モデルファイルで記述したものを指定します.モデルファイルにない 素性を指定するとエラーになります.各素性の後ろには,素性関数の値を指定 することができます.上の例の通り,コロン(:)に続けて素性関数の値を指定 します.省略した場合は1とみなされます.
各事象は,空行で区切ります.空行は何行でも構いません.コメントのみの行 も空行とみなされるので注意して下さい.
まず,イベントファイルから素性を取り出すために, FIXMAP_FILEとして,次の形式のファイルを指定します.
ラベル名 ラベル名 ラベル名 ... 特徴名 ラベル名 素性名 ラベル名 素性名 ... 特徴名 ラベル名 素性名 ラベル名 素性名 ... 特徴名 ラベル名 素性名 ラベル名 素性名 ... ...
イベントファイルとしては,次の形式のものを与えます.
ラベル名 1 特徴 特徴 特徴 ... ラベル名 1 特徴 特徴 特徴 ... ラベル名 1 特徴 特徴 特徴 ... ...ただし,「特徴」の部分には,
特徴名または
特徴名:素性の値を書きます.
FIXMAPファイルの先頭の行では,分類に用いるラベルを列挙します. 先頭以外の行は,一行が一つの特徴に対応し, 各特徴がそれぞれのラベルと共起したときに発火する素性を指定します.
イベントファイルは,一行が一つの観測事象に対応します. 行頭には,観測されたラベルと,その事象の頻度を記述します. それに続けて,観測された特徴を列挙します. Amisは,行頭のラベルと,列挙された特徴を組み合わせて, FIXMAP_FILEの対応する素性からなる観測事象を作ります. 補完事象は,行頭に書いたもの以外のラベルを用いて,自動的に作られます.
事象名 頻度 素性 素性 素性 ... [disjunctive node][disjunctive node]は,BNF風に書くと以下のようになります.
[disjunctive node] := ノード名の参照 | { ノード名 [conjunctive node] [conjunctive node] ... } [disjunctive node] := ノード名の参照 | ( ノード名 素性 素性 ... [disjunctive node] [disjunctive node] ... )中かっこ及び小かっこの前後には必ずスペースを空けてください. スペースがない場合はノード名や素性名の一部とみなされます.
具体的には,以下のようになります.
event_1 2 feature1:2 feature2:3 feature3 { dnode_1 ( node_1 feature1:2 { dnode_2 ( node_2 feature2:3 ) ( node_3 ) } { dnode_3 $node_2 ( node_4 feature3 ) } ) } event_2 1 feature2:3 { dnode_1 ( node_1 feature1 ) ( node_2 { dnode_2 ( node_3 feature2:3 ) ( node_4 feature3 ) } ) } ...
Amis 形式と同様に,空行が事象の区切りを表します.AmisTree 形式では,一 つの事象を3行で記述します.1行目は,事象の名前を記述します.2行目に は,その事象の観測回数と,観測事象の素性を記述します.上の例では,事象 event_1 は2回,event_2 は1回観測されたことを表します.Amis 形式と同 様,素性の名前と素性関数の値を組で記述します.3行目には,観測事象およ び補完事象の feature forest を記述します.まず,disjunctive node は中 かっこで表します.中かっこの中に,はじめにノード名を記述し,次に conjunctive node をスペースで区切って並べます. ノード名は,イベント単位で一意になっている必要がありますが, 共有する必要のないノードに対しては,'_'にすることもできます. conjunctive node は,小 かっこまたはノード名で表します.小かっこで表すときは,最初にその conjunctive node の名前を記述します.conjunctive node の名前は,ノード の共有を表すために使います.素性と同様に,特殊文字以外の任意の文字が使 えます.その後にそのノードで発火する素性を記述します.素性の記述方法は Amis 形式などと同じです.その後に,disjunctive node を記述することもで きます.conjunctive node や disjunctive node の共有を表すときは,ノー ド名を用います.既出のノードについて,そのノード名の先頭に $ をつけた ものでノードの共有を表します.上の例では,event_1 において,$node2 は 前に出てきた node2 と共有していることを表します.このようにノードを共 有して feature forest のサイズを小さくすると,計算量が小さくなり,スピー ドアップします.
feature forestからは,次のような相互再帰的な手続きで,観測/補完事象の素性列を取り出すことができます.
amis は,素性とパラメータの組を、OUTPUT_FILEで指定したファイルに出力します.出力形式は, モデルファイルと同じです.出力形式がモデルファイ ルと同じなので,出力データを新たな入力として amis を使うこともできます. すなわち,ある程度学習したデータを元に,さらに学習を進めることができます.
各素性に対応するパラメータa_iが出力されるので, 未知のデータに対して発火する素性のa_iの積を求め ることで,その確率値を計算することができます.