38

単純な機械学習の質問. おそらくこれを解決するための多くの方法：

4 つの可能なイベントの無限のストリームがあります。

'event_1', 'event_2', 'event_4', 'event_4'

イベントは完全にランダムな順序ではありません。ほとんどのイベントが発生する順序にはいくつかの複雑なパターンがあり、残りのイベントはランダムであると仮定します。ただし、事前にパターンはわかりません。

各イベントが受信された後、過去にイベントが発生した順序に基づいて、次のイベントが何であるかを予測したいと考えています。私の質問は次のとおりです。この予測子にはどの機械学習アルゴリズムを使用すればよいですか?

予測子には、次のイベントが実際に何であったかが通知されます。

Predictor=new_predictor()

prev_event=False
while True:
    event=get_event()
    if prev_event is not False:
        Predictor.last_event_was(prev_event)
    predicted_event=Predictor.predict_next_event(event)

無限の履歴を維持することは不可能であるため、予測子がどのくらいの期間の履歴を維持する必要があるかという問題が生じます。これはあなたの答えに任せます。実用性のために、答えは無限大ではありません。

したがって、予測は何らかのローリング履歴を使用して行う必要があると思います。したがって、新しいイベントを追加して古いイベントを期限切れにすることはかなり効率的であり、たとえば、予測モデル全体を再構築する必要はありません。

研究論文の代わりに特定のコードがあれば、あなたの回答に計り知れない価値を加えることができます。Python や C ライブラリは便利ですが、何でも構いません。

更新:各ラウンドで複数のイベントが同時に発生する場合はどうでしょうか。それは解決策を変えますか？

4

5 に答える 5

23

これは基本的にシーケンス予測の問題であるため、リカレント ニューラル ネットワークまたは隠れマルコフ モデルが必要です。

振り返る時間が決まっている場合は、タイム ウィンドウ アプローチで十分です。シーケンス データを取得し、長さ n の重複するウィンドウに分割します。(たとえば、シーケンス ABCDEFG を ABC、BCD、CDE、DEF、EFG に分割します)。次に、関数近似器 (ニューラル ネットワークや線形回帰など) をトレーニングして、そのウィンドウの最初の n-1 部分を n 番目の部分にマッピングします。

予測子は、ウィンドウのサイズよりも長い時間を振り返ることはできません。RNN と HMM は理論的にはそうすることができますが、調整が難しいか、または機能しないことがあります。

