機械学習のグラフィカルモデル。 ヤンデックスワークショップ

構造分類問題を解決するためのグラフィカルモデルの装置は非常に人気がありましたが、トレーニングサンプルのパラメーターを設定するタスクは長い間開かれたままでした。 彼のレポートで、 Dmitry Vetrovは、サポートベクトル法の一般化と、グラフィックモデルのパラメーターを調整するためのアプリケーションのいくつかの機能について述べました。 ドミトリーは、ベイジアン手法グループのリーダーであり、モスクワ州立大学のVMKの准教授であり、ShADの教師です。

レポートのビデオ録画。

レポート概要：

• 機械学習におけるベイジアン手法。
• 相互依存する非表示変数を持つタスク。
• 確率的グラフィックモデル
• グラフィックモデルのパラメーターを調整するためのサポートベクターメソッドとその一般化。

機械学習の概念そのものは非常に単純です-比speaking的に言えば、それはデータ内の関係の検索です。 データは、同じ一般母集団から取得されたオブジェクトのセットによって古典的な設定で表示されます。各オブジェクトには観測可能な変数があり、隠された変数があります。 観測された変数（ 以下ではXと表記します ）はそれぞれ属性と呼ばれますが、隠れた変数（ T ）は決定されるものです。 観測可能な変数と隠された変数との間のこの関係を確立するために、トレーニングサンプル、つまり オブザーバブルコンポーネントと非表示コンポーネントの両方が既知のオブジェクトのセット。 それを見て、私たちは将来的に私たちが一連の兆候を見たときに隠されたコンポーネントを評価できるようにするいくつかの重要なルールを設定しようとしています。 トレーニング手順はほぼ次のとおりです。通常は重み（ W ）を使用して設定される一連の有効な決定ルールが固定され、その後、トレーニング中に何らかの方法でこれらの重みが調整されます。 必然的に、再トレーニングの問題は必然的に発生します。許容可能な決定ルールのファミリーが多すぎる場合、トレーニングプロセス中に、トレーニングサンプルについてその隠れたコンポーネントを完全に予測する場合に簡単にケースに到達できますが、予測は新しいオブジェクトにとっては悪いことがわかります。 機械学習の分野の研究者は、この問題を議題から取り除くために長年の努力を費やしてきました。 現在、どういうわけか成功しているようです。

ベイジアンパラダイムは機械学習のサブセクションであり、この場合、調整可能なパラメーターW 、観測された変数Xおよび隠れた変数Tの間の関係は、たとえばこれらの3つの変数グループすべてについて、共同分布の形でモデル化されると想定されています。 したがって、機械学習問題の古典的な声明、つまり、データが同じ独立したオブジェクトの同じ一般的なセットから取得されたオブジェクトのコレクションであると想定される場合、この共同分布はこの比較的単純な形式で表すことができます：



最初の要因は、既知の特性と特定の決定ルールを備えた隠し変数の分布を担当します。 2番目の要因は、特定の決定ルール（いわゆる判別モデル）について観測された変数の分布を担当します。 観測された変数の分布をモデル化しないため、この要因は興味を持ちません。 しかし、いわゆるジェネレーティブモデルの一般的な場合には、それがあるべき場所があります。 そして最後に、確率を扱うルールを単に考慮する場合に必然的に最後の要因は、重みWの先験的分布です。 決定ルールのパラメーター値。 そして、これをアプリオリ分布に設定する機会があったという事実だけが、この10年間ベイジアン手法が活況を呈している主な理由であると思われます。 長い間、90年代半ばまで、確率理論へのベイズのアプローチは、何らかの方法でパラメータにアプリオリ分布を設定する必要があることを示唆するという理由で、研究者に対してかなり懐疑的でした。 そして、伝統的な質問は-それをどこで手に入れるかでした。 もちろん、尤度関数はデータによって決定され、天井からアプリオリ分布を取りますか？ 異なるアプリオリ分布をとると、ベイズの公式を使用して異なる結果になることは明らかです。 そのため、長い間、ベイジアンアプローチはある種のメンタルゲームのように思われていました。 それにも関わらず、90年代半ばごろ、一連の作業が始まり、解決された問題の詳細を考慮すると、機械学習の一般的で標準的な方法が大幅に改善されることが証明されました。

