2018-09-04

August 2018

VOLUME 33 NUMBER 8

テストの実行 - C# を使用した Q 学習の紹介

James McCaffrey に心より感謝いたします。強化学習 (RL) の問題に取り組んでいます機械学習の分岐は、既知の正しい出力値を持つ明示的なトレーニングデータが存在しません。Q 学習は、いくつかの種類の RL 問題を解決するために使用できるアルゴリズムです。この記事では Q 学習のしくみを説明し、サンプルプログラムを提供します。

今回の方向性を確認する最善の方法がでシンプルなダンジョンを見て、図 1と関連付けられているデモプログラム図 2します。3 x 4 maze では、0 から 11 に示す番号付きの 12 のセルがあります。目標は、右上隅にある移動を最小限にします、11 のセルに左上隅にあるセル 8 から取得します。左に移動、右、セットアップしたり、下しますが、斜めではありません。

図 1 シンプルなダンジョン問題

Q 学習デモプログラム
図 2 Q 学習のデモプログラム

デモプログラムでは、迷路のメモリ内の表現を設定し、Q マトリックスを検索する、Q 学習アルゴリズムを使用します。Q より大きな値がより優れた、品質を表します。行のインデックスは、"from"セルと列のインデックスは、"to"セル。開始のセルが 8 の場合は、その行をスキャンし、Q の最大値がセルに 9 に 0.44 示しています。9 のセルから、行の最大値は 1.08 セルを 5 にします。プログラムが 11 のセルで、目標とする状態に到達するまで、処理が続きます。

Maze () を解決するコードを記述する必要がありますが、これは、問題は、簡単に理解するための Q 学習の Hello World 可能性が高いことはできません。この記事の後半でより現実的な問題に Q 学習を一般化する方法を説明します。

この記事では、中級以上のプログラミング、スキルを持っていても Q 学習に関する知識を想定していません前提としています。デモプログラムは c# を使用してコーディングしていますが、コードを Visual Basic や Python などの別の言語にリファクタリングしても大きな問題は起きません。デモプログラムのコードは、この記事では全体が表示されは付随するファイルのダウンロードにもあります。

コードの確認

私にとって少なくとも、Q 学習は普通と少し異なる概念は一般的な原則以降ではなく、特定のデモコードを調べて理解というのもします。スペースを節約するために少し編集したデモプログラムの全体構造を図 3 に示します。

図 3 Q 学習デモプログラムの構造

using System;
using System.Collections.Generic;
namespace QLearning
{
  class QLearningProgram
  {
    static Random rnd = new Random(1);
    static void Main(string[] args)
    {
      Console.WriteLine("Begin Q-learning maze demo");
      Console.WriteLine("Setting up maze and rewards");
      int ns = 12;
      int[][] FT = CreateMaze(ns);
      double[][] R = CreateReward(ns);
      double[][] Q = CreateQuality(ns);
      Console.WriteLine("Analyzing maze using Q-learning");
      int goal = 11;
      double gamma = 0.5;
      double learnRate = 0.5;
      int maxEpochs = 1000;
      Train(FT, R, Q, goal, gamma, learnRate, maxEpochs);
      Console.WriteLine("Done. Q matrix: ");
      Print(Q);
      Console.WriteLine("Using Q to walk from cell 8 to 11");
      Walk(8, 11, Q);
      Console.WriteLine("End demo");
      Console.ReadLine();
    }
    static void Print(double[][] Q) { . . }
    static int[][] CreateMaze(int ns) { . . }
    static double[][] CreateReward(int ns) { . . }
    static double[][] CreateQuality(int ns) { . . }
    static List<int> GetPossNextStates(int s,
      int[][] FT) { . . }
    static int GetRandNextState(int s, int[][] FT) { . . }
    static void Train(int[][] FT, double[][] R, double[][] Q,
      int goal, double gamma, double lrnRate,
      int maxEpochs) { . . }
    static void Walk(int start, int goal, double[][] Q) { . . }
    static int ArgMax(double[] vector) { . . }
  } // Program
} // ns

デモプログラムを作成するには Visual Studio を起動し、新しい c# コンソールアプリケーションプロジェクト QLearning という名前を作成します。Visual Studio 2017 を使用しましたが、デモには .NET の大きな依存関係がないため、どのバージョンの Visual Studio でも問題なく機能します。テンプレートコードが読み込まれた後、エディターのすべてを削除して不要な using ステートメント、システム名前空間への参照のみを離れること。次のデモは List < int > コレクションを使用するため Collections.Generic 名前空間への参照を追加します。

デモプログラムはクラススコープの Random オブジェクト Q 学習には、ランダムに選択のコンポーネントが含まれているためすぐにわかります。変数の ns の略、状態の数は迷路のセルの数と同義です。FT (可能な遷移) のオブジェクトは、配列の配列形式の行列です。マトリックス R は、reward マトリックスとマトリックス Q は品質の行列。

