確率的コンプレキシティと学習理論
山西 健司
l……ll…州…川…‖＝‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖＝‖‖‖‖‖＝‖‖‖‖‖‖＝＝‖＝‖＝‖‖‖州‖‖‖‖‖州l川l川l…l……l…l州Il……………‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖＝‖‖‖‖州…州…州l………11州

2．確率的コンプレキシティ

1． はじめに
本稿では、次の2つの統計的推論の問題を扱う。
1．確率モデルの最適選択、が統計学における「確率分布」と見方の違った同一の

2．逐次的確率予測。

概念であることを示し、この関係に基づいて確率的コ

前者は、データが与えられたとき、これを発生させている確率分布として最もふさわしいモデルを選択す

ンプレキシティを導入する。
（情報源）符号化とはデータ系列を2進系列に変換する問題である。後者は、データが逐次的に与えられるることである。データ系列Y＝れ…㌦は有限アル

とき、オンラインで未来のデータの確率分布を予測す

ファベットJの直積空間Amの元であるとし、（0，1）＊

るという問題である。これらの問題は、統計的推論のを有限長の2進列の集合として、符号化を表す写像を基本問題であると同時に、近年発展している確率的規￠‥』m→（0，1）＊で表す。￠は1対1写像とする。

則の計算論的学習理論【6＝12】，【16＝101といった分野のさらに￠としては、符号語の系列￠（Ⅹ）￠（Y）￠（Z）…

中心的話題である。本稿では、「学習」という言葉はからⅩ，Y，Z，…に対応する符号語をコンマなどの特上の2つの統計的推論の問題を意味するものとする。

別な区切り記号などを用いなくとも、正確にその順

1では、未知のデータ発生分布に出来るだけ近いモ●

本節では∵、情報理論における「符号化」という概念に分離して復号化できるような符号化を考える。この

デルを少ないデータ数で選択するためのアルゴリズ

ような性質をもつためには「任意の2つのデータ系列

ムが必要になる。また、2では予測誤差の累積が出来

Ⅹ，Y∈Jmに対して、符号語￠（Ⅹ）と￠（Y）の一方がるだけ小さくなるようなアルゴリズムが必要となる。

他の先頭部分に一致することはない」という条件をみこのようなアルゴリズムはどのようにして設計でき

たすことが十分である【3】。この条件をみたす符号化るのか？本箱は「確率的コンプレキシティ」という概を語頭符号化とよぶ。我々は符号化のコストを符号語

念を軸にして、上の間に対する統一的な解答指針が与の長さ一「符号長」−で測り、符号長が出来るだけ短くえられることを示すものである。

なるような語頭符号化を設計したい。

確率的コンプレキシティはJ．Rissanenによって提実は、語頭符号化の条件と符号長とは密接に結び付唱された新しい情報量概念であり、大雑把に言って、いている。実際、￠が語頭符号化であるための必要十データ系列を与えられた確率モデルのクラスを用い

分条件は、各Yに対する符号長をJ（Y）として、次式て符号化する際の最短符号長として定義される。実は（Ⅹraftの不等式）をみたすことである【3】。

上の2つの問題に有効なアルゴリズムの設計は、確率的コンプレキシティを最良に近似するための符号化を∑2−げ）≦1・
Y∈」▼▼l

設計することに帰着されるのである。以下、確率的コ
ンプレキティの概念が最適な学習アルゴリズムの設計と解析に本質的な役割を果たす事情を、近年の情報理論と学習理論の結果をふまえて解説する。

一方、各Y ∈ 月mに対してQ（Y）≧ 0かつ∑Y∈AmQ（Y）≦1を満たすQ（Y）をAm上の劣確率分布とよぶ。語頭符号￠が1つ与えられたら、その符号長〜（Y）に対して、

やまにし けんじ NECC＆C研究所〒216川崎市宮前区宮崎4−1−1

J（Y）＝−log（フ（Y）（1）

によって劣確率分布Q（Y）が定義できる（logは底が2の対数を表すものとする）。逆に劣確率分布Q（Y）が1996年7 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（19）3丁91つ与えられると、上の関係によってJ（Y）を符号長関数とする語頭符号化が存在する（例えば、Shannon−
Fano−Elias符号【3］）。以下、このような符号化を分布Qに対する符号化と呼び、（1）をYのQに対する
Shannon情報量とよぶ（本稿では、簡単のため、符号長は非整数値をとることを許すものとする）。このように、（劣）確率分布と語頭符号化は表裏一体の関係にある。

