13

簡単な機械学習の質問だと思います。

基本的な問題は次のとおりです。新しいオブジェクトと、オブジェクトに関する説明のリストが繰り返し与えられます。例: new_object: 'bob'new_object_descriptions: ['tall','old','funny']。次に、なんらかの機械学習を使用して、過去に処理した 10 個以下の最も類似した説明を持つオブジェクトを見つける必要があります (例: past_similar_objects: ) ['frank','steve','joe']。次に、これらのオブジェクトが実際に bob に似ているかどうかを直接測定できるアルゴリズムがあります (たとえば、 correct_objects: ) ['steve','joe']。次に、分類子には、成功した一致のこのフィードバック トレーニングが与えられます。次に、このループが新しいオブジェクトで繰り返されます。a 疑似コードは次のとおりです。

Classifier=new_classifier()

while True:
    new_object,new_object_descriptions = get_new_object_and_descriptions()
    past_similar_objects = Classifier.classify(new_object,new_object_descriptions)
    correct_objects = calc_successful_matches(new_object,past_similar_objects)
    Classifier.train_successful_matches(object,correct_objects)

ただし、使用できる分類子を制限する可能性のあるいくつかの規定があります。

  • この分類子には何百万ものオブジェクトが配置されるため、分類とトレーニングは何百万ものオブジェクト タイプに十分にスケーリングし、高速である必要があります。これは、スパムかスパムでないかの 2 つのタイプだけに最適なスパム分類器のようなものを失格にすると思います。(更新: 問題がある場合は、おそらくこれを数百万ではなく数千のオブジェクトに絞り込むことができます。)

  • 繰り返しますが、何百万ものオブジェクトが分類されているときは、正確さよりも速度を好みます。

  • 更新: 分類子は、過去のトレーニングからのフィードバックに基づいて、最も類似した 10 個 (またはそれ以下) のオブジェクトを返す必要があります。この制限がなければ、分類子が過去のすべてのオブジェクトを返すことができるため、明らかなチートになります:)

この目的のための適切で高速な機械学習アルゴリズムは何ですか?

注: calc_successful_matches 距離メトリックは計算に非常にコストがかかるため、高速な機械学習アルゴリズムを使用して、実際に高価な計算を行う前にどのオブジェクトが近くにあるかを推測しようとしています。

4

6 に答える 6

9

要件を満たしているように見える（そしておそらく統計家のジョンが提案しているものに似ている）アルゴリズムは、セマンティックハッシュです。。基本的な考え方は、ディープビリーフネットワーク（「ニューラルネットワーク2.0」と呼ばれるタイプのニューラルネットワークであり、現在非常に活発な研究分野です）をトレーニングして、オブジェクトの説明のリストのハッシュを作成することです。数値間のハミング距離が類似のオブジェクトに対応するような2進数。これはビット単位の操作を必要とするだけなので、かなり高速になります。また、これを使用して最近傍スタイルのアルゴリズムを作成できるため、当然、非常に多数のクラスに一般化されます。これは非常に優れた最先端のものです。欠点：理解して実装するのは簡単ではなく、パラメータの調整が必要です。著者はここにいくつかのMatlabコードを提供します。実装がやや簡単で、これに密接に関連しているのは、局所性鋭敏型ハッシュです。

すぐに近似したい高価な距離関数があると言ったので、これを行う別の非常に興味深いアルゴリズム、Boostmapを思い出しました。これは、ブーストを使用して、メトリックの計算にコストがかかる近似の高速メトリックを作成します。ある意味では上記の考え方に似ていますが、使用するアルゴリズムが異なります。この論文の著者は、関連する技術に関するいくつかの論文を持っていますが、それらはすべてかなり良い品質（トップカンファレンスで公開されています）で、チェックしておくとよいでしょう。

于 2010-03-26T02:21:55.110 に答える
3

このために本当に機械学習アルゴリズムが必要ですか？類似性の指標は何ですか？オブジェクトの数の次元について言及しましたが、各人に設定された特性のサイズはどうですか？特性タイプの最大数はありますか？私はこのようなことを試みるかもしれません：

1）mapという名前の名前のリストへの辞書マッピング特性を持っている

一人一人のためにp

pの各特性tについて

map [t] .add（p）;

2）次に、最も近い人を見つけたい場合は、辞書を使用して新しい一時的な辞書を作成します。

cntと呼ばれるカウントする辞書マッピング名

関心のある人の特性ごとに

map[t]の各人pに対して

cnt [p] ++;

次に、カウントが最も高いエントリが最も近くなります

ここでの利点は、マップが1回だけ作成されることです。一人当たりの特性が小さく、利用可能な特性のタイプが大きい場合、アルゴリズムは高速である必要があります。

于 2010-03-26T01:05:19.690 に答える
3

