テストの実行

多群最適化によるロジスティック回帰分類

James McCaffrey

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

James McCaffrey機械学習の最も基本的な手法の 1 つに、ロジスティック回帰 (LR) 分類があります。LR 分類が目標とするのは、ある変数が取り得る 2 つの値のうち、どちらを取るかを予測するモデルの作成です。たとえば、投票者の年齢 (x1)、性別 (x2)、年収 (x3) によって、2 人の候補者 (スミス = 0、ジョーンズ = 1) のどちらに投票するかを予測するとします。

Y を予測結果とすると、この問題の LR モデルは以下の式で表されます。

z = b0 + b1(x1) + b2(x2) + b3(x3)
Y = 1.0 / (1.0 + e^-z)

ここで b0、b1、b2、b3 は重みです。重みとは、事前に決めておかなければならない数値にすぎません。言葉で説明すると、各入力値に対応する重み b を掛けて合算し、その合計に定数 b0 を加えた値を z とします。この z を自然対数の底 e を使用する方程式に渡します。その結果、Y は常に 0 ~ 1 の値になります。Y が 0.5 未満の場合は結果を 0 とし、Y が 0.5 以上の場合は結果を 1 とします。

たとえば、投票者の年齢が 32 歳、性別が男性 (-1)、数万ドルの年収を 48.0 で表すとします。また、各重みを b0 = -9.0、b1 = 8.0、b2 = 5.0、B3 = -5.0 と仮定します。この場合は z = -9.0 + (8.0)(32) + (5.0)(-1) + (-5.0)(48.0) = 2.0、Y = 1.0 / (1.0 + e^-2.0) = 0.88 となります。

Y は 0.5 より大きいので、この投票者が選択するのは候補者 1 ("ジョーンズ") だという結論になります。しかし、問題になるのは重み b の決め方です。LR 分類のトレーニングとは、重み b の値を見つけ出すプロセスを指します。出力値がわかっているトレーニング データを使用して、計算後の出力値と既知の出力値の誤差が最小になる b 値のセットを見つけ出すのがトレーニングの考え方です。これは数学の問題で、多くの場合、数値最適化と呼ばれます。

機械学習で主に使われる最適化アルゴリズムは 10 数個あります。LR 分類トレーニングでによく使用されるのは、反復的なニュートン ラフソンと L-BFGS と呼ばれる 2 つのアルゴリズムです。今回は、多群最適化 (MSO: Multi Swarm Optimization) と呼ばれる手法を紹介します。MSO は、粒子群最適化 (PSO: Particle Swarm Optimization) のバリエーションです。MSO では仮想粒子が重み b 値のセットに相当します。群れは、鳥の群れのようにグループの行動に触発されて動く粒子の集まりを表します。MSO は、使用する群れが 1 つだけの PSO とは異なり、複数の群れが相互に影響します。

今回の方向性を確認し、MSO を使用した LR について理解する最適な方法は。具体例で考えてみることです。図 1 のデモ プログラムをご覧ください。このデモ プログラムの目的は、MSO を使用して、(プログラムで生成した) 合成データの集合に対して Y を予測する LR モデルを作成することです。

実行中の多群最適化によるロジスティック回帰
図 1 実行中の多群最適化によるロジスティック回帰

デモ プログラムは最初に 10,000 個のデータ項目をランダムに作成します。データ項目には予測変数が 5 つあります (多くの場合、機械学習用語ではこの予測変数を "フィーチャー" と呼びます)。各フィーチャー値は -10.0 ~ 10.0 の間です。データ セットの最終列にある Y 値は 0 または 1 になります。フィーチャー値は、現実の問題には対応していません。

データ セット 10,000 項目をランダムに分割し、8,000 項目を LR モデル生成に使用するトレーニング セットとし、残りの 2,000 項目をトレーニング後のモデルの正確性評価に使用するホールドアウト テスト セットとします。デモ プログラムではLR 分類を作成してから、3 個ずつの粒子を有する 4 つの群れを使用して、作成した LR 分類をトレーニングします。MSO は反復プロセスです。今回は最大反復回数 (maxEpochs) を 100 回に設定しています。