これを具体的な符号化を例に見て行こう。

3．非逐次的符号化とモデル選択
3．1 2段階符号化
本節では、データ系列ym．＝れ‥」㍍が一括与えられた時にこれを符号化する方法（これを非逐次的符号化とよぶ）及び、これによる確率的コンプレキシテ

ィの近似について考える。先ず、乃を用いてymを以では、符号長を出来るだけ短くするにはどのような確率分布に対して符号化すればよいのか？データを発生させる確率分布P＊（これを真の分布とよぶ）がわかっていれば、P＊に対する符号化は平均の意味で最小の符号長をもつことが容易に確かめられる【3】。ところが現実には真の分布P＊は未知である場合が多い。その場合、平均符号長を出来るだけ短くするように符号化するにはどうしたらよいか？1つの解決策は、たった1つの（劣）確率分布の代わりに、真の分布を含むと思われる（含まなくても良い）確率モデルのクラスを1つ導入し、これに対して符号化することである。
ここでいう確率モデルとは、何らかの数学的制約の入下の2つのステップを踏んで語頭符号化することを考える。（1）γの中から確率モデルを1つ選択し、（2）これを用いて確率モデルと一緒にデータの符号化を行う。このような符号化を2段階符号化（Two−part
Coding）【9］とよぶ。2段階符号化に必要な全符号長
は「選ばれた確率モデルに対するデータの符号長」と「その確率モデル自身の符号長」の紀和として計算できる。選ばれた確率モデルをPとすると、これに対するデータの符号長は−logf）（ym）で求められる。P自身の記述長はⅨraftの不等式を満たす符号長関数ゼを1つ固定してゼ（P）で計算する。よって、全符号長は−logf）（ym）＋ゼ（P）

った確率分布のことを指す。

ところで、「 クラス に対してデータ系列を符号化する」とはどういうことか？そのクラスの中から最適な確率モデルを1つ選んでそれに対して符号化するという方法もあるだろうし、クラスに属するモデル全（2）として計算できる。そこで、（2）をγ上のPに関して最小化して得られる量は、2段階符号化による確率的コンプレキシティ5C（ym：γ）の近似と見なすことが出来る：

体を重み付き平均して符号化するという方法もある∬（ym：叫た−logP（ym）＋岬））・だろう。実に様々な符号化が考えられるのである。

今、γを確率モデルのクラスとし、与えられたデー

ここで左辺の量のminimumを達成するようなPは、

タ系列ym＝れ…｝㍍のナ‖こ対する確率的コンプレ「与えられたデータ系列ymを、2段階符号化によってキシティ（Stochastic Complexity）［11】を「Ymをク

最も短く符号化出来るような確率モデル」である。こラチγに対して語頭符号化するときの最小符号長」のようなモデルこそがデータ生成源の最良のモデルとして定義し、gC（ym：γ）とかく。ここで、最小はであると見なす、確率モデル選択基準をMDL（Min−γに対するあらゆる符号化に関してとるものとする。

imum Description Length）原理【8】，［9］とよぶ。

Shannon情報量（1）は1つの分布に対する符号長でMDL原理では、（2）の量の大小を確率モデルの評価あったから、SC（Ym：7i）はShannon情報量の一般化

値とし、この値が小さい程、データ発生源をうまく表と見なすことが出来る。（注意：3．2節の最後により数現していると見なす。以上のように、2段階符号化に学的に正確なぶC（ym：γ）の定義を与える。）

よる確率的コンプレキシティの最良近似を考えること

5C（ym：γ）の正確な値は、通常簡単に計算できるとは限らない。そこで実際は特定の符号化を選んで∫C（ym‥γ）を近似的に評価することになる。符号化の多様性に対応して、確率的コンプレキシティの近似により、最適モデル選択の戦略が得られる。

3．2 最尤符号化
2段階符号化において、もし告が有限のクラスなら方法は幾通りも考えられる。どの符号化を選ぶかはまば、（2）の左辺の計算は特に問題はない。ところが、告さに、統計的推論の状況に依存するのである。以下、が連続の実数億パラメータで指定されている場合はそれは自明に計算できない。なぜならば、通常、実数
380（20）オペレーションズ・リサーチ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

●

