テストの実行

C# を使用した Winnow 分類

James McCaffrey

コード サンプルのダウンロード

James McCaffrey機械学習 (ML) の場合、分類の問題は、数値以外の個別の値を受け取り、結果を予測するモデルを作成することが目標です。たとえば、議員の所属政党 (民主党または共和党) を予測することがあります。この場合、単純ベイズ分類、ロジスティック回帰分類、ニューラル ネットワーク分類など、多種多様な分類アルゴリズムや分類手法があります。

非常にシンプルかつ興味深い分類手法として、Winnow アルゴリズムを使用する方法があります (英単語「winnow」には、「不要な項目を取り除く」という意味があります)。いつものように、Winnow 分類の雰囲気を感じ、今回の目標を確認するには、図 1 のデモ プログラムを見るのが一番です。

Winnow アルゴリズムによる分類のデモ
図 1 Winnow アルゴリズムによる分類のデモ

このデモ プログラムの目的は、16 個の法案に対する米国議会下院議員のこれまでの投票を基に、議員の所属政党 (民主党または共和党) を予測することです。米国議会下院には 435 人の議員がいます。有名なベンチマークのデータ セットには、シンプルなテキスト ファイルに格納された 435 の項目が含まれています。最初の 3 つのデータ項目は次のとおりです。

republican,n,y,n,y,y,y,n,n,n,y,?,y,y,y,n,y
republican,n,y,n,y,y,y,n,n,n,n,n,y,y,y,n,?
democrat,?,y,y,?,y,y,n,n,n,n,y,n,y,y,n,n

行の最初の列は democrat (民主党) または republican (共和党) です。次の 16 個の列は、n (反対票)、y (賛成票)、または ? (欠損、不明、または棄権票) です。16 個の列のうち最初の列は、障碍者関係の法案に対する各議員の投票を表します。次は、水道事業関係の法案への投票です。他も同様に続きます。それぞれの列に結び付けられている法案はここには記載しませんが、興味のある方は「UCI voting data」(UCI 投票データ) をインターネットで検索すれば、さまざまな場所でこのデータ セット (説明付き) が見つかります。

Winnow 分類は、非常に明確な種類の分類問題向けに設計されています。つまり、予測するクラスは可能性のある 2 つの値のうちいずれかを受け取り (バイナリ分類の問題と呼ばれます)、予測変数 (ML 用語では「フィーチャー」と呼ばれます) も可能性のある 2 つの値のうちいずれかを受け取るという分類の問題です。不明な (不足している) 値を処理すれば、この投票データ セット自体は Winnow 分類の要件を満たします。不明な値を処理する最も一般的なアプローチは、1 つでも不明な値を含むデータ行のデータ項目を単純に削除する方法です。ただし、投票データの場合、不明票の多くは反対票を意味するため、デモ プログラムでは不明な値をすべて反対票 ("no") に置き換えます。

デモ プログラムでは、投票結果の 435 個のデータ項目をすべて使用するのではなく、最初の 100 個のデータ項目を使用します。このデモでは、独立変数 X の値 "no" の投票を 0 に、"yes" の投票を 1 にエンコーディングします。また、政党を表す従属変数 Y の値は "democrat" を 0 に、"republican" を 1 にエンコーディングします。このデモでは、従属変数 Y を先頭列から末尾列に移動しました。これは、最後の列を Y 用に使用するとコーディングの際に便利であり、一般的に行われることだからです。

デモでは、エンコーディングしたデータ セット 100 項目のうち、80 項目をモデル生成のためのトレーニング セットに、残りの 20 項目をモデルの正確性評価のためのテスト セットとしてランダムに分割しました。デモでは、Winnow アルゴリズムを使用して 16 個の投票の重みを見つけます。入力ごとに重みを 1 つ付けます (0.2500、0.500、 . . 、0.0625 など)。このような重みを使用すると、デモのモデルは、トレーニング項目の 97.50% (80 項目のうち 78 項目)、およびテスト項目の 95.00% (20 項目のうち 19 項目) で正確に政党を予測します。