デモは、各粒子によって求められる最適 (最小) 誤差を 10 エポックごとに表示します。トレーニングが完了すると、見つかった最適な重み (4.09、10.00、8.43、1.86、-9.27、1.84) が表示されます。この 5 個の重みを使用して、LR モデルのトレーニング データでの精度 (99.98%、8,000 個のうち 7,998 個が正解) と、テスト データでの精度 (99.85%、2,000 個のうち 1,997 個が正解) を計算します。テスト データでの LR モデルの精度によって、出力値が不明な新たなデータが渡された場合に、モデルがどの程度正確に予測可能かをおおまかに把握できます。

今回は、中級以上のプログラミング スキルがあることを前提にしますが、LR 分類や MSO については知らなくても問題ありません。デモ プログラムは C# を使用してコーディングしていますが、コードを Visual Basic .NET や Python などの別の言語にリファクタリングする場合もそれほど難しくはないでしょう。

デモ コードは長すぎるためすべてを掲載することはできませんが、完全なソース コードは本稿付属のコード ダウンロードから入手できます。また、コードを小さく抑え、中心となる考え方を可能な限り明確にするため、通常のエラー チェックはすべて削除しています。

プログラムの全体構造

スペースを節約するために少し編集したプログラムの全体構造を図 2 に示します。デモ プログラムを作成するには、Visual Studio を起動して、LogisticWithMulti という名前の新しい C# コンソール アプリケーションを作成します。デモは、Microsoft .NET Framework との大きな依存関係がないので、比較的新しいバージョンの Visual Studio であれば動作します。

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

using System;
namespace LogisticWithMulti
{
  class LogisticMultiProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin demo");
      int numFeatures = 5;
      int numRows = 10000;
      int seed = 0;
      Console.WriteLine("Generating " + numRows +
        " artificial data items with " + numFeatures + " features");
      double[][] allData = MakeAllData(numFeatures, numRows, seed);
      Console.WriteLine("Done");
      Console.WriteLine("Creating train and test matrices");
      double[][] trainData;
      double[][] testData;
      MakeTrainTest(allData, 0.80, seed, out trainData, out testData);
      Console.WriteLine("Done");
      Console.WriteLine("Training data: ");
      ShowData(trainData, 4, 2, true);
      Console.WriteLine("Test data: ");
      ShowData(testData, 3, 2, true);
      Console.WriteLine("Creating Logistic Regression classifier");
      LogisticClassifier lc = new LogisticClassifier(numFeatures);
      int numSwarms = 4;
      int numParticles = 3;
      int maxEpochs = 100;
      Console.WriteLine("Setting numSwarms = " + numSwarms);
      Console.WriteLine("Setting numParticles = " + numParticles);
      Console.WriteLine("Setting maxEpochs = " + maxEpochs);
      Console.WriteLine("\nStarting training");
      double[] bestWeights = lc.Train(trainData, maxEpochs,
        numSwarms, numParticles);
      Console.WriteLine("Training complete");
      Console.WriteLine("Best weights found:");
      ShowVector(bestWeights, 4, true);
      double trainAcc = lc.Accuracy(trainData, bestWeights);
      Console.WriteLine("Accuracy on training data = " +
        trainAcc.ToString("F4"));
      double testAcc = lc.Accuracy(testData, bestWeights);
      Console.WriteLine("Accuracy on test data = " +
        testAcc.ToString("F4"));
      Console.WriteLine("End demo");
      Console.ReadLine();
    } // Main
    static double[][] MakeAllData(int numFeatures,
      int numRows, int seed) { . . }
    static void MakeTrainTest(double[][] allData, 
      double trainPct, int seed,
      out double[][] trainData, out double[][] testData) { . . }
    static void ShowData(double[][] data, int numRows,
      int decimals, bool indices) { . . }
    static void ShowVector(double[] vector, int decimals,
      bool newLine) { . . }
  } // Program
  public class LogisticClassifier { . . }
} // ns

テンプレート コードが Visual Studio エディターに読み込まれたら、内容がよくわかるようにソリューション エクスプローラー ウィンドウで Program.cs の名前を LogisticMultiProgram.cs に変更します。こうすると、Visual Studio によって Program クラスの名前が自動的に変更されます。ソース コードの先頭で、不要な名前空間を指定する using ステートメントをすべて削除し、最上位レベルのシステムの名前空間への参照のみを残します。