多くの詳細があり、すべてのタスクが標準設定に削減されているように見えますが、ほとんどの場合、特定の決定ルールの何らかの形式に対する特定の事前設定があります。 つまり 実際には、重みWの特定の値に対する選好 そして、疑問が生じました。これをトレーニングサンプルの決定ルールの品質とどのように組み合わせることができますか？ 従来、機械学習手順は学習エラーを最小限に抑えるように見えます。 変数Tが既知のトレーニングサンプルに対してできるだけ正確に予測できるように、決定的なルールを構築しようとしています。 つまり 私たちは品質を高く評価できます。 これは1つの指標です。 別の指標は、 Wのいくつかの値がより好ましいと考えることです。

このすべてを統一された用語でどのようにリンクできますか？ これは、ベイジアンパラダイムの枠組み内で可能であることが判明しました。 トレーニングの質的特性は、確率的意味である尤度関数によって特徴付けられ、パラメーターの優先度は、アプリオリ分布によって特徴付けられます。 したがって、尤度関数とアプリオリ分布は、ベイズ式の枠組みで完全に組み合わされ、トレーニング中に調整するパラメーターWの値の事後分布につながります。 したがって、ベイジアンパラダイムにより、トレーニングサンプルの精度と、多くの応用問題で非常に有機的に生じた重みの値のアプリオリ選好の両方を均一な用語で正しく組み合わせることが可能になりました。したがって、これらのアプリオリ選好の導入により、結果の決定ルールの品質を大幅に改善することができました。 さらに、90年代後半からゼロ年にかけて、より高度なツールが登場しました。これにより、アプリオリ分布がデータに応じて何らかの巧妙な方法でパラメーター化および調整できるようになりました。 つまり ボタンを押すと、特定のタスクに最適なアプリオリ分布が自動的に構成され、その後、機械学習手順が実行されました。

これらの方法はすでに十分に開発されています。 機械学習の問題に関する古典的な声明が解決されたと言っても、それは誇張ではありません。 そして、人生でしばしば起こるように、古典的なプロダクションを閉じるとすぐに、非古典的なプロダクションにもっと興味があり、それがはるかに豊かで興味深いことが判明しました。 この場合の非古典的なステートメントは、隠されたオブジェクト変数が相互依存している状況です。 つまり 従来の機械学習問題で想定されていたように、このオブジェクトの兆候のみを見て、各オブジェクトの隠し変数を決定することはできません。 さらに、他のオブジェクトの兆候だけでなく、他のオブジェクトの隠された変数にも大きく依存します。 したがって、各オブジェクトの隠し変数を個別に決定することはできず、集計のみです。 以下に、相互接続された非表示コンポーネントを使用したタスクの例を多数示します。 これらの関係、つまり サンプルの隠された変数が相互に依存しているという事実を認識することで、タスクをさらに正規化するための大きな機会が開かれます。 つまり 最終的には、ソリューションの精度をさらに向上させます。

画像のセグメンテーション

最初の最も典型的な例は、画像のセグメンテーションです。 これは、相互依存する隠れ変数に関するこのような問題を解決できるツールであり、実際、グラフィックモデルのブームが始まりました。 このタスクは、デジタルカメラの開発で非常に人気があります。 これは何ですか 各ピクセルに対して、クラスラベルを配置しようとしています。 バイナリセグメンテーションの最も単純なケースでは、オブジェクトを背景から分離しようとします。 さらに複雑なケースでは、オブジェクトに何らかのセマンティクスを導入しようとしています。 原則として、この問題は標準的な分類問題と見なすことができます。 各ピクセルはオブジェクトであり、各ピクセルはKクラスのいずれかに属することができ、各ピクセルには特定の機能セットがあります。 最も単純な場合、これは色であり、テクスチャ機能、いくつかのコンテキスト情報を削除できますが、この場合、いくつかの仕様があることはかなり明らかです。 セグメント化の問題では、セグメント化の結果としていくつかのコンパクトな領域があると仮定しているためです。 この事実を形式化しようとすると、必然的に、各ピクセルを他のすべてから個別に分類またはセグメント化することができず、画像全体を一度にセグメント化することしかできなくなります。 以下は、隠し変数間に相互依存関係がある最も単純なタスクです。