デモはこのモデルを使用して、16 個の法案すべてに "賛成" と投票した仮想議員の政党を予測すること完結します。このモデルに基づくと、この仮想議員は共和党であると予測されます。

今回は、少なくとも中級レベルのプログラミング スキルがあることを前提としますが、Winnow 分類アルゴリズムの知識は問いません。このデモは C# を使用してコーディングしていますが、コードを Visual Basic .NET や JavaScript などの別の言語にリファクタリングしても大きな問題は起きません。

Winnow アルゴリズムについて

説明を簡単にするために、トレーニング データは 16 個の投票ではなく、5 個の投票だけに基づくものとします。例を次に示します。

1, 0, 1, 1, 0 -> 0
1, 1, 1, 0, 1 -> 1
0, 0, 0, 1, 0 -> 1

最初の行は "賛成"、"反対"、"賛成"、"賛成"、"反対"、"民主党" を意味します。ここでモデルをトレーニングして、重み { 0.75、3.00、1.00、0.50、0.40 } が生成されたとします。予測結果を計算するために、アルゴリズムでは、各項の入力値と対応する重みを乗算した結果を加算して、合計をしきい値と比較します。たとえば、最初の行を計算した場合の合計は次のようになります。

(1 * 0.75) + (0 * 3.00) + (1 * 1.00) + (1 * 0.50) + (0 * 0.40) = 2.25

しきい値が 5.0 の場合、合計 (2.25) はしきい値よりも小さいので、予測される Y は 0 となり、この場合は正しい予測になります。

モデルのトレーニングとは、一連の重みを見つけることです。結果が決まっているトレーニング データに重みを当てはめた場合、その計算出力は既に決まっている結果と正確に一致する必要があります。Winnow アルゴリズムを大まかな擬似コードで表すと、次のようになります。

initialize weights
loop until done
  for each training item
    compute Y
    if correct do nothing
    else if incorrect
      if computed Y is too large
        divide all relevant weights by 2.0
      else if computed Y is too small
        multiply all relevant weights by 2.0
  end for
end loop

前述の 3 つのデータ項目があるとして、次に示すように重みを初期化します。

{ 2.50, 2.50, 2.50, 2.50, 2.50 }

最初のトレーニング項目 (1, 0, 1, 1, 0 -> 0) の計算結果 Y は次のようになります。

Y = (1 * 2.50) + (0 * 2.50) + (1 * 2.50) + (1 * 2.50) + (0 * 2.50) = 7.50 -> 1

これは、計算結果の Y が 1 になり、想定する 0 よりも大きくなるので不適切な予測です。そこで、関連する重みを 2.0 で除算します。関連する重みとは、出力 1 と結び付けられている重みです。新しい重みは次のとおりです。

{ 2.50 / 2, (no change), 2.50 / 2, 2.50 / 2, (no change) }
= { 1.25, 2.50, 1.25, 1.25, 2.50 }

ここで、2 つ目のトレーニング項目 (1, 1, 1, 0, 1 -> 1) を新しい重みを使用して処理します。

Y = (1 * 1.25) + (1 * 2.50) + (1 * 1.25) + (0 * 1.25) + (1 * 2.50) = 7.50 -> 1

結果は正しい予測になったので、すべての重みはそのままにします。次に、3 つ目のトレーニング項目 (0, 0, 0, 1, 0 -> 1) を現在の重みを使用して処理します。

Y = (0 * 1.25) + (0 * 2.50) + (0 * 1.25) + (1 * 1.25) + (0 * 2.50) = 1.25 -> 0

これは、計算結果 Y が 0 になり、想定する 1 よりも小さくなるので不適切な予測です。そこで、関連する重みに 2.0 を乗算します。

{ (no change), (no change), (no change), 1.25 * 2.0, (no change) }
= { 1.25, 2.50, 1.25, 2.50, 2.50 }