この LogisticMultiProgram クラスには、ヘルパー メソッドとして MakeAllData、MakeTrainTest、ShowData、および ShowVector があります。LR のロジックはすべて 1 つの LogisticClassifier クラスに含めています。LogisticClassifier クラスの内部には、入れ子にしたヘルパー クラス Particle、Swarm、および MultiSwarm を用意し、トレーニングで使用する MSO データとロジックをカプセル化しています。これらのヘルパー クラスは LogisticClassifier クラス外部で定義してもかまいません。

Main メソッドに多くの WriteLine を含めていますが、主要な呼び出しステートメントは非常にシンプルです。合成データは次のように生成します。

int numFeatures = 5;
int numRows = 10000;
int seed = 0; // Gives representative demo
double[][] allData = MakeAllData(numFeatures, numRows, seed);

メソッド MakeAllDate は、重み b の値を -10.0 ~ 10.0 の間でランダムに作成します。次にデータ項目ごとに、x の値を -10.0 ~ 10.0 の間でランダムに生成し、重み b の値と組み合わせます。その後その算出値から Y 値を生成します。この合成データは、x の値が正規化され、Y = 0 と Y = 1 の値がほぼ同数存在しているデータ セットになります。

このように作成したデータを、次のステートメントを使ってトレーニング セットとテスト セットに分けます。

double[][] trainData;
double[][] testData;
MakeTrainTest(allData, 0.80, seed, out trainData, out testData);

以下のステートメントを使って LR モデルを作成し、トレーニングを行います。

LogisticClassifier lc = new LogisticClassifier(numFeatures);
int numSwarms = 4;
int numParticles = 3;
int maxEpochs = 100;
double[] bestWeights = lc.Train(trainData, 
  maxEpochs, numSwarms, numParticles);

以下の 2 つのステートメントを使ってモデルの精度を評価します。

double trainAcc = lc.Accuracy(trainData, bestWeights);
double testAcc = lc.Accuracy(testData, bestWeights);

MSO アルゴリズムについて

以下は、MSO 最適化を表す大まかな擬似コードです。

for-each swarm
  initialize each particle to a random position
end-for
for-each swarm
  for-each particle in swarm
    compute new velocity
    use new velocity to compute new position
    check if position is a new best
    does particle die?
    does particle move to different swarm?
  end-for
end-for
return best position found

MSO アルゴリズムでは、粒子の速度計算が重要です。粒子の速度とは、粒子の移動先を制御する一連の値です。たとえば、単純な 2 次元の問題では、ある粒子の位置を (6.0, 8.0)、速度を (-2.0, 1.0) とすると、その粒子の新たな移動先の位置は (4.0, 9.0) になります。

粒子が次のように動くものとして、速度を計算します。現在と同じ方向に移動します。その時点までに見つかった最適な位置に移動します。群れの仲間が見つけた最適な位置に移動します。任意の群れの任意の粒子が見つけた最適な位置に移動します。

数学的には、x(t) を時間 t における粒子の位置とすると、新たな速度 v(t+1) を次のように計算します。

v(t+1) = w * v(t) +
         (c1 * r1) * (p(t) - x(t)) +
         (c2 * r2) * (s(t) - x(t)) +
         (c3 * r3) * (g(t) - x(t))

項 p(t) は、粒子の既知の最適位置です。項 s(t) は、その粒子と同じ群れに含まれる任意の粒子の最適位置です。項 g(t) は、任意の群れに含まれる任意の粒子のグローバルな最適位置です。項 w は、慣性質量と呼ばれる定数です。項 c1、c2、c3 は、新しい速度の各成分を最も大きく変化させる定数です。項 r1、r2、r3 は、0 ~ 1 のランダム値で、速度を更新するたびにランダム効果を適用します。

粒子の現在位置を (20.0, 30.0)、現在速度を (-1.0, -3.0) とします。また、粒子の既知の最適位置を (10.0, 12.0)、この粒子の群れに含まれる任意の粒子の既知の最適位置を (8.0, 9.0)、および任意の群れに含まれる任意の粒子の既知の最適位置を (5.0, 6.0) とします。さらに、定数 w の値を 0.7、定数 c1 と定数 c2 の値を 1.4、定数 c3 の値を 0.4 とします。最後に、ランダム値 r1、r2 および r3 をすべて 0.2 とします。