ビデオ追跡

次のタスクはビデオトラッキングです。 たとえば、歩行者を検索または識別する、歩行者を識別するなど、各フレームを個別に処理できます。 または、マウスの追跡を行います。 上部のマウスは非常によく似ていますが、各マウスを正確に識別できるように追跡する必要があります。 マウスにストレスがかかると主張する生物学者は、羊毛に色のついたストロークを付ける試みを厳しく抑えています。 したがって、マウスはすべて同じです。行動を分析するためには、どのマウスがどこにいるのかを知る必要があります。 単一のフレームでは問題を解決できないことは明らかです。 できれば多数の隣接フレームを考慮する必要があります。 ここでも、マウスの識別子が隠し変数として機能する隠し変数間に相互依存関係があります。

ソーシャルネットワーク分析

ソーシャルネットワークの分析は、今や明らかなタスクです。 もちろん、ソーシャルネットワークの各ユーザーは、他のユーザーとは独立して分析できますが、情報の重要なレイヤーが失われることは明らかです。 たとえば、現在の体制に反対するユーザーを分析しようとしています。 「大統領にナバルニー！」または「市長にナバルニー！」というバナーがある場合は、もちろん、反対派として識別できますが、これにもっと注意を払い、これらのバナーを掲げない場合は、反対派に同情すると決めます。これらのバナーが喜んでぶら下がっている私の友人をあまり慎重に分析することはできません。 そのような人がたくさんいる友人の地位にいることが判明した場合、私自身もこれらの傾向に共感する可能性がわずかに高くなります。 そのようなgbshnoyトピックから逃れる場合、たとえば、特定のユーザーに関するデータ（たとえば、彼が彼のページで報告した個人データ）だけでなく、友達のサークルを見て。

2Dおよび3Dモデルの挿入

次のタスクは、画像を登録して、画像から3次元モデルを構築し、画像を2次元または3次元モデルに適合させることです。 このタスクは、登録中に画像がある程度変形することを前提としています。 もちろん、各ピクセルの変形を他のピクセルとは無関係に検索することもできますが、この場合は弾性変形が発生せず、結果はかなり嘆かわしいことは明らかです。 正式には各ピクセルをどこかに入力しますが、各ピクセルのエラーは最小限に抑えられます。 同時に、各ピクセルが独立して変形すると、画像全体が単純に崩れます。 これらの相互依存性を説明する方法の1つとして、グラフィックモデルの装置を使用できます。これにより、隠れ変数の相互依存性を分析できます。

ノイズの多いメッセージのデコード

別の重要なタスクがあります。 あまり言及されていませんが、実際には非常に関連性があり、今後数年のうちに、関連性が高まるだけです。 これは、ノイズの多いメッセージのデコードです。 今、私たちはモバイルデバイスに囲まれています。 彼らの助けを借りたデータ転送はあまり信頼性が高くなく、チャンネルはひどく過負荷になっています。 明らかに、トラフィックの需要は現在の能力を超えているため、一方でノイズ耐性があり、他方で高い帯域幅を持つプロトコルを作成するというタスクが自然に発生します。 ここで私たちは奇妙な現象に直面しています。 前世紀の50年代以来、Claude Shannonが情報理論を開発したとき、各通信チャネルには、特定の干渉強度で特定の最大スループットがあることが知られています。

理論式が導き出されました。 シャノンの定理が予測する以上の情報は、原則としてノイズの多いチャネルを介して送信することはできません。 しかし、この理論的な限界に近づくにつれて、つまり いくつかのトリッキーなアーカイブスキームを使用して情報をより効率的に送信し、エラーの修正を目的とした制御ビットを追加するほど、このメッセージのデコードスキームはより複雑になります。 つまり 最も効率的なエラー訂正コードは、デコードが非常に困難です。 単純なデコード式はありません。 したがって、シャノンの制限に達すると、デコードの複雑さが指数関数的に増加します。 メッセージをエンコードして送信することはできますが、解読することはできません。 ゼロ年に開発および標準化された最新のコード（現在、ほとんどのモバイルデバイスで使用されています）は、この理論的に可能な制限に近く、いわゆるメッセージ伝播アルゴリズムは、相互接続された隠された変数の問題を解決しようとして生まれたグラフィックモデルの理論。

