第 6 章 知識情報処理入門 2

〜 アルゴリズム入門 〜

サンプルプログラムのダウンロード (msdnaa_algorithm06.exe、98.6 KB)

6.1 はじめに

近年の情報技術の発達に伴い、コンピュータを利用した知識情報処理が注目されています。知識情報処理とは、人間の知識をコンピュータ上に実現し、コンピュータの有効性を向上させる技術です。知識情報処理は、最近注目を集めている知的ロボットや、家電製品やエレベータなどの制御、言葉の構文解析などの様々な分野で利用されています。前章では、生物の進化を基に準最適解を算出する遺伝的アルゴリズムについて解説しました。しかし、知識情報処理には、遺伝的アルゴリズム以外にも多数の手法が存在します。その中でも、パターン認識や様々な予測、制御などに利用されているニューラルネットワークが最近注目されています。

そこで、本章の前半では、知識情報処理の代表的な技術であるニューラルネットワークについて解説します。さらに、本章の後半では、オブジェクト指向言語である Visual C# を用いたニューラルネットワークのプログラム例を解説します。

6.2 ニューラルネットワークとは

ニューラルネットワークとは、人間の脳の神経細胞をプログラム上でモデル化した手法です。具体的には、他の計算手法のように 1 つづつ順番に処理するのではなく、人間のように多数の神経細胞の集団を組織します。そのため、入力された情報を分散化して記憶し、複数の情報を並列処理します。また、ニューラルネットワークには、学習という概念があるため、様々な環境に適応させることができます。今日、ニューラルネットワークは、株価予測や天気予測などの予測、音声や画像などのパターン認識、家電製品やロボットなどの制御といった様々な用途で利用されています。

6.2.1 ニューロンとは

ニューロンとは、神経細胞のことです。人間の脳には、約 100 億のニューロンが存在します。また、それぞれのニューロンが約 1 万のニューロンに繋がっています。ニューラルネットワークでは、この繋がりをネットワークモデルで表現します。また、ニューロンは、複数の入力端子がありますが、出力端子は 1 つしかありません。ニューロンの構造を図 1 に、解説を表 1 に示します。

図 1 ニューロンの構造

表 1 ニューロンの解説

6.2.2 ニューロンのモデル化

ニューラルネットワークでは、図 1 に示した実際の人間のニューロンをモデル化する必要があります。ニューロンのモデル化を図 2 に、その解説を表 2 に示します。

図 2 ニューロンのモデル化

表 2 モデル化の解説

ユニットの状態の決定には、入力の結合荷重を用いてパラメータを算出する必要があります。ニューラルネットワークでは、このパラメータが閾値以上になることを発火と言います。パラメータを計算する動作式の例を次式 (1) に示します。

6.2.3 ニューラルネットワークの特徴

ニューラルネットワークには、様々な特徴があります。その特徴を次に示します。

(1) パターン情報処理

ニューラルネットワークは、雑音を含んだ入力情報から有意なパターン情報を抽出、認識、分類することに優れています。例えば、ニューラルネットワークを用いて文字 "A" をパターン認識する場合は、様々な形状の "A" を学習させます。この場合、様々な形状の "A" というデータから共通の特徴を抽出、認識、分類することで、新しい入力に対して "A" かどうかを判断します。

(2) 適応性

ニューラルネットワークの特徴の一つに、学習を行うことが挙げられます。それに伴い、遭遇した事例を学習し、様々な環境に適応していきます。そのため、ニューラルネットワークは、前章で解説した遺伝的アルゴリズムと同様に、様々な環境に絶え間なく連続的に適応させていくことにより、精度を向上させることができます。

(3) 並列分散的

ニューラルネットワークは、一般的な計算手法とは異なり、並列的に情報を連続して処理する手法です。例えば、複数のコンピュータを接続すれば並列な手法に改良できますが、膨大なコストと処理時間が必要になります。しかし、ニューラルネットワークは、多数のニューロンが並列に繋がっているため、人間の脳のように並列分散的に処理できます。