値パラメータの指定には無限の精度を要求されるのしてタイトなものなのであろうか？結論から先に言で、まと＿もに計算すればその符号長が無限大になって

えばYesである。実際に以下の不等式が成立する。

しまうからである。この間題を克服する1つの方法として、パラメー定理2／9ル（ym）を任意の語頭符号化の符号長関数とタ空間の量子化に基づく2段階符号化する。データymが確率分布昂，た∈γ（机こ従って発生の方法が考えられる【叶【19】0しか〔ここでは、確率的するとき、定理Jと同じ条件のもとで、すべてのど＞0

コンプレキシティを近似する非逐次的符号化として、

に対し、漸近的に測度が0となる実数値パラメータの最尤符号化とよばれる、より単純な符号化方法を紹介

集合を除いた全てのβについて次式が成立する。

する。

今、γ（た）＝（昂，た（ym）：β ∈ 0 ⊂ Rりとか且針た【エ（ym）】≧ガγ丁−（昂，た）＋（喜」logm・（5）けるた次元パラメトリックな確率モデルのクラスを考える。ここで、0はた次元の実数値パラメータ空間で

ここで、ガm（恥）竺」恥トlogj㌔，ん（ym）】はある。データ系列ymが与えられたとして、最初に思昂，た（l′m）に関するエントロピーを表す。

い付くパラメータの推定量は最尤推定量である。こ

ここで、ガm（恥）恕昂棋トlogfち，た（ym）】＋準でれは、尤鹿角，た（ym）を最大にする推定量として定義あることが知られているから、（4）と（5）を比較する

される0∂をymからの最尤推定量として、昂，た（ym）≒、叩′m：¶（ん））は真の分布に関する平均の意味でに対してymを符号化すれば確率的コンプレキシティ（5）の下界を0（log川ノ）の誤差以内で達成していることが得られそうだと簡単に思えるかも知れない。とこがわかる。ここに、1imm→∞0（logm）／logm＝0であろが、巧，たは確率分布をなさないという点に注意しる。よって、真の分布が宮（た）の中に含まれている状況

なければならか−0実際、各々の帯，たはymに依存

では、（4）の右辺の値は確率的コンプレキシティを平するので、∑ym。Am fも、た（ym）＞1となる場合が存均として叫og7乃）以内の精度でタイトに近似してい在する。そこで、正規化して得られるym の関数、るといえる。さらに注目すべきことに、（4）の右辺のち，た（i′m）／∑l′mfち，た（ym）はymに関する確率分布を第3項に関しては、実は、ペイズリスクのミニマック

なすことに注目すると、この分布に対する†′mの符ス戦略の立場からその最適性が証明されている【2］。

号化が定義できる。これを最尤符号化（Maximum

以上、近似や）がタイトであることを見た。以下、LikelihoodCoding）【4‖11】とよぶ。さらには、その連続なパラメータのみで指定されたモデルクラスに符号長で確率コンプレキシティを近似することが出来

対しては、（4）で計算できる叩′m‥γ（た））の催そのる。すなわち、
5C（ym‥γ（た））た−log

ものを、ymの乃（叫こ対する確率的コ㌢プレキシティ
巧，た（ym）∑Y′mfち，た（y り）・（3）の定義として議論を進めて行こう。

3．3 確率モデルの最適選択（3）の右辺の量を∫（ym：乃雄））とかくことにする。

この値に関しては次が知られている。

これまではパラメータの次数たを固定してきたが、如こ関して入れ子構造をもつクラスの系列：

定理1／〃ノβのほとんどいたるところで最尤推定量
に関して中心極限定理が成立するものと仮定する。こγ（1）⊂告（2）⊂・‥⊂宮（た）⊂γ（頼1）⊂…γ（β）のとき次式が漸近的に成り立つ。
J（ym：乃（た））（4）＝−log射ym）・…log芸＋log／挿両dβ＋0（1）・

ここに、叩）＝恥【∂2怒㌢】はβにおけるダ吏5んeγを考えて、その和集合をγ＝∪たγ（た）としよう。たに関する事前分布を汀（た）として、データ系列ymの佃こ対する確率的コンプレキシティ5C（ym：乃）を2段階符号化で近似すると次のようになる。