(最先端の RNN 実装は PyBrain http://pybrain.orgにあります)

更新: 問題の pybrain コードは次のとおりです。(私はそれをテストしていません。いくつかのタイプミスなどがあるかもしれませんが、全体的な構造は機能するはずです。)

from pybrain.datasets import SequentialDataSet
from pybrain.supervised.trainers import BackpropTrainer
from pybrain.tools.shortcuts import buildNetwork
from pybrain.structure import SigmoidLayer

INPUTS = 4
HIDDEN = 10
OUTPUTS = 4

net = buildNetwork(INPUTS, HIDDEN, OUTPUTS, hiddenclass=LSTMLayer, outclass=SigmoidLayer, recurrent=True)

ds = SequentialDataSet(INPUTS, OUTPUTS)

# your_sequences is a list of lists of tuples which each are a bitmask
# indicating the event (so 1.0 at position i if event i happens, 0.0 otherwise)

for sequence in your_sequences:
    for (inpt, target) in zip(sequence, sequence[1:]):
        ds.newSequence()
        ds.appendLinked(inpt, target)

net.randomize()

trainer = BackpropTrainer(net, ds, learningrate=0.05, momentum=0.99)
for _ in range(1000):
    print trainer.train()

これにより、再帰型ネットワークが 1000 エポックトレーニングされ、エポックごとにエラーが出力されます。その後、次のように正しい予測を確認できます。

net.reset()
for i in sequence:
  next_item = net.activate(i) > 0.5
  print next_item

これにより、すべてのイベントのブール値の配列が出力されます。

于 2010-03-26T17:04:07.317 に答える
13

完全な履歴を保持するのではなく、過去に関する集約された情報を保持できます (予測ロジックへの入力として使用される比較的短いスライド履歴と共に)。

暫定的な実装は次のようになります
:

  • 個々のイベント数の表を保持します。目的は、順序に関係なく、4 つの異なるイベントのいずれかの確率を計算することです。
  • バイグラムカウントのテーブル、つまり [これまでに観測されたイベントの累積カウント]を保持します テーブル
    は空で始まり、2 番目のイベントが観測されると、カウント 1 で最初のバイグラムを保存できます。 2 番目と 3 番目のイベントがテーブルに「追加」されます。既存のバイグラムのカウントをインクリメントするか、元のカウント 1 を新しい (これまでにない) バイグラムとして追加します。
    並行して、テーブル内のバイグラムの総数を保持します。
    この表と合計集計により、1 つ前のイベントに基づいて、特定のイベントの確率を計算できます。
  • 同様の方法で、トライグラム カウントのテーブルと、見られた合計トライグラムの実行中の集計を保持します (これはバイグラムの数から 1 を引いたものに等しいことに注意してください。それぞれの 1 つが新しいイベントごとに追加されます)。このトライグラム テーブルを使用すると、先行する 2 つのイベントに基づいて、特定のイベントの確率を計算できます。
  • 同様に、最大で 10 グラムまでの N グラムのテーブルを保持します (これを増減する必要があるかどうかはアルゴリズムが判断します)。
  • スライディング ウィンドウを最後の 10 個のイベントに保持します。
  • 上記の表は、予測の基礎を提供します。一般的な考え方は次のとおりです。
    • 異なる N グラムに基づく個々の確率の加重平均として、次のイベントの確率を表す数式を使用します。
    • 数式で対応する重みを増やすことにより、より良い個々の N グラム長に報酬を与えます。逆の方法で悪い長さを罰します。(個々のイベントの限界確率を考慮する必要があることに注意してください。これは、それらに関連する相対的に低い予測値に関係なく、たまたま最も頻繁なイベントを予測する N グラムを優先しないためです)
    • システムが十分な数のイベントを「確認」したら、長い N グラムに関連付けられた重みの現在の値を確認します。これらの値が比較的高い場合は、テーブルを追加して、より大きな N グラムに関する集計情報を保持することを検討してください。（残念ながら、これは空間と時間の両方の観点からアルゴリズムを傷つけます）

上記の一般的なロジックにはいくつかのバリエーションがあります。特に、個々の N-Gram の長さの予測の品質を「等級付け」するために使用される特定のメトリックの選択において。イベント分布の変化の可能性
を検出し、それに適応することに関しては、他の考慮事項を考慮する必要があります(上記では、一般的にエルゴード イベント ソースを想定しています)。考えられるアプローチの 1 つは、2 セットのテーブルを使用し (それに応じて確率を組み合わせます)、いずれかのセットのすべてのテーブルの内容を定期的に削除することです。これらのリセットに適切な期間を選択することは、本質的に、統計的に有意な量の履歴の必要性と、より短い変調を見逃さないように十分に短い期間の必要性とのバランスをとるのが難しいビジネスです...

于 2010-03-26T17:06:43.280 に答える
0

問題は、予測子がどのくらいの期間の履歴を維持する必要があるかということです

唯一の答えは「場合による」です。

これは、これがどれだけ正確である必要があるかによって異なります。無限の歴史があっても、この戦略が 100% 正確であるとは思えません。10 の履歴を試してみると x% の精度が得られ、次に 100 を試してみると y% の精度が得られます。

最終的には、システムが希望どおりに正確であるか、または精度の向上が履歴の長さの増加 (およびメモリ使用量の増加、処理時間など) の価値がないことがわかるはずです。この時点で、仕事が終わったか、新しい戦略を見つける必要があります。

価値があるのは、単純な「ソフト」ニューラルネットを調べる方が良い計画かもしれないと思うからです。

于 2010-03-26T16:10:02.347 に答える
0

コンピュータ アーキテクチャの分岐予測子について調べました (プロセッサが条件 if(EXPRESSION) を実際に評価するには時間がかかりすぎるため、「推測」して時間を節約しようとします)。この分野ではさらに多くの研究が行われていると確信していますが、現時点で私が考えることができるのはそれだけです.

私はあなたのようなユニークなセットアップを見たことがないので、自分で予備実験を行う必要があると思います. N スロットの履歴を使用して、ソリューションを X 秒間実行してみてください。正しさの比率はどれくらいですか? そして、それを同じ固定 X スロットとさまざまな N 履歴スロットと比較して、メモリと履歴の最適な比率を見つけようとします (それらをグラフ化します)。

複数のイベントが同時に発生する可能性がある場合...それは少し頭を悩ませますが、そこにはいくつかの制約が必要です。一度に無限の数のイベントが発生した場合はどうなるでしょうか? うーん、それはあなたには計算上不可能です。一度に複数のイベントを予測する予測子が有効になっている場合を除いて、一度に 1 つのイベントと同じアプローチを試みます。

于 2010-03-26T16:11:42.603 に答える
0

プロセッサは、いくつかの非常に軽量なトリックを使用して、分岐ステートメントが分岐するかどうかを予測します。これにより、効率的なパイプライニングが可能になります。たとえば、マルコフモデルほど一般的ではないかもしれませんが、その単純さゆえに興味深いものです。分岐予測に関するウィキペディアの記事は次のとおりです。Saturating Counterと2 レベルの適応予測子を参照してください。

于 2010-06-29T19:39:26.433 に答える