(4) 故障許容性 (ロバスト性)

ニューラルネットワークは、あるニューロンが壊れても処理を継続して行うことができます。なぜならば、情報が 1 つの場所だけに格納されるのではなく、ネットワーク全体に分散的に分配されているためです。そのため、ニューラルネットワークの故障許容性は、原子力発電所や誘導システムなどの失敗が致命的な災害を起こす場合に有効です。

(5) ニューラルネットワークの欠点

ニューラルネットワークは、上記のような様々な長所を持っていますが、苦手な課題もあります。その課題を次に示します。

• 大規模な対象に対する精密な計画・設計や制御
• 深い再帰を必要とする記号処理

これらの課題に対しては、線形理論を中心に展開されてきた数理計画法や制御理論などが有効です。あらゆる課題に適応できる万能な手法は存在しないため、それぞれの手法の長所を組み合わせることが重要になってきます。

6.2.4 ネットワークモデル

ニューラルネットワークでは、ニューロンの繋がりのことをネットワークと言います。このネットワークには、大きく分けると階層結合型ニューラルネットワークと相互結合型ニューラルネットワークの二種類があります。

(1) 階層結合型ニューラルネットワーク

階層結合型ニューラルネットワークとは、入力から出力までのニューロンがすべて順方向のみに結合されており、フィードバック結合などの相互結合の形態を持たないようなモデルのことです。代表的なものには、パーセプトロンやバックプロパケーション法などが挙げられます。階層型ニューラルネットワークの例を図3に示します。

図 3 階層型ニューラルネットワーク

(2) 相互結合型ニューラルネットワーク

相互結合型ニューラルネットワークとは、入力から出力までのニューロンの結合が順方向とは限らないモデルのことです。代表的なものには、ホップフィールドネットワークやボルツマンマシンなどが挙げられます。相互結合型ニューラルネットワークを図 4 に示します。

図 4 相互結合型ニューラルネットワーク

6.2.5 学習法

ニューラルネットワークでは、学習することにより、様々な環境に適応していきます。学習とは、シナプスの結合荷重を環境に応じて変化させることです。その学習方法には、教師あり学習と教師なし学習があります。

(1) 教師あり学習

教師あり学習とは、ニューラルネットワークからの出力と理想的な出力 (教師信号) を比較することによってその差をできるだけ小さくするようシナプスの結合荷重の値を変更する学習手法です。代表的なものには、パーセプトロンやバックプロパケーション法などが挙げられます。教師あり学習は、正しい出力だけでなく、間違った出力を教師データとして与えることができるため、パターン認識などによく利用されています。

(2) 教師なし学習

教師なし学習とは、外部から与えられる教師信号がなく、入力と出力の値のみで結合荷重の値を変更する学習手法です。教師なし学習は、間違ったデータを必要としない組み合わせ最適化問題などに利用されています。

6.3 N クイーン問題

前節までは、ニューラルネットワークの概要について解説しました。本節では、ニューラルネットワークを用いた組み合わせ最適化問題の解法の入門として「N クイーン問題」について解説します。

6.3.1 N クイーン問題とは

N クイーン問題とは、「n×n のマスの中に、n 個のクイーンを互いに効きが当たらないように並べよ」というものです。クイーンとは、チェスで使用されている駒のクイーンのことを示しています。また、「効きが当たらないように並べよ」とは、縦、横、斜めに進めるクイーンの行動範囲に含まれないように並べることです。 クイーンの動きを図 5 に、示します。

図 5 クイーンの動き

この問題の解答は、複数あります。例えば、8×8 のマスに 8 個のクイーンを並べる解は、12 通りあります。5×5 のマスに 5 個のクイーンを配置する解答例を図 6 に示します。

図 6 5個のクイーンの解答例

6.3.2 ニューロンのモデル化

ニューラルネットワークを用いて組み合わせ問題を解く場合は、ニューロンをモデル化する必要があります。具体的には、まず、チェスのマスを n 行 n 列の 2 次元の行列 V で表現します。次に、行列 V をニューロンにより 0 と 1 で表現します。クイーンが置かれている状態をニューロンの発火状態の 1 とし、置かれていない状態を 0 とします。ニューロンのモデル化の例を図 7 に示します。