シミュレーション

90年代後半には、条件付きでシミュレーションモデリングまたはエージェント環境のモデリングと呼ばれるタスクも一般的になりました。 これは、相互作用する多数のエージェントで構成されるシステムの動作を分析する試みです。 このタスクは非常に興味深いものであり、その解決のための厳密な方法はありません。 したがって、これらの問題のほとんどは、さまざまな修正を加えたモンテカルロ法を使用したシミュレーションによって解決されます。 簡単な例は、トラフィックモデリングです。 車両はエージェントとして機能しますが、すべてのドライバーが高速道路上の最も近い隣人を見て決定を下すため、文脈から車の挙動をモデル化できないことは明らかです。 そして、運転者間の最も単純な相互作用をモデルに導入するだけで、驚くべき結果が得られることがわかりました。 まず、最初に理論的に確立され、次に実際に、流れの強度に特定の限界があります。 フローがこの制限を超えると、メタステーブルになります。 不安定。 規範からのわずかな逸脱（たとえば、ドライバーの1人がもう少し急激に速度を落としてすぐに走った）は、交通渋滞がすぐそこに数十キロメートル成長するという事実につながります。 これは、トランスポートチャネルが過負荷になった場合でも、交通渋滞がなくても機能できることを意味しますが、交通渋滞はほとんど発生しません。

最初に彼らは理論的にそれを得た、そして彼らは実際にはこれが本当に起こると確信したようになった。 実際、各ルートには、その交換に応じて、フローがまだ安定して動いている一定の最大スループットがあります。 安定した動きから死んだ交通渋滞への突然の移行のこの効果は、フェーズ移行の一例です。 エージェントシステムでは、このような現象が非常に頻繁に発生し、相転移が発生する条件は決して些細なものではないことが判明しました。 シミュレートできるようにするには、適切なツールが必要です。 これらがマルチエージェントシステムであると既に述べた場合、エージェントはオブジェクトであり、オブジェクトは相互作用します。 各エージェントを記述する変数間に相互依存関係があります。

深層学習

次の例はディープラーニングです。 この画像は、ICML 2012カンファレンスのGoogle代表によるレポートから取られたもので、機械学習-ディープラーニングで比較的若いパラダイムを使用することで、Flickrデータベースからの写真の分類の質を大幅に高めることで注目を集めました。 ある意味では、これは新しい方法でのニューラルネットワークの生まれ変わりです。 従来のニューラルネットワークは、長命の注文に成功しています。 しかし、彼らは何らかの形で別のアプローチの出現を促しました。 深いネットワーク、ボルツマンネットワーク、これは特定の限定されたボルツマンマシンのセットです。 実際、これらは相互接続されたバイナリ変数の層です。 これらの変数は隠された変数として解釈することができ、決定を行う際に、観測された変数に従って何らかの形で調整されます。 しかし、ここでの特徴は、すべての隠された変数がvariablesな方法で相互接続されていることです。 そのようなネットワークを訓練し、そのようなネットワークの枠組み内で決定を下すために、相互依存変数を持つオブジェクトの分析に基づいた方法を再度適用する必要があります。

協調フィルタリング

最後に、私の頭に浮かんだ最後のアプリケーションは、協調フィルタリングまたは推奨システムです。 また、比較的新しい方向。 ただし、明らかな理由により、ますます人気が高まっています。 現在、オンラインストアは活発に開発されており、数万から数十万のアイテムを提供しています。 ユーザーがキャプチャを一lanceすることさえできない量。 ユーザーがこの巨大な品揃えから以前に何らかの形で選択した製品のみを表示することは明らかです。 したがって、推奨システムを構築するタスクがあります。 特定のユーザー（既に購入した製品、個人データ、性別、年齢）だけでなく、同様の製品を購入した他のユーザーの行動も分析することで構築できます。 繰り返しますが、変数間には相互依存関係が生じます。

グラフィックモデル