情報量行列とよばれる量であり笹∂，たは昂，た（ym）に関する平均を表すノ、け（∂）lはその行列式を表す。0（1）は∬（｝rm‥明記聖n（招′m：γ（た））−log打（硯・1imm→∞0（1）＝0となる量である。
もっとも、たに関して特に事前知識がなければ、汀（た）このように、最尤符号化の符号長が評価されたのだ

が、これによる確率コンプレキシティの近似（3）は果1996年7 月号

を一様分布に設定することにより−log打（た）の項を無視して、単純にJ（i′m‥乃（た））のたに関する最小化の問© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（21）381

題として捉えることが出来る。その際の上式の右辺のここで0（1）の鱒は無視した0よって、与えられたデー

最小化は以下に帰着できる。

タに対して最良のヒストグラムの分割数を推定するには上式の値を最小にするたを求めれば良い。（注：上聖n（−logPh（Ym）＋…log芸＋log

式にて、データの符号長を（−log（密度関数の尤度））と（6）

形式的に計算しているが、これは負の億をとる。〝が∂はymからの最尤推定値である。たはモデルクラスの連続の場合は、本来はズを離散化して、その上の確率

複雑さを表す一種の指標であるが、真の分布を記述す

分布に対して符号長を計算しなければならないのだ

る最小のたカゞ未知であるとして、ここでMDL原理をが、上記のような形式的展開も許される。）

適用すると、（6）の右辺の最小を達成するようなたが

3．5 具体例その2：確率的規則の一括学習

最適なモデルのパラメータ次元ということになる。これがパラメータ哀数選択におけるMDも基準t8】，t9】と〝⊂Rn，y＝iO，1）とする。今、入力変数ズ∈〝と呼ばれるものである。MDL基準はしばしばBayes理

出力変数y∈ツの組β＝（ズ，i′）が独立に未知の真の論の立場から解釈されているが、最尤符号化からの導分布P（ズ，y）＝Q（芳）P＊（y】ズ）に従って生成されてい出において事前分布などのBayes的な仮定を一切おいるとする。宮を条件付確率モデルのクラスとし、デーていないことに注意しよう。

タ系列βm＝β1…刀m（仇＝（ズi，℃））が一括与えら

今、（6）の馴、億を達成するたを￡としよう。もし、真れたとして、省からP＊（ylズ）に出来るだけ近い確率の分布ア＊のパラメータの次数がた＊であるとしたら、モデルを1つ選び出す問題を一括学習の問題とよぶ。

（6）と定理2から、漸近的には左はた＊に確率収束するこ

いま、ズを有限個の排反する領域（Ci‥i＝1，…，た）とを示すことができる。この性質を一致性とよぶ。確に分け、〝＝∪た1Ci（CinCl＝￠，盲≠J）とし、ズが率モデル選択基準の 良さ はいろいろな尺度で評価

領域C−iに入ったら確率釣でy＝1を、確率1一針でされ得るが，MDL基準の良さの1つは一致性にある。

y＝0を出力するような確率モデルを考える。このよ

3．4 具体例その1：ヒストグラムの推定

うな確率モデルを有限分割型の確率規則【121とよぶ。
た個の有限分割で指定される有限分割型の確率規則の定義域をズ＝【0，1】として、〝上のた＋1分割のヒス

クラスをγ誓主とかく。データ系列かmが与えられたとき、γ畏のモデルについて、ズがよ番目の領域に属す

トグラム密度とは、∬をた＋1等分して、それぞれのセルをq（よ＝1，…，た＋1）として、Ciに入ったデータズに対する確率密度を（た＋1）βiで定めるような確率密るデータの数をmいそのうちy＝0，1であるデータの数をmil，m五0（mil＋肌用＝〝㍉）とすると、尤度は度関数である（0≦β壷≦1，∑誓Jβ壷＝1）。た＋1分割のヒストグラム密度全体のクラスをγ慧i5とかく。デー

nた1∂「il（ト帰miOとかけるので、∂ の最尤推定値は∂i＝mil／miと計算される。また、Fisher情報行列のタ系列yrn＝れ…i㌦が与えられたとして、そのう

行列式はt叩）l＝1／口た1叛1一瑚で与えられるか

ちf番目のセルに入ったデータの数を†乃立とするとき

ら、logJ √F弼†dβ＝log（v斤／r（1／2））た＝0と計算さ（m＝∑崇m ）、尤度はれる。よって、MDL基準では札叩＝∪謹製の中でた＋1

口（（た＋瑚）mi
i＝1

た −∑∑

