- 2014 年 5 月 20 日
- ヴァシリス・ヴリニオティス
- 。 コメントはありません
この記事は、ディリクレプロセス混合モデルによるクラスタリングに関するシリーズのパートXNUMXです。 前回、ディリクレ分布に基づいて有限混合モデルを定義し、この特定のモデルを無限にする方法について質問しました。 k個のクラスターが無限大になりがちな場合にモデルの極限をとるという考え方について簡単に説明しましたが、そのようなオブジェクトの存在は自明ではありません（つまり、実際に「モデルの極限をどのように取るか」 ”？）。 なお、make kを無限大にしたいのは、このようにしてデータ内のクラスターの総数を事前に定義する必要のないノンパラメトリックモデルが得られるためです。
更新：Datumbox Machine Learning Frameworkがオープンソースになり、無料で ダウンロード。 パッケージcom.datumbox.framework.machinelearning.clusteringをチェックして、Javaでのディリクレプロセス混合モデルの実装を確認してください。
データセットでクラスタリングを実行できるモデルを構築することが目標ですが、その前にディリクレプロセスについて説明する必要があります。 厳密な数学的定義とDPのより直感的な説明の両方を提供し、プロセスを構築する方法について説明します。 これらの構造/表現は、「現実の生活」でディリクレプロセスの発生を見つける方法と見なすことができます。
これらのブログ投稿がわかりやすくなるように調査レポートを調整しようとしたにもかかわらず、モデルを使用する前に必要な数学的ツールと分布を定義することが重要です。 ディリクレ過程モデルは活発な研究のトピックですが、統計と確率過程を十分に理解してから使用する必要があります。 別の問題は、この記事で説明するように、ディリクレプロセスはさまざまな方法で表現/構築できることです。 その結果、いくつかの学術論文では、まったく異なる表記法/規約を使用し、さまざまな観点から問題を検討しています。 この投稿では、できるだけ簡単に説明し、同じ表記法を使用するようにしています。 うまくいけば、ディリクレプロセス混合モデルの定義と、それらを実際に使用してクラスター分析を実行する方法に焦点を当てたXNUMXつの今後の記事で、より明確になるでしょう。
1.ディリクレ過程の定義
Θ空間でのディリクレ過程は確率過程です。 これは、「Θ空間上の確率分布」に対する確率分布であり、 そこから引き出すのは離散分布です。 より正式には、ディリクレ分布は確率測度の分布です。 あ 確率測度 空間Θ〜[0,1]のサブセットの関数です。 Gは、次のように表されるDP分散ランダム確率測度です。 
、パーティションの場合（A1、…An）のスペースΘ私たちはそれを持っています 
.
図1：有限パーティションのマージナルはディリクレ分布です。
DPにはXNUMXつのパラメーターがあります。最初のパラメーターは基本分布Gです。0 それは平均のように役立ちます 
。 XNUMXつ目は、厳密に正であり、逆分散のように機能する強度パラメーターαです。 
。 出力分布の値の繰り返しの程度を決定します。 aの値が高いほど、繰り返しは少なくなります。 値が小さいほど、出力分布の値の繰り返しが高くなります。 最後に、Θ空間は、DPを定義するパラメーター空間です。 さらに、空間ΘはGの定義空間でもあります0 これはGのものと同じです。
よりシンプルでより 直感的な方法 ディリクレ過程を説明すると次のようになります。 有限の方法で分割できるスペースhaveがあるとします（A1、…、An）と確率を割り当てる確率分布Gです。 Gはover上の特定の確率分布ですが、他にも多数あります。 onのディリクレプロセスはこれを正確にモデル化しています。 それは、空間onのすべての可能な確率分布にわたる分布です。 ディリクレプロセスは、G0 基本関数とα濃度パラメーター。 GはパラメーターαおよびGのDPに従って分布していると言えます0 Gがofの分割に割り当てる確率の同時分布がディリクレ分布に従う場合 あるいは、GがΘの任意の有限分割に割り当てる確率は、ディリクレ分布に従うと言えます。
図2：ディリクレプロセスのグラフィカルモデル
最後に、私たちは見ることができます DPのグラフィカルモデル。 αはスカラーハイパーパラメーターG0 はDPの基本分布、GはDPからサンプリングされたΘパラメータ空間上のランダム分布であり、パラメータとθに確率を割り当てますi G分布から描かれたパラメーターベクトルであり、Θ空間の要素です。
2.事後ディリクレ過程
事後ディリクレ過程については、 ファーガソン。 まず、ディリクレ過程からランダム確率測度Gを引きます。 
。 Gはoverの確率分布であるため、この分布からサンプリングして、独立して同一に分布したサンプルθを描くこともできます。1、…、θn 〜G.ディリクレプロセスからのドローは離散分布であるため、 
コラボレー 
の短い表記です 
これは、次の場合に1を取るデルタ関数です 
他の場所では0。 これの興味深い効果は、Gがこのように定義されているため、異なるサンプルが同じ値を持つという正の確率があることです。 
。 後で見るように、これはデータセットに対してクラスター分析を実行するために使用できるクラスター効果を作成します。
上記の定義と観察を使用して、サンプルθが与えられた場合のディリクレプロセスの事後を推定します。 それにもかかわらず、私たちはそれを知っているので & 
ベイズ規則とディリクレと多項式の共役性を使用することにより、 
& 
.
方程式1：事後ディリクレプロセス
このプロパティは非常に重要であり、さまざまなDP表現で使用されます。
3.ディリクレ過程の表現
前のセグメントでは、ディリクレプロセスを定義し、その理論モデルを示しました。 私たちが回答しなければならない重要な質問のXNUMXつは、そのようなオブジェクトが存在することをどのようにして知ることができ、 構築して表現する ディリクレプロセス。
存在の最初の兆候は、 ファーガソン コルモゴロフ整合性定理を使用し、ディリクレ過程の定義を与え、事後ディリクレ過程を記述しました。 彼の研究を続け、 ブラックウェルとマックイーン de Finettiの定理を使用して、このようなランダム確率測度の存在を証明し、ディリクレプロセスの特性を満たすBlackwell-MacQueen urnスキームを導入しました。 1994年 セチュラマン Stick-breaking構造を導入することにより、DPを構築するための追加の単純で直接的な方法を提供しました。 最後に別の表現が提供されました オルダス ディリクレプロセスを構築する効果的な方法として中華レストランプロセスを導入した人。
ディリクレ過程のさまざまな表現は数学的に同等ですが、問題を異なる視点から検討するため、それらの定式化は異なります。 以下では、文献に見られる最も一般的な表現を示し、ディリクレプロセスの推論アルゴリズムを構築するためのシンプルで計算効率の高い方法を提供する中華レストランプロセスに焦点を当てます。
3.1 Blackwell-MacQueen urnスキーム
Blackwell-MacQueen urnスキームは、ディリクレプロセスを表すために使用できます。 ブラックウェルとマックイーン。 これは、置換なしのサンプリングの反対のモデルと見なすことができるPólyaurnスキームに基づいています。 Pólyaurnスキームでは、色付きのボールを含む不透明なurnがあると想定し、ランダムにボールを描画します。 ボールを描くとき、その色を観察し、骨壷に戻し、同じ色のボールを追加します。 同様のスキームは、ディリクレプロセスを構築するためにブラックウェルとマックイーンによって使用されます。
このスキームは一連のθを生成します1、θ2、… 条件付き確率 
。 このスキームでは、G0 色と各θの分布ですn 骨壷に置かれたボールの色を表します。 の アルゴリズム 次のとおりです。
· 空のつぼから始めます。
· に比例する確率で α 私たちは描く 
この色のボールをつぼに追加します。
· n-1に比例する確率で、骨壷からランダムなボールを描画し、その色を観察し、骨壷に戻し、同じ色の追加のボールを骨壷に追加します。
以前は、ディリクレプロセスから始めて、Blackwell-MacQueenスキームを導き出しました。 次に、Blackwell-MacQueenスキームから逆に開始し、DPを導出します。 θ以来i Gからiidの方法で描画された場合、それらの共同分布は有限の順列に対して不変であり、したがって交換可能です。 その結果、デフィネッティの定理を使用することにより、それらをiidにするためのメジャーの分布が存在する必要があり、この分布はディリクレプロセスです。 その結果、Blackwell-MacQueen urnスキームがDPの表現であり、それを構築する具体的な方法を提供することを証明しました。 後で見るように、このスキームは数学的に中華レストランのプロセスと同等です。
3.2スティック破壊構造
スティック破壊構造は、によって導入されたディリクレ過程を表す代替方法です セチュラマン。 それは形成の建設的な方法です 配布と使用 次の類推：長さ1の棒があると仮定し、位置βでそれを壊します1 そして私たちはπを割り当てます1 折った棒の部分の長さに等しい。 同じプロセスを繰り返して、πを取得します2、π3、…など。 このスキームの定義方法により、無限にそれを続けることができます。
上記に基づいて、πk 次のようにモデル化できます 
ここで、 
一方、前のスキームと同様に、θはベース分布によって直接サンプリングされます 
。 したがって、G分布は、πで重み付けされたデルタ関数の合計として書くことができます。k に等しい確率 。 したがって、スティック破壊構造は、ディリクレプロセスを構築するためのシンプルで直感的な方法を提供します。
3.3中華レストランのプロセス
によって導入された中華レストランのプロセス オルダスは、ディリクレ過程を表すもうXNUMXつの効果的な方法であり、Blackwell-MacQueen urnスキームに直接リンクできます。 このスキームは、 次の類推：テーブルが無限にある中華料理店があると仮定します。 顧客がレストランに入ると、占有されているテーブルのいずれかにランダムに座るか、空いている最初の空のテーブルに座ることを選択します。
CRPは、正の整数のパーティションのスペース上の分布を定義します。 θを描くことから始めます1、…θn Blackwell-MacQueen urnスキームから。 前のセグメントで説明したように、クラスタリング効果が見込まれるため、一意のθ値の総数kはnよりも大幅に少なくなります。 したがって、これはk個のクラスター内のセット{1,2、…、n}のパーティションを定義します。 したがって、Blackwell-MacQueen urnスキームから描画すると、{1,2、…、n}セットのランダムパーティションが発生します。 中華レストランのプロセスはこれによって引き起こされます パーティションへの分散。 アルゴリズムは次のとおりです。
· 空のレストランから始めます。
· 1st 顧客は常に1に座っていますst テーブル
· n + 1th お客様には2つのオプションがあります。
o 最初の空きテーブルに確率で座る 
o k番目の占有テーブルのいずれかに確率で座る 
コラボレー 
そのテーブルに座っている人の数です
ここで、αはDPの分散値であり、nはある時点でのレストランの顧客の総数です。 潜在変数zi iのテーブル番号を格納しますth 顧客であり、1からkまでの値を取ります。n ここでkn n人の顧客がレストランにいるときの占有テーブルの総数です。 kはn は常にn以下であり、平均して約 
。 最後に、テーブル配置の確率が 
順列に対して不変です。 したがって、zi 同じサイズの顧客を持つテーブルが同じ確率を持つことを意味する交換可能です。
中華レストランのプロセスは、PólyaurnスキームおよびDirichletプロセスと密接に関連しています。 CRPは、 パーティションへの分散 （テーブル割り当て）n個のポイントの潜在変数zの空間で事前として使用できますi which クラスタの割り当てを決定します。 CRPはPólyaのurnスキームと同等ですが、各テーブル/クラスターにパラメーターを割り当てない点のみが異なります。 トーゴ CRPからPólyaのurnスキームへ 私たちは描く すべてのテーブルに対してk = 1,2…そしてすべてのxに対してi これはテーブルzにグループ化されていますi 割り当てる 
。 つまり、新しいxに割り当てますi テーブルのパラメータθ。 ついに 割り当てられません θを最初から無限テーブルに割り当てる場合、誰かが新しいテーブルに座るたびに新しいθを割り当てるだけです。 上記のすべてにより、CRPはデータセットに対してクラスター分析を実行するための計算効率の高いアルゴリズムを構築するのに役立ちます。
この投稿では、ディリクレ過程とそれを構築するいくつかの方法について説明しました。 上記のアイデアは次の記事で使用します。 ディリクレプロセス混合モデルを紹介し、中華レストランの表現を使用してディリクレプロセスを構築し、クラスター分析を実行します。 いくつかのポイントを逃した場合は、心配する必要はありません。次のXNUMXつの記事で、状況がより明確になります。
この投稿がおもしろかったと思います。 もしそうなら、少し時間を取ってFacebookやTwitterで共有してください。 🙂