(小数第 1 位で丸めた) 粒子の新たな速度は次のようになります。

v(t+1) = 0.7 * (-1.0, -3.0) +
         (1.4 * 0.2) * ((10.0, 12.0) - (20.0, 30.0)) +
         (1.4 * 0.2) * ((8.0, 9.0) - (20.0, 30.0)) +
         (0.4 * 0.2) * ((5.0, 6.0) - (20.0, 30.0))
       = 0.7 * (-1.0, -3.0) +
         0.3 * (-10.0, -18.0) +
         0.3 * (-12.0, -21.0) +
         0.1 * (-15.0, -24.0)
       = (-8.8, -16.2)

したがって、この粒子の新しい位置は次のようになります。

x(t+1) = (20.0, 30.0) + (-8.8, -16.2)
       = (11.2, 13.8)

図 3 のグラフは、x 値が 2 つ、5 個ずつの粒子を有する群れが 3 つ、最適位置が (0, 0) である問題に対する MSO プロセスを示しています。グラフから、各群れの最初の粒子がどのように最適位置に近づいて行くかがわかります。このようにらせんを描いて動くのが MSO の特徴です。

多群最適化アルゴリズムのグラフ
図 3 多群最適化アルゴリズムのグラフ

MSO の擬似コードでは、確率は低いですが、粒子が消滅する可能性があります。粒子が消滅すると、ランダムな位置で新しい粒子が後を継ぎます。こちらも確率は低いですが、粒子が他の群れに移住することもあります。その場合は、その粒子が別の群れの粒子と交換されます。この消滅と移住のメカニズムによって、MSO にランダム要素が加わり、アルゴリズムが最適解以外から抜け出せなくなることを防ぐことができます。

MSO を使用するロジスティック回帰の実装

Train メソッドの定義は以下のように始めます。