図 7 ニューロンのモデル化

6.3.3 動作式

動作式とは、ニューロンが問題の条件を満たすための式であり、各ニューロンの接続を決定します。N クイーン問題では、マッカロック・ピッツニューロンを用いた動作式を用います。このニューロンの動作式を次式 (2) に示します。

A,B：任意定数、U：パラメータ値

N クイーン問題では、各行と各列に 1 つのクイーンを並べる必要があります。動作式の第1項は、各行に対して 1 つのクイーンを置くように制約しています。また、第 2 項は、各列に対して 1 つのクイーンを置くように制約しています。クイーンの数が多いほど、項の値が負の大きい値をとります。 1 つのクイーンがある場合は、項の値は、0 になります。同様に、第 3 項と第 4 項では、斜めの方向に関してクイーンを置く制約をしています。

しかし、式 (2) では、組み合わせを算出する途中でニューラルネットワークの状態が極小解に陥った場合、そこから抜け出すことができず N クイーン問題を解くことはできません。局所解に陥った例を図 8 に示します。

図 8 5個のクイーンの極小解例

局所解に陥った場合は、次式 (3) を追加する必要があります。

C：定数

式 (3) は、ヒルクライミングタームと呼ばれます。この式 h(x) は、ある i 行や j 列において、発火しているニューロンが 1 つも無い場合、Vij を発火させる働きをします。ニューロンを発火させることにより、極小解を抜け出すことが可能となります。最終的な動作式を次式 (4) に示します。

A、B、C：任意定数、U：パラメータ値

6.3.4 プログラム例

本項では、5×5 のマスに、5 個のクイーンを並べる 5 クイーン問題を Visual C# で作成します。

(1) Neuron クラス

Neuron クラスは、5×5 のマスの行列をモデル化しています。また、プロパティには、各ニューロンの発火状態と、動作式より算出するパラメータがあります。そして、メソッドには、動作式によりパラメータを算出するメソッドと、終了状態のチェックを行うメソッドがあります。Neuron クラスのプロパティを表 3 に示します。

表 3 Neuron クラスのプロパティ

Neuron クラスのメソッドを表 4 に示します。

表 4 Neuron クラスのメソッド

dU メソッドでは、まず、縦、横、斜めの方向に発火状態であるニューロンをカウントします。次に、発火状態のニューロンが縦と横の方向に存在しない場合は、ヒルクライミングタームの値を1に設定します。最後に、縦、横、斜めの方向のニューロン数とヒルクライミングタームの値を基に、動作式によりパラメータを算出します。また、動作式の定数 A、B の値を 1 に、C の値を引数により設定します。

Check メソッドでは、終了状態のチェックを行います。終了条件とは、発火状態であり、動作式によるパラメータが 0 のニューロンが縦、横、斜めにただ 1 つ存在することです。

