教師なし学習問題のための一般的なメタアルゴリズムベースのフレームワーク

11月13日、マイクロソフトリサーチとプリンストン大学の研究者らは、ガウス分布とサブスペースクラスタリングの混合など、教師なし学習の問題に対する効率的なアルゴリズムを設計するための一般的なフレームワークを提案した。

研究者らが提案したフレームワークは、下限学習計算式のメタアルゴリズムを使用してノイズ問題を解決します。これは、ノイズのない状態で算術式を学習するためのフレームワークを設計した Garg、Kayal、Saha (FOCS '20) による最近の研究に基づいています。メタアルゴリズムの重要な要素は、「ロバストなベクトル空間分解」と呼ばれる新しい問題に対する効率的なアルゴリズムです。

特定の行列が十分に大きい最小の非ゼロ特異値を持つ場合、メタアルゴリズムがうまく機能することが示されています。 「この条件は問題の滑らかなインスタンスに当てはまると推測しており、したがって、私たちのフレームワークは滑らかな設定でこれらの問題に対する効率的なアルゴリズムを生み出すでしょう。」

この研究は、11月13日に「ノイズが存在する状況での算術式の学習：一般的な枠組みと教師なし学習への応用」というタイトルでarXivプレプリントプラットフォームで公開されました。

教師なし学習では、ラベルや直接の人間による監督を使用せずに、データ内の隠れたパターンと構造を発見します。

ここで研究者は、優れた数学的構造を持つデータ、または数学的に明確に定義された分布から生成されたデータを考慮します。前者の例としては、データ ポイントを特定の類似性パターンに基づいて意味のあるクラスターにグループ化でき、その基礎となるクラスターを見つけることが目標である場合が挙げられます。後者の例としては混合モデリングが挙げられます。これは、データが簡潔に記述された確率分布（ガウス分布など）の混合によって生成されると想定し、サンプルからこれらの分布のパラメータを学習することを目標としています。

多くの教師なし学習問題を解決するための一般的なフレームワークはモーメント法であり、データの統計モーメントを使用してモデルの基礎となる構造またはパラメータを推測します。多くの教師なし学習の問題シナリオでは、基礎となるデータが何らかの優れた数学的構造を持っているため、データのモーメントはパラメーターの明確に定義された関数です。ヒューリスティックな議論では、一般的にはその逆が当てはまる、つまり、構造/分布のパラメータは、データのいくつかの低次のモーメントによって一意に決定されることが多いことが示唆されています。この一般的な方向性において、主な課題は、（経験的）モーメントから潜在パラメータを（近似的に）回復するアルゴリズムを設計することです。

また、アルゴリズムは効率的で、ノイズ耐性（つまり、モーメントが正確ではなくおおよそしかわかっていない場合でもうまく機能する）、さらには外れ値耐性（つまり、いくつかのデータ ポイントが基礎となる構造/分布に準拠していない場合でもうまく機能する）であることが必要です。しかし、この分野では最も単純な問題でさえ NP 困難になる傾向があり、これはノイズや外れ値がない場合でも当てはまります。

したがって、最悪のケースが保証されることが証明できるアルゴリズムを実際に当てにすることはできません。しかし、このアルゴリズムが一般的に、つまりランダムな問題インスタンスに対して、あるいはより理想的には、スムーズに選択されたインスタンスに対して、うまく機能することが保証されることを期待できます。その結果、教師なし学習におけるこれらの各問題に対して、効率性、ノイズ許容度、外れ値許容度、証明可能な保証のレベルが異なる、さまざまなアルゴリズムが設計されてきました。

この研究では、研究者らは、このような多くの教師なし学習問題に適用可能なメタアルゴリズムを提示しています。この研究の出発点は、これらの問題の多くは、算術式の適切なサブクラスを学習するというタスクに帰着するという観察です。