機械学習の古典的な設定から実際に離れなければならないという事実と、実際にはより複雑で興味深い世界との関連性を示すことができたと思います。 相互依存する非表示コンポーネントを持つオブジェクトがある場合、タスクに移動する必要があります。 その結果、たとえば隠れたコンポーネントなど、高度な多次元分布をモデル化する必要があります。 トラブルがあります。 最も単純な状況を想像してください。 それぞれが隠しバイナリ変数を持ち、値0/1をとることができる1000個のオブジェクトを考えてみましょう。 すべてがすべてに依存する共同分布を指定する場合は、バイナリ変数に千次元分布を正式に設定する必要があります。 質問：このような分布を設定するには、いくつのパラメーターが必要ですか？ 回答：2 ¹⁰⁰⁰または約10 ³⁰⁰です。 比較のために、観測可能な宇宙の原子の数は10 ⁸⁰です。 明らかに、全世界の計算能力を組み合わせても、 ^10,300を設定することはできません。 各ピクセルがオブジェクト/背景値を取ることができる30x30の画像を想像してください。 分布は離散的であり、2 ^1000個のパラメーターを必要とするため、このような画像のセットの分布を原理的に計算することはできません。

どうする？ 頭に浮かぶ最初のオプションは、私たちが持っている各ピクセルが他から独立して分布していると仮定します。 その後、必要なパラメータは千個だけです。 各ピクセルが値をとる確率、たとえば1。その後、-1は値が0をとる確率です。これが標準的な機械学習の仕組みです。 1つの小さな問題-すべての変数が独立しています。 つまり、これらのタスクをこの方法で解決することはできません。 質問：どうすれば少数のパラメーターに制限されますが、すべてがすべてに依存する分布を求めますか？ そして、ここでグラフィカルモデルのパラダイムが助けになります。これは、共同分布が、変数のサブセットの交差で定義された一定数の要因の積として表されることを示唆しています。 これらの要因を指定するために、従来、サンプル内のいくつかのオブジェクトを相互に接続する無向グラフが使用され、因数分解システムはこのグラフの最大クリック数によって決定されます。



これらのクリック数は非常に小さく、最大クリック数はサイズ2です。つまり、サイズ2のクリックの分布を決定するには3つのパラメーターで十分です。それぞれの要素は少数の変数で指定できます。 、比較的少数のパラメーターで共同分布を記述することができます。 一方、比較的単純な因数分解システムでさえ、すべての変数がすべての人に依存するという状況を保証します。 つまり 完全な相互依存性が得られ、一部の因数分解システムに限定されました。 因数分解システムは条件付き独立性を決定します。

主なタスク

グラフィックモデルの理論の枠組みで生じる主なタスクは何ですか？ このデバイスは、90年代後半に提案されました。因数分解システムの形で共同分布をモデル化するためです。 このようなシステムを導入したとします。 次に、機械学習の問題に戻ります。ベイズの定式化では、3つの量のグループへの分布があることが示唆されています：隠れ変数T 、観測可能変数Xおよび決定ルールWのパラメーター。 グラフィカルモデルのフレームワーク内では、タスクは非常に似ていることが判明しました。

1. 意思決定。 決定ルールWが与えられます;観測された変数を見るサンプルがあります。 課題は、隠れた変数を評価することです。 機械学習の標準的な問題に関連して、問題は簡単に解決され、誰も考慮しません。 グラフィカルモデルでは、タスクは実質的に自明ではなく、常に解決可能とはほど遠いものになりました。
   
2. 正規化定数Zの決定。 計算は必ずしも簡単ではありません。
3. 先生とのトレーニング 。 観測可能な変数だけでなく、隠れた変数も知っているトレーニングサンプルが提供されます。 これは、相互接続されたオブジェクトのコレクションです。 最大結合分布を描くベクトルWを見つける必要があります。
   
4. 教師なしで学習。 サンプルが提供されますが、その中にあるのは観測されたコンポーネントのみであり、隠されたコンポーネントはわかりません。 決定ルールを設定します。 Tにはかなりの数の構成があるため、タスクは非常に困難です。
   
5. 限界分布 。 サンプルが与えられ、 Xの観測されたコンポーネントは既知であり、決定ルールWは既知ですが、サンプルのすべての隠れ変数の最も可能性の高い構成を見つけるのではなく、任意のオブジェクトの隠れ変数の分布を見つけたいです。 多くの場合、タスクはアプリケーションに関連しています。 簡単に解決されます。
   

レポートの残りの部分は、教師による指導のタスクの分析に専念しています。 詳細なレポートはこちらでご覧ください 。