Winnow トのレーニング プロセスについて少し考えてみると、2 つの重要な特徴がわかります。まず、アルゴリズムは不適切な情報だけを使用します。次に、アルゴリズムは基本的に関係のない予測の重みを 0 にして処理対象から除外します。これにより、予測変数の多くが無関係になる状況では、多くの場合、Winnow 分類が大きな効果を発揮します。Winnow の基本アルゴリズムはかなりシンプルですが、重みを初期化する方法やトレーニング停止時間の決定など、解決すべき実装の詳細がいくつかあります。

プログラムの全体構造

デモ プログラムの全体構造を図 2 に示します。WriteLine ステートメントをいくつか削除し、スペースを節約するために少し編集しています。デモ プログラムを作成するには、Visual Studio を起動して、WinnowPredict という名前の新しい C# コンソール アプリケーションを作成します。このデモは特定の .NET バージョンとの依存関係がないので、どのバージョンの Visual Studio でも動作します。テンプレート コードをエディターに読み込んだ後、最上位レベルの System 名前空間への 1 つの参照を除いて、すべての using ステートメントを削除します。次に、ソリューション エクスプローラー ウィンドウで、Program.cs ファイルの名前を WinnowProgram.cs に変更します。これにより Program クラスの名前が Visual Studio によって自動的に変更されます。

図 2 デモ プログラムの全体構造

using System;
namespace WinnowPredict
{
  class WinnowProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin Winnow algorithm demo");
      int[][] data = new int[100][];
      data[0] = new int[] { 0, 1, 0, 1, 1, 1, 0, 0,
        0, 1, 0, 1, 1, 1, 0, 1, 1 };
      // Etc.
      // Create, train and test matrices from data
      // Instantiate Winnow classifier
      // Train using training data
      // Compute accuracy
      // Predict party of hypothetical person
      Console.WriteLine("End Winnow demo");
      Console.ReadLine();
    } // Main
    static void MakeTrainTest(int[][] data, int seed,
      out int[][] trainData, out int[][] testData) { . . }
    static void ShowVector(double[] vector, int decimals,
      int valsPerRow, bool newLine) { . . }
    static void ShowMatrix(int[][] matrix, int numRows,
      bool indices) { . . }
  }
  public class Winnow
  {
    private int numInput;
    private double[] weights;
    private double threshold;
    private double alpha;
    private static Random rnd;
    public Winnow(int numInput, int rndSeed) { . . }
    public int ComputeOutput(int[] xValues) { . . }
    public double[] Train(int[][] trainData) { . . }
    public double Accuarcy(int[][] trainData) { . . }
    private static void Shuffle(int[][] trainData) { . . }
  }
}

デモ プログラムは長すぎてコラムにすべて掲載することはできませんが、付属のコード サンプルのダウンロードで完全なソース コード (WinnowProgram.cs) を確認できます。すべての Winnow 分類ロジックは、プログラムで定義した Winnow というクラスに含めています。

Main メソッドは、100 項目のデータ セットを設定するところから始まります (図 3 参照)。

図 3 100 項目のデータ セットを設定する Main メソッド