ベクトル空間モデル ( http://en.wikipedia.org/wiki/Vector_space_model ) を使用できます。あなたが学ぼうとしているのは、たとえば単純化された相互情報量の観点から、2 つのオブジェクト記述ベクトルが互いにどれだけ近いかを考慮して、用語を重み付けする方法だと思います。項からベクトルにハッシュできるため、これは非常に効率的です。つまり、共有機能のないオブジェクトを比較する必要はありません。単純なモデルは、項ごとに調整可能な重み (ベクトルごとの項ごと、項全体ごと、またはその両方) としきい値を持ちます。ベクトル空間モデルは広く使用されている手法です (たとえば、Apache Lucene では、この問題に使用できる可能性があります)。そのため、さらに検索することで、それについて多くのことを知ることができます。

あなたの例の観点から、これを非常に簡単に定式化しましょう。与えられたボブ: ['tall','old','funny'], 私は取得します

フランク：[「若い」、「背が低い、面白い」] スティーブ：[「背が高い」、「年寄り」、「不機嫌」]

Funny->{frank,...}、tall->{steve, joe,...}、および old->{steve, joe,...} からのハッシュを維持しているため

全体的な相互情報のようなものを計算します:共有タグの重み/ボブのタグの重み。その重量がしきい値を超えている場合は、それらをリストに含めます。

トレーニングの際に間違えた場合は、共有タグを変更します。私の間違いにフランクが含まれていた場合は、面白さのために重みを減らしますが、スティーブやジョーを含めなかったという間違いを犯した場合は、背の高いものと古いものの重みを増やします。

たとえば、用語の接続詞の重みを含めるなどして、これを必要に応じて洗練させることができます。

于 2010-03-25T23:38:00.333 に答える
2

SVMはかなり高速です。特に、Python 用のLIBSVMは、分類用のサポート ベクター マシンの非常に適切な実装を提供します。

于 2010-03-26T00:12:00.403 に答える
1

あなたが説明することはLocally Weighted Learning、クエリインスタンスを与えられたアルゴリズムにいくぶん似ています。それは、クエリインスタンスまでの距離によって重み付けされた隣接するインスタンスの周りでモデルをローカルにトレーニングします。

Weka（Java）は、weka.classifiers.lazy.LWLにこれを実装しています。

于 2010-03-26T02:27:12.940 に答える
1

このプロジェクトは、次の 2 つの点で典型的な分類アプリケーションから逸脱しています。

  • 新しいオブジェクトが属すると考えられるクラスを出力するのではなく (または、これらのクラスの配列をそれぞれ確率/信頼レベルとともに出力する可能性があります)、「分類子」は、オブジェクトに「十分に近い」「近傍」のリストを提供します。新しいオブジェクト。
  • 新しい分類ごとに、分類子から独立した目的関数が正しい「近隣」のリストを提供します。次に、修正されたリスト（分類子によって提供されるリストのサブセット？）を使用して、分類子をトレーニングします

2 番目のポイントの背後にある考え方は、進行中のトレーニングが強化されるため、分類子に送信され、現在のオブジェクトに類似する将来のオブジェクトがより適切に「分類」される (以前に見られたオブジェクトのより正確なセットに関連付けられる) ということです。正の (正しい) 一致への接続、分類器が最初に間違ったオブジェクトへの接続を弱めます。

これらの 2 つの特性は、明確な問題を引き起こします。
-出力が「プロトタイプ」（または種類のカテゴリ識別子）ではなくオブジェクトのリストであるという事実は、これまでに見られたオブジェクトの数が質問で示唆されているように数百万のインスタンスに向かって増加するにつれて、スケーリングを困難にします。- 分類子によって検出された一致のサブセット
に 基づいてトレーニングが行われるという事実は、過剰適合を導入する可能性があり、それにより、分類子は、誤って重み付けしなかった機能 (次元) に対して「ブラインド」になる可能性があります。トレーニングの初期段階で、重要/関連性として。(「正しい」オブジェクトのリストの作成を担当する目的関数に関して、私はあまりにも多くのことを想定している可能性があります)

おそらく、スケーリングの問題は、K-Means アルゴリズムまたは同様のアルゴリズムに基づく最初の分類器を使用した 2 段階のプロセスを持つことで処理できます。現在のオブジェクト (コレクションの 70% 以上を効果的に除外します)。これらの可能な一致は、ベクトル空間モデル (特徴の次元が値ではなく因子に基づいている場合に特に関連) またはその他のモデルに基づいて評価されます。この 2 段階のプロセスの基本的な前提は、オブジェクト コレクションがクラスタを効果的に公開することです (さまざまなディメンションに沿って比較的均等に分散されている可能性があります)。

以前に確認されたオブジェクトのサイズが大きくなるにつれて、評価する候補の数をさらに制限するもう 1 つの方法は、重複に近いものを削除し、これらの 1 つとのみ比較することです (ただし、結果で完全な重複リストを提供することです。新しいオブジェクトは、このほぼ重複するクラスの「代表」に近く、クラスのすべてのメンバーも一致します)

オーバーフィッティングの問題は扱いにくいです。考えられるアプローチは、分類子が通常は含めない一致リストに[時々]ランダムにオブジェクトを追加することです。追加のオブジェクトは、新しいオブジェクトまでの相対距離に基づいて追加できます (つまり、比較的近いオブジェクトが追加される可能性が少し高くなります)。

于 2010-03-26T01:28:30.937 に答える