8

これは教師あり学習の問題です。

有向非巡回グラフ (DAG) があります。各エッジには特徴 X のベクトルがあり、各ノード (頂点) にはラベル 0 または 1 があります。タスクは、コスト関数 w(X) を見つけて、任意のノード ペア間の最短パスの比率が最大になるようにすることです。 1 ～ 0 (最小分類誤差)。

ソリューションは適切に一般化する必要があります。ロジスティック回帰を試してみたところ、学習したロジスティック関数は、着信エッジの特徴を示すノードのラベルをかなりよく予測します。ただし、グラフのトポロジはそのアプローチでは考慮されないため、グラフ全体の解は最適ではありません。言い換えれば、ロジスティック関数は、上記の問題設定では適切な重み関数ではありません。

私の問題設定は典型的な二項分類の問題設定ではありませんが、ここに良い入門があります: http://en.wikipedia.org/wiki/Supervised_learning#How_supervised_learning_algorithms_work

詳細は次のとおりです。

  1. 各特徴ベクトル X は、実数の d 次元リストです。
  2. 各エッジには特徴のベクトルがあります。つまり、エッジのセット E = {e1, e2, .. en} と特徴ベクトルのセット F = {X1, X2 ... Xn} が与えられると、エッジ ei はベクトル Xi に関連付けられます。
  3. 関数 f(X) を考え出すことができるので、f(Xi) は、エッジ ei が 1 でラベル付けされたノードを指している可能性を示します。そのような関数の例は、私が上で述べたもので、ロジスティックによって見つけられます。回帰。しかし、上で述べたように、そのような機能は最適ではありません。

問題は次のとおりです: グラフ、開始ノード、終了ノードが与えられた場合、最適なコスト関数 w(X) をどのように学習すれば、ノード 1 と 0 の比率が最大化されますか (最小分類誤差)?

4

3 に答える 3

5

これは本当の答えではありませんが、質問を明確にする必要があります。私は可能な答えのために後で戻ってくるかもしれません。

以下は DAG の例です。

ここに画像の説明を入力

赤いノードが開始ノードで、黄色のノードが終了ノードであるとします。最短経路をどのように定義しますか

1 と 0 の最大比率 (最小分類誤差) ?

編集: 各ノードに名前を追加し、上部の 2 つのエッジに 2 つのサンプル名を追加します。

特徴ベクトルを入力として取り、その出力（エッジの重みなど）がグラフトポロジを考慮して任意のノードへの最短経路を導くことができるようなコスト関数を学習できないように私には思えます。その理由を以下に述べます。

  • あなたが述べた特徴ベクトルを持っていないとしましょう。1上記のグラフが与えられた場合、 s とsの比率に応じてすべてのペアの最短経路を見つけたい場合は、ベルマン方程式、またはより具体的にはダイカストラと適切なヒューリスティック関数0を使用するのが最適です (たとえば、パス）。もう 1 つの考えられるモデルフリーのアプローチは、q 学習を使用することです。この場合、ノードを訪問すると +1 の報酬が得られ、ノードを訪問すると -1の報酬が得られます。一度に1つずつ、各ターゲットノードのルックアップqテーブルを学習します。最後に、すべてのノードがターゲット ノードとして扱われる場合、すべてのペア最短パスが得られます。110

  • ここで、魔法のように特徴ベクトルを取得したとします。それらのベクトルがなくても最適解を見つけることができるのに、それらが存在するときになぜそれらが役立つのでしょうか?

  • 特徴ベクトルを使用してエッジの重みを最適化するコスト関数を学習できる条件が 1 つあります。つまり、特徴ベクトルはグラフ トポロジ (ノード間のリンクと1s と0s の位置) に依存します。しかし、あなたの説明にはこの依存関係はまったく見られませんでした。だから、存在しないと思います。

于 2012-11-15T01:46:29.520 に答える
1

これは、遺伝的アルゴリズムが優れた可能性を秘めている問題のように見えます。目的の関数をたとえば (ただしこれに限定されない) 特徴の線形結合として定義する場合 (2 次項を追加してから、3 次項を追加することもできます)、遺伝子は係数のベクトルです。mutator は、妥当な範囲内の 1 つまたは複数の係数のランダムなオフセットにすぎません。評価関数は、現在のミューテーションによるすべてのペアの最短パスに沿った 1 と 0 の平均比率です。各世代で、最良のいくつかの遺伝子を祖先として選択し、突然変異させて次世代を形成します。ueber 遺伝子が手元に来るまで繰り返します。

于 2012-11-21T05:04:56.760 に答える
1

あなたの質問は逆強化学習の分野に非常に近いと思います。そこでは、最適なパスの特定の「専門家のデモンストレーション」を行い、プランナー (A* または一部の強化学習エージェント) が同じパスを出力するようにコスト関数を学習しようとします。専門家のデモンストレーションとして。このトレーニングは反復的に行われます。あなたの場合、エキスパートのデモンストレーションは、最大数の 1 つのラベル付きエッジを通過するパスになるように作成できると思います。同じことに関する優れた論文へのリンクがあります: Learning to Search: Functional Gradient Techniques for Imitation Learning . これは、通常、モーション プランニングがグラフ検索問題として設定され、目的の動作を実証するためにコスト関数の学習が不可欠なロボティクス コミュニティからのものです。

于 2017-06-06T19:52:31.937 に答える