m力log＋logと計算できるから、βiの最尤推定量は∂古＝mi／↑乃であることがわかる。ただし、0logO＝0とする。まを最小にするP（ylズ）が最適モデルとして選ばれる。

た、このときのFisher情報行列の行列式はII（0）l＝

一括学習の性能の良さを測る学習基準として、確率的PAC（ProbablyApproximatelyCorrect）学習

1／n誓さβ と与えられるから、Jノ同村dβは基準【12】というものが知られている。これは、真の分／軒′2dβ＝蒜布P＊（ylズ）とアルゴリズムが推定する分布♪（y】ズ）の距離を d（P＊，♪）として、0＜ど，∂＜1が与えられたもとで、1−∂以上の確率でd（P＊，♪）＜どとなるののように計算できる。ここに、rはガンマ関数を表す。
結局、（4）の∫（ym‥γ（た））は以下のように計算できる。
頼1

灯り2に必要最小のデータ数で（これをサンプルコンプレキ−∑叫log慧−mlog（頼）＋喜log芸・＋log市河

シティとよぶ）アルゴリズムを評価するものである。

l＝＝1

（7）

に1ブ＝0，1

オペレーションズ・リサーチ

382（22）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

このサンプルコンプレキシティはアルゴリズムの一種

れ，鴇，・‥，‡㌦の順で与えられたとして、混合符号化の収束速度の指標であり、1／ど」／∂のオーダーとしてした場合のymの符号長は小さければ小さいほど良い。
（7）を最小にするモデルを出力するようなアルゴリ

墓（−log帥））＝−log／帆（ym）叫0）

ズムのサンプルコンプレキシティは、もし、あるたりこと計算できる。もし、確率モデルのクラスを乃（た）の代対して真の分布P＊がγ（た●）に含まれている場合には、

0（筈log筈＋竿＋喜

わりにγ＝∪たγ（た）とすれば、ymに対するγの混合
（8）

log吉）

符号化も、もう一段高いパラメーで与えられることが知られている 【12】。

考慮することにより同様に定義できる。

ここに舛ア＊，♪）＝Jd方Q（ズ）∑y＝。，1（P＊（yl弟1／2−

4．2 予測的符号化j）（YIX）1／2）2はHe11ingerの距離であり（QはX上の分タたに関する階層を

もう1つの代表的な逐次的符号化方法として予測

布を表す）、ゼ（P＊）はP＊の有限分割の記述に必要な符的符号化（PredictiveCoding）【9］を紹介しよう。こ号長である。（8）の値は1／ど，1／∂，㍍の関数として最小

れは、確率モデルのクラスγ（た）が与えられたとして、であることも知られており、MDL基準の一括学習に逐次的にパラメータβを過去のデータから推定しながおけるサンプルコンプレキシティの意味での最適性をら符号化する方法である。具体的には次のような符号保証している。ただし、真の分布P＊がどのγ（たりこも化を行う。f番目のデータ坑を確率分布含まれない場合の最適性は必ずしも保証されない。

烏（y）＝範士＿1，た（y）

4．逐次的符号化と確率的予測（11）に対して符号化する。ここで♂f＿1はパラメータ♂の過4．1 混合符号化

去のデータ系列yト1＝ れ…名＿1からの推定値（
例えば、最尤推定値）である。データ系列がym ＝

3節ではデータ系列が一括与えられたもとで確率的コンプレキシティを近似する符号化を考えてきた。

れ…i㌦の順で与えられたとして、予測的符号化によところが、データ系列が1つ1つ逐次的に与えられって符号化した場合のymのγ（た）に対する符号長は、て、オンラインで符号化しなければならない状況と

nl−∑logfも亡＿1，た（名）いうのも考えられる。本節では、このよう別犬況下での、与えられた確率モデルのクラスに対するデータ系と計算される。この量はしばしば、（ymのγ（叫こ対す列の符号化（これを逐次的符号化とよぶ）による確率

る）予測的確率的コンプレキシティ【9】と呼ばれる。

的コンプレキシティの近似について考えてゆこう。

混合符号化と予測的符号化といった逐次的符号化に先ず最初に混合符号化（Mixture Coding）ある

要する総符号長（10）と（12）は、いずれもymの乃（たりこいはBayes符号化【1】，【7】とよばれる逐次的符号化

対する確率的コンプレキシティの近似と考えてよい。