Q 学習アルゴリズムでは、パラメーターのガンマ (割引係数とも呼ばれます) と learnRate が必要です。後で説明します。Q 学習は、maxEpochs 変数 Q マトリックスを検索するアルゴリズムを使用できる期間を制御する設定、デモ、反復的です。

迷路と報酬を設定します。

迷路は CreateMaze、次のように定義されているメソッドによって作成されます。

static int[][] CreateMaze(int ns) {
  int[][] FT = new int[ns][];
  for (int i = 0; i < ns; ++i) FT[i] = new int[ns];
  FT[0][1] = FT[0][4] = FT[1][0] = FT[1][5] = FT[2][3] = 1;
  FT[2][6] = FT[3][2] = FT[3][7] = FT[4][0] = FT[4][8] = 1;
  FT[5][1] = FT[5][6] = FT[5][9] = FT[6][2] = FT[6][5] = 1;
  FT[6][7] = FT[7][3] = FT[7][6] = FT[7][11] = FT[8][4] = 1;
  FT[8][9] = FT[9][5] = FT[9][8] = FT[9][10] = FT[10][9] = 1;
  FT[11][11] = 1;  // Goal
  return FT;
}

メソッドでは、使用可能な移動を定義する行列を返します。たとえば、セル 4 から 8 のセルに移動することができますことはできませんから移動するセル 4 5 のセルに壁が方法であるためです。C# を初期化する 0 に int 配列 CreateMaze が許容される移動のみを指定する必要があるので注意してください。目的のセルの場合、11 を除く、それ自体にセルから移動することはできませんに注意してください。

Reward マトリックスは、によって定義されます。

static double[][] CreateReward(int ns) {
  double[][] R = new double[ns][];
  for (int i = 0; i < ns; ++i) R[i] = new double[ns];
  R[0][1] = R[0][4] = R[1][0] = R[1][5] = R[2][3] = -0.1;
  R[2][6] = R[3][2] = R[3][7] = R[4][0] = R[4][8] = -0.1;
  R[5][1] = R[5][6] = R[5][9] = R[6][2] = R[6][5] = -0.1;
  R[6][7] = R[7][3] = R[7][6] = R[7][11] = R[8][4] = -0.1;
  R[8][9] = R[9][5] = R[9][8] = R[9][10] = R[10][9] = -0.1;
  R[7][11] = 10.0;  // Goal
  return R;
}

この例では、11 では 10.0、報酬が他の任意の移動-0.1 の負の報酬は、目的のセルに移動します。これらの値は、ある程度任意です。一般に、RL を使用する場合、reward 構造には、まったく問題に依存するがします。ここでは、小さい負 reward punishes すべての移動よりも優先されます、短いパスをより長いパス経由で目的の効果があります。通知が発生しないため、許可されていない移動の報酬を設定する必要はありません。

Q 学習の目的は、Q 行列の値を検索することです。最初に、Q の値がすべては 0.0 に設定され、Q マトリックスを作成したようになります。

static double[][] CreateQuality(int ns) {
  double[][] Q = new double[ns][];
  for (int i = 0; i < ns; ++i)
    Q[i] = new double[ns];
  return Q;
}

可能な次の状態の定義

後ほどとを知り、システムは、遷移状態を現在の状態、Q 学習アルゴリズム必要があります。この例で、システムの状態は、同じ迷路で場所としてのみ 12 の状態があるためです。メソッドの GetPossNextStates が定義されているようになります。

static List<int> GetPossNextStates(int s, int[][] FT) {
  List<int> result = new List<int>();
  for (int j = 0; j < FT.Length; ++j)
    if (FT[s][j] == 1) result.Add(j);
  return result;
}

たとえば、s の現在の状態が 5 の場合は、し GetPossNextStates コレクションを返します < int > の一覧 (1, 6, 9) を保持しています。Q 学習アルゴリズムは、次の状態をランダムに現在の状態から場合がありますに移動します。この機能は、GetRandNextState メソッドによって定義されます。

static int GetRandNextState(int s, int[][] FT) {
  List<int> possNextStates = GetPossNextStates(s, FT);
  int ct = possNextStates.Count;
  int idx = rnd.Next(0, ct);
  return possNextStates[idx];
}

そのため、s の現在の状態が 5 の場合は、し GetRandNextState またはを返す 1 または 6 9 等しい確率 (0.33)。

Q 学習アルゴリズム

Q 学習のキーの更新式では、Bellman 数式に基づいており、図 1 の下部に表示されます。アルゴリズムは、Train メソッドに実装されます。大まかな擬似コードでは、Q 学習アルゴリズムは次のとおりです。

loop maxEpochs times
  set currState = a random state
  while currState != goalState
    pick a random next-state but don't move yet
    find largest Q for all next-next-states
    update Q[currState][nextState] using Bellman
    move to nextState
  end-while
end-loop

アルゴリズムは、まったくないと、その理解を深めて、コードを調べることで。定義を開始します。