public class Neuron
{
// 定数
public const int QUEEN_NUM = 5;  // 前提とする Queen の数
public const int A_VALUE = 1;  // ニューロン動作式の定数 A の値
public const int B_VALUE = 1;  // ニューロン動作式の定数 B の値

// グローバル変数
public int[,] U = new int[QUEEN_NUM, QUEEN_NUM];// ニューロンのパラメータ値の配列
public int[,] V = new int[QUEEN_NUM, QUEEN_NUM];// ニューロンの発火状態

public int dU(int iIndex_X, int iIndex_Y, int iCValue)
{

（中略）

// 縦方向と横方向の発火しているニューロンをカウント
for(i = 0; i < QUEEN_NUM; i++)
{
    // 発火しているニューロンの状態値を加算
    iVerticalSum = iVerticalSum + V[iIndex_X, i];
    // 発火しているニューロンの状態値を加算
  iAcrossSum = iAcrossSum + V[i, iIndex_Y];
}

i = 0;  // 初期化

// 右斜め上方向の発火しているニューロンをカウント
while ( iIndex_X - i >= 0 && iIndex_Y - i >= 0 )
{
    // 発火しているニューロンを加算
    iDiagonalNum = iDiagonalNum + V[iIndex_X - i, iIndex_Y - i];
    i++;  // 繰り返し処理用変数を加算
}

i = 0;  // 初期化

// 右斜め下方向の発火しているニューロンをカウント
while ( iIndex_X + i < QUEEN_NUM && iIndex_Y + i < QUEEN_NUM )
{
    // 発火しているニューロンを加算
    iDiagonalNum = iDiagonalNum + V[iIndex_X + i, iIndex_Y + i];
    i++;  // 繰り返し処理用変数を加算
}

i = 0;  // 初期化

// 左斜め上方向の発火しているニューロンをカウント
while ( iIndex_X - i >= 0 && iIndex_Y + i < QUEEN_NUM )
{
    // 発火しているニューロンを加算
    iDiagonalNum = iDiagonalNum + V[iIndex_X - i, iIndex_Y + i];
    i++;  // 繰り返し処理用変数を加算
}

i = 0;  // 初期化

// 左斜め下方向の発火しているニューロンをカウント
while ( iIndex_X + i < QUEEN_NUM && iIndex_Y - i >= 0 )
{
    // 発火しているニューロンを加算
    iDiagonalNum = iDiagonalNum + V[iIndex_X + i, iIndex_Y - i];
    i++;  // 繰り返し処理用変数を加算
}

// 縦方向で発火しているニューロンが無い場合
if(iVerticalSum == 0)
    iHCTValue++;  // ヒルクライミングターム値の加算
// 横方向で発火しているニューロンが無い場合
if(iAcrossSum == 0)
    iHCTValue++;  // ヒルクライミングターム値の加算

// ニューロン動作式によるパラメータ値の算出
iReturnValue = -A_VALUE * (iVerticalSum + iAcrossSum - 2)
	 - B_VALUE * (iDiagonalNum - 4) + iCValue * iHCTValue;
      
return iReturnValue;  // 戻り値
}

public bool Check(int iCValue)
{
int i, j;    // 繰り返し処理用変数
int iCount = 0;  // 発火状態のニューロンをカウントする変数

// ニューロンの状態のチェック
for(i = 0; i < QUEEN_NUM; i++)
  for(j = 0; j < QUEEN_NUM; j++)
    {
      // ニューロンが発火し，パラメータ値 U が 0 の場合
      if(V[i, j] == 1 && dU(i, j, iCValue) != 0)
        return false;  // 戻り値
      // ニューロンが発火し，パラメータ値 U が 0 でない場合
      else if(V[i, j] == 1 && dU(i, j, iCValue) == 0)
        iCount++;    // ニューロンをカウント
    }
// iCountがQUEEN_NUMと等しい場合
if ( iCount == QUEEN_NUM )
    return true;  // 戻り値
// iCountがQUEEN_NUMと等しくない場合
else
    return false;  // 戻り値
}
}

(2) メイン プログラム

本プログラムでは、まず、ニューロンの発火状態の初期設定を行います。次に、動作式によりニューロンの発火状態を変更する処理をニューロンの終了条件を満たすか、3000 回まで繰り返します。 また、極小解に陥ることを避けるため、20 回ごとに C の値を 1 から 4 に変更します。そして、終了条件を満たした場合は、ニューロンの発火状態を出力してプログラムを終了します。 定数 QUEEN_NUM の値を変更することで、5 個のクイーン以外に 8 個のクイーンなどの解も算出できます。正確な解が算出されない場合は、繰り返す回数や動作式の定数 A、B、C を適切に設定する必要があります。