を紹介しよう。これは、確率モデルのクラスγ（た）＝

実際、予測符号化において∂ト1をyト1からの最尤推（昂，た（y）‥β∈0⊂Rりが与えられたとして、この定量とし、真の分布P＊が宮（叫こ属すると仮定して、クラスの要素全ての重みつき平均として定義される

P＊＝昂・，たとすると、（12）のP＊に関する平均は漸近確率分布に対して符号化する方法で、しかもその重み的に以下で与えられることが知られている【16】。

の値が逐次的に変化していくというものである。具体的には、f番目のデータ名を確率分布
昂（y）＝

／

（12）

t＝1

瑚恥）＋log汀い・c（logm）・

可叩′ト1）為，た（y）dβ

（9）

（13）

混合符号化についても、データが独立でパラメータに対して符号化する。ここで重みひ（呵yt−1）は過去の空間がcompact−SuPpOrtedである場合には、真の分布

データ系列yト1＝れ‥・名＿1からBayesの事後確率

P＊＝昂・，たが乃（叫こ属するならば、（10）のP＊に関すひ（叫yt￣1）＝

打（♂）昂，た（yt￣1）
J打（β）昂，た（yト1）dβとして計算するものとする。ここで汀（β）は予め与えられた事前分布である。データ系列が ym
1996年7月号

る平均は以下で与えられることが知られている【1】。

人・仁‥川．仁ガ■昂・，たけ盲log＋log

仰＋0（1）．（14）汀（〃●）

ここに、針は真の分布を指定するパラメータである。

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（23）383（13），（14）と（4）を比べると、逐次的符号化である

ム（これをBayes予測アルゴリズムとよぶ）が考えら

予測的符号化、混合符号化に要する稔符号長は、非れる。また、予測的符号化に対応して、各時刻fで（11）逐次的符号化である最尤符号化に要するそれ（すなの分布を出力する予測アルゴリズム（これを最尤予測

わち、確率的コンプレキシティそのものの値）と、平アルゴリズムとよぶ）も考えられる。

均として0（logm）以内で漸近的に一致しているといもし、真の分布P＊がγ（た）に属するならば、（13）とう興味深い事実が浮かび上がる。さらに、混合符号（14）からわかるように、上の2つの予測アルゴリズ

化でパラメータの事前分布をJeffereysの事前分布

ムに対する平均累積予測誤差はいずれも‰（昂・，た）＋

打（β）＝

ァ

に設定すると（酬まFisherの情

喜logγ托に0（logm）以内の誤差で収まり、平均予測誤報行列）、混合符号化の平均総符号長は最尤符号化の差の下界式（5）と0（logm）の誤差範囲内で漸近的に一

それと0（1）の項まで一敦することがわかる。

敦することがわかる。この意味で上の2つのアルゴリ
ズムは最適であるといえる。このように、逐次的符号

4．3 逐次的確率的予測モデル化を用いた確率的コンプレキシティの近似を考えるこ

確率分布と符号化は表裏一体の関係であることか
ら、非逐次的符号化が符号化自体の意味を離れて、確とによって、最適な逐次的確率予測アルゴリズムが具体的に設計できるのである。

率モデルの最適選択や確率的規則の一括学習という問題に有効な戦略を与えていた。これと同様に、逐次的符号化は符号化の意味を離れても、逐次的確率的予測という学習問題【叶［16】に有効な戟略を提示する。

5．確率的コンプレキシティの発展以上見たように、確率的コンプレキシティは確率モ

逐次的確率的予測の問題とは以下のような問題でデル選択や逐次的確率予測の問題に対して有効な戟ある。データがれ，鴇，…と順番に与えられる状況の

略設計指針を与えている。しかしながら、現実的な学

もとで、f−1番目のデータまでの系列 yト1＝

習問題への適用において幾つか問題が残っている。

れ…名＿1が与えられた時点で、坑をもらう前に名が1．一般化確率的コンプレキシティ

従う確率分布を予測したいものとする。予測アルゴ問題の1つは、統計的決定理論の立場から見ると、確

リズムは、与えられた確率モデルのクラスγを用い率的コンプレキシティの定義において、モデルのクラて、yt￣1の関数として坑の分布を予測し（予測分布をスは確率モデルのクラスであり、損失関数は対数誤差

昂（y）とかく）、予測後正しい値吊を敢えてもらう。こを用いるといった制限が与えられていたことである。