using System;
namespace WinnowPredict
{
  class WinnowProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin Winnow algorithm prediction demo");
      int[][] data = new int[100][];
      data[0] = new int[] { 0, 1, 0, 1, 1, 1, 0, 0,
        0, 1, 0, 1, 1, 1, 0, 1, 1 };
...

このデータを作成するために、UCI 投票データ セットを Web で検索し、それをコピーしてメモ帳に貼り付けます。次に、置換編集機能を使用して、配列の配列形式の行列にデータを直接配置します。経験豊富なプログラマでも C# の行列構文になじみがないかもしれませんが、このコーディング パターンにはすぐに慣れるでしょう。デモではない実際のシナリオでは、何らかのメソッドを作成して、テキスト ファイルからデータを読み込んで行列に配置します。

次に、ヘルパー メソッドを使用して、データ セット全体の最初の 4 行と最終行を表示し、このデータ セットをトレーニング セット (80 項目) とテスト セット (20 項目) に振り分けます。

Console.WriteLine("\nFirst few lines of all data are: \n");
ShowMatrix(data, 4, true);
Console.WriteLine("\nSplitting data into 80% train" +
  " and 20% test matrices");
int[][] trainData = null;
int[][] testData = null;
MakeTrainTest(data, 0, out trainData, out testData);

MakeTrainTest メソッドでは、80% と 20% の分割率がハードコードしています (トレーニング データとして使用する割合はパラメーター化することをお勧めします)。デモでは、トレーニング データの一部を表示して間違いがないことを確認後、Winnow 分類オブジェクトの初期化を行い、Train メソッドを使用してモデルを作成します (つまり、適切な重みを見つけます)。

Console.WriteLine("First few rows of training data are:");
ShowMatrix(trainData, 3, true);
Console.WriteLine("Begin training using Winnow algorithm");
int numInput = 16;
Winnow w = new Winnow(numInput, 0);
weights = w.Train(trainData);
Console.WriteLine("Training complete");

Winnow コンストラクターでは、ランダムな順番でトレーニング項目を処理するために使用する乱数生成に渡す、変数 x の数とシード値が必要です。次に、デモでは、Train メソッドで見つかった最終的な重みを表示後、トレーニング セットとテスト セットでモデルの正確性を計算します。

Console.WriteLine("Final model weights are:");
ShowVector(weights, 4, 8, true);
double trainAcc = w.Accuarcy(trainData);
double testAcc = w.Accuarcy(testData);
Console.WriteLine("Prediction accuracy on training data = " +
  trainAcc.ToString("F4"));
Console.WriteLine("Prediction accuracy on test data = " +
  testAcc.ToString("F4"));

16 個の法案すべてに "賛成" と投票した米国議会下院の仮想議員の所属政党を予測することで、このデモは完結します (図 4 参照)。

図 4 所属政党の予測

...
  Console.WriteLine("Predicting party of Representative" + "
    with all 'yes' votes");
  int[] unknown = new int[] { 1, 1, 1, 1, 1, 1, 1, 1,
  1 , 1, 1, 1, 1, 1, 1, 1 };
  int predicted = w.ComputeOutput(unknown);
  if (predicted == 0)
    Console.WriteLine("Prediction is 'democrat'");
  else
    Console.WriteLine("Prediction is 'republican'");
  Console.WriteLine("End Winnow demo");
  Console.ReadLine();
} // Main

Winnow クラス

Winnow クラスには次の 5 つのデータ メンバーがあります。

private int numInput;
private double[] weights;
private double threshold;
private double alpha;
private static Random rnd;

データ メンバー threshold (しきい値) は、計算結果 Y が 0 (しきい値以下) か 1 (しきい値以上) かの判断に使用する値を保持します。データ メンバー alpha は、不適切な Y が計算で導かれた場合に重みを減少 (研究文献での別称は「降格」) または増加 (「昇格」) するための因子です。前述のように、alpha の標準値は 2.0 です。昇格と降格の両方に 1 つの値を使用するのではなく、異なる 2 つの値を使用して実験することもできます。

Winnow コンストラクターは次のように定義します。

public Winnow(int numInput, int rndSeed)
{
  this.numInput = numInput;
  this.weights = new double[numInput];
  for (int i = 0; i < weights.Length; ++i)
    weights[i] = numInput / 2.0;
  this.threshold = 1.0 * numInput;
  this.alpha = 2.0;
  rnd = new Random(rndSeed);
}

threshold 値は入力変数の数に初期化します (たとえば、このデモの場合は 16.0 です)。この値は Winnow アルゴリズムの標準ですが、別の値で実験することも可能です。何の変化ももたらさない 1.0 による乗算があります。ここに別の値を使用できることを示していますが、入力変数の数に関連のある値にします。

入力変数の数を使用して weights 配列を確保します (デモでは 16)。それぞれの重みは、入力変数の数を 2 で除算した値で初期化します (デモでは 8.0)。この値は変更可能なので、ここでも実験のために別の値を使用することができます。Winnow アルゴリズムは、一般的に使用されている他の多くの分類アルゴリズムに比べて、あまり研究調査が進んでいません。

ComputeOutput メソッドは簡単です。

public int ComputeOutput(int[] xValues)
{
  double sum = 0.0;
  for (int i = 0; i < numInput; ++i)
    sum += weights[i] * xValues[i];
  if (sum > this.threshold)
    return 1;
  else
    return 0;
}

合計がしきい値以上やしきい値と等しい場合ではなく、しきい値よりも大きい場合に値 1 を返しています。これは変更可能であり、">" の代わりに ">=" を使用してもアルゴリズムにそれほど影響はありません。

Training メソッド

Winnow アルゴリズムのトレーニング ルーチンは、すべての ML 分類アルゴリズムの中でも最も短くシンプルなものの 1 つです。このメソッドの定義は次のように始めます。

public double[] Train(int[][] trainData)
{
  int[] xValues = new int[numInput];
  int target;
  int computed;
  Shuffle(trainData);
...

ローカル配列 "xValues" は、ターゲットの出力値ではなく、トレーニング項目の入力値を保持します。ローカル変数 "target" は、トレーニング データ項目の想定結果の Y 値を保持します。ローカル変数 "computed" は、与えられた一連の入力値 x および現在の一連の重みの計算結果 Y 値を保持します。Shuffle メソッドでは、Fisher-Yates ミニアルゴリズムを使用してトレーニング データの順番をランダムに決定します。

次に、トレーニングのメイン ループを以下のように始めます。

for (int i = 0; i < trainData.Length; ++i)
{
  Array.Copy(trainData[i], xValues, numInput); // Inputs
  target = trainData[i][numInput]; // Last value is target
  computed = ComputeOutput(xValues);
  // Update weights here
}

前述のように、トレーニングする回数はまったく明確にされていません。このデモではトレーニング データを 1 回だけ反復処理します。代わりに、トレーニング データを複数回反復処理して既定回数後に停止したり、想定する正確性を達成した場合に停止することもできます。

トレーニングのメイン ループ内では、図 5 のコードを使用して重みを更新しています。

図 5 重みの更新

if (computed == 1 && target == 0) // Decrease
{
  for (int j = 0; j < numInput; ++j)
  {
    if (xValues[j] == 0) continue; // Not relevant
    weights[j] = weights[j] / alpha; // Demotion
  }
}
else if (computed == 0 && target == 1) // Increase
{
  for (int j = 0; j < numInput; ++j)
  {
    if (xValues[j] == 0) continue; // Not relevant
    weights[j] = weights[j] * alpha; // Promotion
  }
}

見つかった最適な重みを、結果を返すローカル配列にコピーすることで、Train メソッドは終了します。

...
  } // end for
  double[] result = new double[numInput]; // = number weights
  Array.Copy(this.weights, result, numInput);
  return result;
} // Train

まとめ

今回は、N. Littlestone が 1998 年に Winnow アルゴリズムを最初に発表した「Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm」(不適切な属性が限定されたときの急速学習: 新しい線形しきい値アルゴリズム) という研究論文に基づきます。この論文は Web 上の複数の場所から PDF 形式でダウンロードすることができます。

今回のコラムの背景調査を行っているときに、F# 言語を使用して記述された興味深い Winnow アルゴリズムの実装を見つけました。この興味深い実装は、Mathias Brandewinder の個人ブログ記事に記載されています (bit.ly/1z8hfj6、英語)。

Winnow 分類は、独立変数 x がすべてバイナリであるバイナリ分類の問題用に設計されていますが、1 つ以上の変数 x がカテゴリ化される問題の実験で使用することもできます。たとえば、1 つの予測変数 "color" があり、"color" は、"red"、"green"、または "blue" という 3 つの値のいずれかを受け取るとします。1-of-N エンコーディングを使用する場合、red は (1, 0, 0)、green は (0, 1, 0)、blue は (0, 0, 1) となるので、Winnow アルゴリズムを適用することができます。


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

この記事のレビューに協力してくれた Microsoft Research 技術スタッフの Nathan Brown と Kirk Olynyk に心より感謝いたします。