static void Train(int[][] FT, double[][] R, double[][] Q,
  int goal, double gamma, double lrnRate, int maxEpochs)
{
  for (int epoch = 0; epoch < maxEpochs; ++epoch) {
    int currState = rnd.Next(0, R.Length);
...

トレーニングエポックの数は、試行錯誤によって決定する必要があります。代替のデザインでは、Q マトリックス内の値は変更しないでください、まで、またはイテレーションあたりの非常に小さな変更を安定化、反復処理します。内側のループでは、現在の状態が、セル 11 デモ迷路の場合の目標状態になるまで反復処理します。

while (true) {
  int nextState = GetRandNextState(currState, FT);
  List<int> possNextNextStates = GetPossNextStates(nextState, FT);
  double maxQ = double.MinValue;
  for (int j = 0; j < possNextNextStates.Count; ++j) {
    int nns = possNextNextStates[j];  // short alias
    double q = Q[nextState][nns];
    if (q > maxQ) maxQ = q;
  }
...

迷路で想像してください。A、B、C. 3 つの異なる部屋に進んでいるを参照してください。B を選択することはまだ移動してはなりません。領域 B に友人し、友人は、ルーム B は X のルームに進んでから Y、Z、およびそれらのルーム Y の値を持つこと、最適な Q を指示します。つまり、Y は、最適な [次へ]、[次へ] の状態です。

Q マトリックスに、更新プログラムが実行されます。

...
      Q[currState][nextState] =
        ((1 - lrnRate) * Q[currState][nextState]) +
        (lrnRate * (R[currState][nextState] + (gamma * maxQ)));
      currState = nextState;
      if (currState == goal) break;
    } // while
  } // for
} // Train

更新プログラムが 2 つの部分。最初の部分では、((1-lrnRate) * Q[currState][nextState]) は、悪用コンポーネントが呼び出され、古い値の一部を追加します。2 番目の部分 (lrnRate * (R [currState] [nextState] + (ガンマ * maxQ)))、エクスプローラーのコンポーネントと呼びます。LrnRate 増加報酬の現在と将来の報酬の両方の影響の大きな値 (探索) 犠牲過去報酬 (ゼロデイ攻撃)。Gamma、割引係数の値では、将来の報酬の重要性に影響します。

Q 行列を使用してください。

品質後マトリックスが計算されて、開始状態から、目的の状態への最適なパスを見つけるために使用することができます。この機能を実装する方法について説明します。

static void Walk(int start, int goal, double[][] Q) {
  int curr = start;  int next;
  Console.Write(curr + "->");
  while (curr != goal) {
    next = ArgMax(Q[curr]);
    Console.Write(next + "->");
    curr = next;
  }
  Console.WriteLine("done");
}

通知メソッドでは、開始時の状態から、目標とする状態に到達できることを前提としています。メソッドは、[次へ] の最高の状態を検索するのにヘルパー ArgMax を使用します。

static int ArgMax(double[] vector) {
  double maxVal = vector[0];  int idx = 0;
  for (int i = 0; i < vector.Length; ++i) {
    if (vector[i] > maxVal) {
      maxVal = vector[i];  idx = i;
    }
  }
  return idx;
}

たとえば、ベクトルが (0.5, 0.3、0.7, 0.2) の値を持つ場合、ArgMax 2 を返します。今回のデモでは、Q マトリックスを表示する Print メソッドを定義します。付随するファイルのダウンロードでは、表示するバージョンを取得できます。簡略化されたバージョンです。

static void Print(double[][] Q) {
  int ns = Q.Length;
  Console.WriteLine("[0] [1] . . [11]");
  for (int i = 0; i < ns; ++i) {
    for (int j = 0; j < ns; ++j) {
      Console.Write(Q[i][j].ToString("F2") + " ");
    }
    Console.WriteLine();
  }
}

まとめ

ここで示した例では、Q 学習から関連する主要な原則を理解が提供する必要があります。この記事で紹介した問題のシナリオは、個別の状態でが、Q 学習が、継続的な状態でも動作できます。迷路の例では、最も少ない移動回数で、目標とする状態を取得すると同じですが、長期的な報酬を最大化の一般的な課題です。Q 学習は、安全に産業のロボットにタスクを実行する方法をトレーニングなど、多くの評価システムをトレーニングすることができる場合に役立ちます。Q 学習はトラフィックをナビゲートする方法を無人自動車にトレーニングのようなシナリオでは適用されません。Q 学習と RL 通知ニューラルネットワークの 1980 年代に — 今、比較的少数の実用的なアプリケーションがあるが、大量の研究活動があります。同僚の多くは、いくつかポイント RL では爆発有用性に予期しない方法でと考えています。

Dr.James McCaffrey は、ワシントン州レドモンドの Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing などの複数のマイクロソフト製品にも携わってきました。Dr.McCaffrey の連絡先は jammc@microsoft.com (英語のみ) です。

この記事のレビューに協力してくれたマイクロソフト技術スタッフの Asli Celikyilmaz、Chris Lee、Ricky Loynd、Amr Sharaf、Ken Tran

この記事について MSDN マガジンフォーラムで議論する