のとき予測誤差を対数誤差

ところが、現実的な学習の間道を考えると、モデルのクラスが一般の実数億関数であり、損失関数も自乗誤−log昂（Ⅵ）

差や絶対誤差などを含む一般的な損失関数を考えなで測るものとする。これは実際に生起した弟に対しければならない状況が多い。そのような状況に対応して小さい確率を割り当てるような分布を予測した場て確率的コンプレキシティの概念を一般化して、より合には大きな値をとるような損失関数である。このプ

広範囲の学習問題に適用できるようなアルゴリズム

ロセスをfに関して逐次的に繰り返す。我々は任意のの設計と解析の理論を推し進めた研究も最近発展しデータ系列ymに対してその累積予測誤差ている【13］，【171。

nl

2．ランダム化による近似∑（−log薫（名））問題のもう1つは、確率的コンプレキシティの近似過

f＝1が出来るだけ小さくなるような予測アルゴリズムを程において、しばしば計算論的困難が伴うということ

琴計したい。ここで、各時刻での予測誤差は予測分布である。例えば、確率的モデルのクラスが有限である

昂（y）に対する名の符号長という解釈が出来るので、が指数的多数である場合や、隠れ変数を伴うモデルな

累積予測誤差最小の問題はまさしく逐次的符号化にどの複雑な連続パラメータ構造をもつ場合は、混合分よる符号長最小化の問題に他ならない。

布（9）を求める際、あるいは最尤符号化（3）で最尤推

そこで、確率モデルのクラス仲ん）＝（昂，た（y）：β∈定値を求める際に計算量が指数的になったり、あるい

0⊂Rた）が与えられたとして、混合符号化に対応しは解析的には計算不可能という事態に陥る。その場合て、各時刻fで（9）の分布を出力する予測アルゴリズに計算的困難を克服していく有望なアプローチの1
オペレーションズ・リサーチ

384（24）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

●

確率的

符号化の方法

統計推論／学習の問題

有効性の理由非逐次的 2段階符号化

確率モデルの一致性、サンプルコン

最尤符号化

最適選択

プレキシティの最小性

混合符号化

逐次的

累積予測誤差

予測符号化

確率的予測

の最小性

符号化

コンプレキシティ

逐次的
符号化

表1：符号化と統計推論／学習問題
つはマルコフチェイン モンテカルロ法などのランダ

ム化手法を用いることである。この手法に基づいて、計算量を考慮した具体的な確率的コンプレキシティの近似理論の研究が進んでいる【15】，【18】。

【2】B．S．ClarkeandA．R．Barron、 Jeffreyspriorisasymp−
toticallyleastfavorable11nderentropyrisk，

toappearinJ5−クエ【3］T・M・CoverandJ．A．Thomas， ElementsofInforma−tionTheory，Wiley−Interscience，1991．

【4lL・D・Davisson， Minimax noiseless universalcoding

6． ぁわりに

forMarkovsources，

本稿では、確率モデルのクラスに対するデータの最小符号長として確率的コンプレキシティを導入し、それを最良近似するための符号化の過程から、統計的推論や学習に有効な戦略が生まれることを見てきた。
確率的コンプレキシティを近似するための符号化方法

として、逐次的符号化と非逐次的符号化の2種類があることを示した。非逐次的符号化としては2段階符号化、最尤符号化などがあり．、符号化自体の意味を離れても、それらは確率モデルの最適選択や一括学習方式のアルゴリズムの設計指針を与えている。それらの有効性はパラメータ次数推定の一致性や一括学習のサ
ンプルコンプレキシティの最小性によって保証されていることを見た。また、逐次的符号化としては混合符
号化、予測的符号化などがあり、符号化自体の意味を●離れても、それらは逐次的確率予測アルゴリズムの設

計指針を具体的に与えている。それらは対数誤差で測った累積予測誤差を最小にするという意味で最適であることを見た。以上をまとめたのが表1である。
本稿で扱わなかった重要な統計的推論の問題の1つに仮説検定と呼ばれるものがある。確率的コンプレキ

シティはユニバーサルな仮説検定問題に対してもやはり有効な検定方式を提示する。この方式の理論的安当

性はPAD学習（ProbablyAlmostDiscriminative
Learning）という文脈の中で証明されている【14】。

【5】A・Dawid， Statisticaltheory：the prequentialap−
proach， J・月・∫ねf．∫oc．A（1984），278−292．