public double[] Train(double[][] trainData, int maxEpochs,
  int numSwarms, int numParticles)
{
  int dim = numFeatures + 1;
  double minX = -10.0;
  double maxX = 10.0;
  MultiSwarm ms = new MultiSwarm(numSwarms, numParticles, dim);
...

この問題の次元数は、予測フィーチャーの数に 1 を加えた数です。1 を加えたのは定数 b0 を考慮するためです。変数 minX と変数 maxX は、Particle オブジェクトの position 配列に含まれる値の最小値と最大値を保持します。LogisticClassifier クラス内では、MultiSwarm クラスを入れ子にしています。MultiSwarm クラスのコンストラクターは、Particle オブジェクトの配列の配列を作成します。各配列は最初にランダムな位置とランダムな速度を有します。LR の Error メソッドは入れ子になった Particle 定義では直接利用できないため、MultiSwarm コンストラクターでは粒子ごとの誤差値を提供しません。そのため Train メソッドを使用して誤差情報を追加します。まず、各粒子の誤差値を次のように設定します。

for (int i = 0; i < numSwarms; ++i)
{
  for (int j = 0; j < numParticles; ++j)
  {
    Particle p = ms.swarms[i].particles[j];
    p.error = Error(trainData, p.position);
    p.bestError = p.error;
    Array.Copy(p.position, p.bestPosition, dim);
...

次に、現在の群れの最適誤差と全体としてのグローバルな最適誤差を以下のように計算します。

...
    if (p.error < ms.swarms[i].bestError) // Swarm best?
    {
      ms.swarms[i].bestError = p.error;
      Array.Copy(p.position, ms.swarms[i].bestPosition, dim);
    }
    if (p.error < ms.bestError) // Global best?
    {
      ms.bestError = p.error;
      Array.Copy(p.position, ms.bestPosition, dim);
    }
  } // j
} // i

トレーニングのメイン ループを以下のように準備します。

int epoch = 0;
double w = 0.729; // inertia
double c1 = 1.49445; // particle
double c2 = 1.49445; // swarm
double c3 = 0.3645; // multiswarm
double pDeath = 1.0 / maxEpochs;
double pImmigrate = 1.0 / maxEpochs;
int[] sequence = new int[numParticles];
for (int i = 0; i < sequence.Length; ++i)
  sequence[i] = i;

定数 w、c1、c2 の値は、ある PSO を調査した結果から得ています。興味深いことに、多くの数値最適化アルゴリズムと比較して、PSO と MSO は (フリー パラメーターやハイパー パラメーターと呼ばれる) 内部のマジック定数に使用する値の影響を比較的受けません。定数 c3 に関する利用できる調査結果はほとんどありません。この定数 c3 の影響を受けるのは、任意の群れの任意の粒子がその時点までに見つけた最適位置へ移動する粒子の動き方です。ここで使用している 0.3645 という値は、慣性定数の半分の数値で、実際に使用して上手く機能した値です。

sequence 配列は、トレーニング データのインデックスを保持します。それぞれの群れで、トレーニングのメイン ループを反復するたびに異なる順序で粒子が処理されるように、この配列をシャッフルすることになります。

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

while (epoch < maxEpochs)
{
  ++epoch;
  // Optionally print best error here
  for (int i = 0; i < numSwarms; ++i) // Each swarm
  {
    Shuffle(sequence);
    for (int pj = 0; pj < numParticles; ++pj) // Each particle
    {
      int j = sequence[pj];
      Particle p = ms.swarms[i].particles[j];
...

トレーニングを停止するタイミングを決めるのは、機械学習において最も難しい課題の 1 つです。今回は、固定の反復回数 maxEpochs を使用します。これはシンプルなアプローチですが、十分なトレーニングができないおそれがあります。あるいは、トレーニングが過剰になるおそれがあります。その場合、使用したトレーニング データには的確に適合しても、新しいデータには上手く機能しないモデルが生成される可能性があります。これを過学習といいます。過学習の対策に利用できる手法はたくさんあります。

次に、前に説明した方法で現在の粒子の新しい速度を計算します (図 4 参照)。

図 4 現在の粒子の新しい速度の計算

for (int k = 0; k < dim; ++k)
{
  double r1 = rnd.NextDouble();
  double r2 = rnd.NextDouble();
  double r3 = rnd.NextDouble();
  p.velocity[k] = (w * p.velocity[k]) +
    (c1 * r1 * (p.bestPosition[k] - p.position[k])) +
    (c2 * r2 * (ms.swarms[i].bestPosition[k] - p.position[k])) +
    (c3 * r3 * (ms.bestPosition[k] - p.position[k]));
  if (p.velocity[k] < minX)
    p.velocity[k] = minX;
  else if (p.velocity[k] > maxX)
    p.velocity[k] = maxX;
} // k

速度を計算したら、各成分の値をチェックして速度を確認します。速すぎる場合は遅くし、1 回の反復で粒子が非常に大きく移動しないようにします。ML トレーニングの一部のタスクでは、速度の規制をなくすことでトレーニングを高速化できるように見えますが、今回具体的にアドバイスできる明確な研究結果がありません。

次に、新しい速度を使用して現在の粒子の新たな位置と、関連誤差を計算します。

for (int k = 0; k < dim; ++k)
{
  p.position[k] += p.velocity[k];
  if (p.position[k] < minX)
    p.position[k] = minX;
  else if (p.position[k] > maxX)
    p.position[k] = maxX;
}

現在の粒子を移動したら、その粒子の新たな誤差を次のように計算します。

p.error = Error(trainData, p.position); // Expensive
if (p.error < p.bestError) // New best position for particle?
{
  p.bestError = p.error;
  Array.Copy(p.position, p.bestPosition, dim);
}

現在の粒子の新たな誤差が、新たな群れの最適誤差、または全体としてのグローバルな最適誤差になる場合もあります。

if (p.error < ms.swarms[i].bestError) // New best for swarm?
{
  ms.swarms[i].bestError = p.error;
  Array.Copy(p.position, ms.swarms[i].bestPosition, dim);
}
if (p.error < ms.bestError) // New global best?
{
  ms.bestError = p.error;
  Array.Copy(p.position, ms.bestPosition, dim);
}

現在の粒子の移動後に、この粒子を消して新たな粒子を生成することもできます。ランダム値がしきい値を下回った場合、新たな粒子が生成されます。

double p1 = rnd.NextDouble();
if (p1 < pDeath)
{
  Particle q = new Particle(dim); // A replacement
  q.error = Error(trainData, q.position);
  Array.Copy(q.position, q.bestPosition, dim);
  q.bestError = q.error;

消滅の確率を固定するのではなく、消滅の確率を徐々に上げていく方法もあります。たとえば次のようにします。

double pDeath = (maxProbDeath / maxEpochs) * epoch;

置き換え用の粒子を作成後、純然たる幸運によってその粒子が新たな群れの最適値または全体としてグローバルな最適値になることもあります。

if (q.error < ms.swarms[i].bestError) // Best swarm error by pure luck?
{
  ms.swarms[i].bestError = q.error;
  Array.Copy(q.position, ms.swarms[i].bestPosition, dim);
  if (q.error < ms.bestError) // Best global error?
  {
    ms.bestError = q.error;
    Array.Copy(q.position, ms.bestPosition, dim);
  }
}

この消滅のメカニズムは、現在の粒子を置き換え用の粒子と交換することで終了します。これにより、事実上現在の粒子を消滅させることができます。

...
  ms.swarms[i].particles[j] = q;
} // Die

次に、(オプションの) 移住メカニズムは次のように始めます。

double p2 = rnd.NextDouble();
if (p2 < pImmigrate)
{
  int ii = rnd.Next(0, numSwarms); // rnd swarm
  int jj = rnd.Next(0, numParticles); // rnd particle
  Particle q = ms.swarms[ii].particles[jj]; // q points to other
  ms.swarms[i].particles[j] = q;
  ms.swarms[ii].particles[jj] = p; // the exchange
...

移住メカニズムは非常におおざっぱです。コードは群れをランダムに選択し、次にその群れから粒子をランダムに選択します。選択した粒子と現在の粒子を交換します。コードからわかるとおり、ランダムに選択した粒子が現在の粒子とは異なる群れのものである保証はありません。

移住メカニズムは、2 つの群れの粒子を交換することによって、次のように 1 つまたは 2 つの群れの最適位置が新たに生じるかどうかを確認して終了します。

...
  if (q.error < ms.swarms[i].bestError) // Curr has new position
  {
    ms.swarms[i].bestError = q.error;
    Array.Copy(q.position, ms.swarms[i].bestPosition, dim);
  }
  if (p.error < ms.swarms[ii].bestError) // Other has new position
  {
    ms.swarms[ii].bestError = p.error;
    Array.Copy(p.position, ms.swarms[ii].bestPosition, dim);
  }
} // Immigrate

Train メソッドは以下のように任意の粒子が見つけた最適位置を返すことで終了します。

...
      } // j - each particle
    } // i - each swarm
  } // while
  return ms.bestPosition;
} // Train

戻り値は、LR の重みのセットを表す配列への参照です。望ましくない副作用が起こる可能性を減らす 1 つの方法としては、これらの値をローカル配列にコピーし、この配列への参照を返す方法があります。

まとめ

トレーニングに MSO を利用した LR を調査する場合、今回のコラムと付属コードが実行に役立つでしょう。MSO は実際にはアルゴリズムというよりもメタヒューリスティックです。つまり、MSO はさまざまな方法で実装できる一連の設計原則です。基本的な MSO 設計への改良は多数存在するので、ご自分で調査してみてください。

ロジスティック回帰は、機械学習分類の最もシンプルな形式の 1 つです。LR が上手く機能しない分類問題もたくさんあります。しかし、筆者を含め、機械学習の専門家の多くは通常 LR を用いて分類問題をまず調査し、それから必要に応じてさらに優れた手法を使用します。

経験上、こう配降下や L-BFGS などの計算に基づく数値最適化手法と比較すると、トレーニングに MSO を利用することで、生成される機械学習モデルが改善される傾向にあります。しかし、MSO を利用することによって 1 段階遅くなることもよくあります。


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

この記事のレビューに協力してくれたマイクロソフト技術スタッフの Todd Bello および Alisson Sol に心より感謝いたします。