private void N_Queen()
{
int i;  // 繰り返し処理用変数

Init();    // 初期設定メソッドの呼び出し

// 終了状態になるまで処理を繰り返す
for(i = 0; i < MAX_CHECK; i++)
{
// YURAGI_NUMで割り切れる場合
if (i % YURAGI_NUM == 0)
  iCValue = YURAGI_VALUE;  // ニューロン動作式の定数 C の設定
// YURAGI_NUMで割り切れない場合
else 
  iCValue = C_VALUE;    // ニューロン動作式の定数 C の設定

SetNeuronV();  // ニューロンの発火状態の設定

// ニューロンが終了状態にある場合
if(nNeurons.Check(iCValue) == true)
{

（中略）

    return;  // 処理の終了
}
}
MessageBox.Show("解が出ませんでした");  // メッセージの表示    
}

private void Init()
{
int i, j;      // 繰り返し処理用変数
Random  rRam = new Random();  // ニューロンの初期状態設定用のランダム変数
      
// ニューロンの初期設定
for(i = 0; i < QUEEN_NUM; i++)
for(j = 0; j < QUEEN_NUM; j++)
    nNeurons.V[i, j] = rRam.Next(2);  // 初期状態の設定
}

private void SetNeuronV()
{

（中略）

iDeltaU = 0;  // 初期化

// ニューロンの発火状態の設定
for(i = 0; i < QUEEN_NUM; i++)
{
iIndex = 0;      // 初期化
  iMaxU = nNeurons.U[i, iIndex];  // 初期化

// 横方向の U 値が最大のニューロンを取得  
for(j = 0; j < QUEEN_NUM; j++)
{
    iDeltaU = nNeurons.dU(i, j, iCValue);    // パラメータを算出
    nNeurons.U[i, j] = nNeurons.U[i, j] + iDeltaU;  // パラメータを加算
    // iMaxUが算出したパラメータより小さい場合
    if(iMaxU < nNeurons.U[i, j])
    {
      iIndex = j;    // インデックスの設定
      iMaxU = nNeurons.U[i, j];  // パラメータ値 U の設定
    }
}
// 横方向のニューロンの発火状態を0に設定
for ( j = 0; j < QUEEN_NUM; j++ )
    nNeurons.V[i, j] = NEURON_OFF;// 静止状態の設定
// 最大パラメータ値Ｕが0より大きい場合
if ( iMaxU > 0 )
    nNeurons.V[i, iIndex] = NEURON_ON;  // 発火状態の設定
}
}

(3) 実行結果

本プログラムの実行結果を図 9 に示します。

図 9 実行結果

6.4 まとめ

本章の前半では、知識情報処理において代表的な技術であるニューラルネットワークについて解説しました。また、本章の後半では、Visual C# のオブジェクト指向プログラミング技術を用いて N クイーン問題のプログラムを解説しました。また、ニューラルネットワークの世界では、「あいまいさ」を扱うファジィ理論と結合することや、膨大なデータから隠れたパターンを抽出するデータマイニングに活用することなどが非常に注目されています。

本連載では、プログラムの設計や開発において、いつの時代にも普遍的に重要なアルゴリズムについて解説しました。本連載を読むことにより、アルゴリズムが計算量等に大きな影響を及ぼすため、プログラムには必要不可欠であると理解できたと思います。

アルゴリズム入門

本連載は、テキスト処理、グラフィック処理、画像処理、知識情報処理などのアルゴリズムを Visual C# を用いて解説します。

• 第 1 章 Visual C# による文字列処理入門 (2003 年 5 月 1 日)
• 第 2 章 Visual C# によるグラフィックス処理と CAD 入門 (2003 年 5 月 1 日)
• 第 3 章 画像処理入門 1 (2003 年 8 月 11 日)
• 第 4 章 画像処理入門 2 (2003 年 8 月 11 日)
• 第 5 章 知識情報処理入門 1 (2003 年 8 月 11 日)
• 第 6 章 知識情報処理入門 2 (2003 年 8 月 11 日)

著者略歴

田中 成典 (たなか しげのり)

中山 浩太郎 (なかやま こうたろう)

中村 健二 (なかむら けんじ)

北川 悦司 (きたがわ えつじ)

上山 智士 (うえやま さとし)

杉町 敏之 (すぎまち としゆき)

野中 一希 (のなか かずき)