【6】D．Haussler， GeneralizingthePACmodelforne11ral
net and otherlearning applications，

Irげorm．Com−

p止，100（1992），78−150，【7］T・Mats11Shima，H・Inazumi，andS．Hirasawa， Aclass
OfdistortionlesscodesdesigIledbyBayesdecisionthe−
Ory， Jβββrrα花5・Jγ小r↑乃・rんeor肌IT−37，5（1991），
1288−1293．

t8】J．Rissanen， Modelingbyshortestdatadescription，A≠まomα上古cα，14（1978），465−471．

【9】J．Rissanen，Siocha31ic CoTnPlexiiyin SialisiicalIn−
quzry，Worl（1Scientific，1989．

【10】J・RissanenandB．Yu， MDLlearning， inProgres3in
AulomaiionsandIγ小rmaiionSy3lem3，SpringerVer−
1ag，1992．

【11］J．Rissanen， FisherinforITlationandstochasticcoln−
Plexity， IEEE Trans．ITげor7n．Theory，IT−42，1（1996），40−47．

【12】Ⅰく・Yamanishi， Alearning criterion for stochastic
rules， 〟αCん五meエeαγ几壱乃タ9（1992），165−203．

【13】Ⅰく・Yamanishi， Generalizedstochasticcomplexityand
its applications tolearning， in Proceeding30flhe
JタタイCo可e↑、e↑tCeO乱丁γ小rmαま壱0几∫c五eγ乙Ceα几d∫yβtem3フ（1994），VOl．2，ppて63−76臥【14】K・Yamanishi， Probablyalmostdiscriminativelearn−ing， Machine Learning，18（1995），23−50．
【15】K・Yamanishi，Randomizedapproximateaggregating

Strategiesandtheirapplicationstopredictionanddis−

Crimination： inProc・OfCOLT95，（1995），pP．83−90．
【16】K．Yamanishi， Aloss bound modelfor on−1ine
StOChastic prediction algorithms， Jγ小rm．Comput．，

参考文献【1】B．Clarke and A．Barron，
asymptoticsofBayesmethods，
rんeoryIT−36（1990），453−471．

1996年7 月号

IEEE升αnS，h小rm．TheoryIT−

29，2（1983），211−215．

Information−theoretic
IEEE升αnS．IrJomn．

119，1，（1995），39−54．
【17】K・Yamanishi，

On−1inemaximumlikelihoodpredic−

tionwithrespecttogellerallossfunctions，りtoappear© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（25）385

inJr．Comput．Sys．Sci，，（1995）．Anextendeda・bstract

appearedinProc．ofEuroCOLT 95，Springer，（1995），
pp．84−98・【18】K．Yamanishi， A randomized approximation ofthe
MDLforstochasticmodelswitIlhiddenvariables，

toappearinProc，COLT 96，（1996）・【19】山西、韓、 MDL入門：情報理論の立場から， 人工知能学会誌 vo17，No3，May（1992）， 45−52．

報文集価格表（会員価格）
R−72−1 コーポレイト・プランニング訪米視察団報告書

1，200円

T−73−1 ネットワーク構造を有するオペレーションズ・リサーチ

1，200円問題の電算機処理に関する基礎研究

T−73−2 新手法による高速道路交通量の推計

1，200円

T−76−1 オペレーションズ・リサーチのためのデータとプログラムに関する研究

4，000円T−77−2 環境アセスメントにおけるシステム分析手法に関する研究

2，000円

一第一編 環境影響評価支援システムの検討●

一第二編 空間に対する影響の評価に関する調査研究
T−77−3 環境アセスメントにおけるシステム分析手法に関する研究

2，400円

一第三編 米国における環境アセスメントマニュアル事例調査
R−82−1「欧州におけるOR実施状況」視察団報告書

1，200円R−84−1「米国におけるORの実施」視察団報告書

1，200円

英文別刷 A New Strategy for North−SOuth Cooperation

1，000円−Micro−electronics as a Catalyst

R−88−1「南米諸国とのOR交流視察団」報告書

1，200円T−94−1NewDirectioninSimulationforManufacturing andCommunications
6，000円R−94−2「ポルトガル・スペインとのOR交流視察団」報告書

1，000円

T−95−1 巨大プロジェクトに関するOR

3，500円オペレーションズ・リサーチ

386（26）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.