【G検定合格への道:第2回】探索・推論と知識表現について解説!

AI技術の進歩に伴い、ビジネスにおけるディープラーニングの重要性が高まっています。 G検定は、ディープラーニングの基礎知識を体系的に習得し、適切な活用方針を決定できる能力を証明する資格です。本記事では、G検定合格を目指す方に向けて、試験で問われる探索・推論と知識表現について解説します。

 

1. 探索・推論

 

探索・推論は、AIシステムが問題を解いたり、最適な行動を選択したりするために必要な能力です。G検定では、以下のトピックについて理解が求められます。

1.1 迷路(探索木)

迷路探索は、AIシステムがいかに効率的にゴールを見つけるかを問うものです。

 

コンピュータが問題を解くためには、コンピュータで処理できるような形式に変換する必要があります。迷路の行き止まりのところに順番に記号を付けていくと、木のような構造(ツリー構造)をした形になります。これを探索木と呼び、要するに場合分けです。探索には、幅優先探索深さ優先探索という2つの代表的な探索アルゴリズムがあります。

 

幅優先探索

迷路のすべてのノード(探索木の各要素)を同じレベルで探索していく方法です。

 

幅優先探索では、出発点に近いノード順に検索します。このため出発点から遠いノードほど検索は後になります。幅優先探索は、最短距離でゴールにたどり着く解を必ず見つけられます。しかし、探索の途中で立ち寄ったノードを全て記憶しておく必要があるため、解かせたい迷路が複雑になるとメモリ不足になり処理が続行できなくなる可能性があります。

 

深さ優先探索

一つのノードを深く掘り下げていき、行き詰まったら別のノードを探索する方法です。

 

深さ優先探索では、あるノードからひたすら行ける所まで進み、行き止まりになったら1つ手前のノードに戻り探索を行うということを繰り返します。深さ優先探索の場合は、求める解が見つからなければ1つ手前に戻って探索し直すので、メモリはあまり必要ありません。ただし、解を見つけるスピードは運次第で、偶然早く解が見つかることはありますが、運が悪ければ探索に時間がかかります。

 

1.2 ハノイの塔

ハノイの塔は、問題解決能力と論理的思考能力を問うパズルです。最適な解法を見つけるためには、再帰アルゴリズムを用いる必要があります。

 

3本のポール(左端、中央、右端)があり、最初は一番左側のポールに大きさの異なる穴の開いた円盤が小さいものが上になるように順に積み重ねられています。円盤は1回に1枚ずつ別のポールに移動させることができますが、小さな円盤の上に大きな円盤を乗せることは出来ません。

 

このルールに従って、全ての円盤を左端のポールから右端のポールに移動させるパズルハノイの塔と呼ばれるパズルです。

 

1.3 ロボットの行動計画

ロボットが自律的に行動するためには、周囲環境を認識し、適切な行動を選択する必要があります。G検定では、ロボットの行動計画に関する知識も問われます。

 

ロボットの行動計画も探索を利用して作成でき、プランニングと呼ばれる技術で古くから研究がなされています。あらゆる状態<前提条件>について、<行動><結果>を記述しておけば、目標とする状態に至る行動計画を立てる事ができます。プランニングの研究では、前提条件、行動、結果という3つの組み合わせで記述するSTRIPS(Stanford Research Institute Problem Solver)が有名です。

 

また、このようなプランニングを「積み木の世界」で完全に再現する研究も行われました。テリー・ウィノグラードによって開発されたシステムであるSHRDLUは、英語による指示を受け付け、コンピュータ画面に描かれる積み木の世界に存在する様々な物体(ブロック、四角錐、立方体など)を動かすことが出来ました。

 

1.4 ボードゲーム(オセロ・チェス・将棋・囲碁)

オセロ、チェス、将棋、囲碁などのボードゲームは、探索・推論と戦略の両方が求められる高度なゲームです。G検定では、これらのゲームにおけるAIの活用についても理解する必要があります。

 

2016年3月、囲碁の世界でトップレベルの実力者であるプロ棋士にDeepMind社が開発した人工知能の囲碁プログラムAlphaGo(アルファ碁)が4勝1敗と大きく勝ち越し世界中が驚愕しました。

 

ボードゲームをコンピュータで解く場合、基本は探索によって解を探りますが、その組み合わせの数が天文学的な数字になるため事実上すべてを探索しきれないという問題があったためです。

 

代表的なボードゲームの組み合わせ

  • オセロ:8×8の盤で駒が白黒で裏返しあり、約10の60乗通り
  • チェス:8×8の盤で駒が白黒6種類ずつ、約10の120乗通り
  • 将棋:9×9の盤で駒が8種類ずつ、かつ獲得した駒が使える、約10の220乗通り
  • 囲碁:19×19の盤(19路盤)で駒が白黒、約10の360乗通り

 

「コスト」の概念

木構造の探索では、探索が深くなるにつれて組み合わせが膨大になり、計算量が指数関数的に増大します。このため、しらみつぶしに探索することは到底不可能でした。

 

そこで、効率よく探索するためにコストの概念を取り入れることになりました。あらかじめ知っている知識や経験を利用してコスト計算すれば、探索を短縮できます。コストがかかり過ぎる探索を省略できるからです。ここで利用する知識のことをヒューリスティックな知識と呼びます。

 

Mini-Max法

相手の最善手も考慮した上で、自分にとって最善の手を選択するアルゴリズムです。

 

ゲームの戦略を立てるとき、Mini-Max法と呼ばれる手法を用います。考え方は単純で、自分の番では自分が最も有利(つまり自分のスコアが最大)になるように手を打つべきであり、逆に相手の番では相手が最も有利(つまり自分のスコアが最小)になるように相手は手を打つはずである、ということを前提にした戦略です。

 

その際は、未来の局面から現在の局面に向けて逆算することで戦略を立てます。逆算していくことで、互いにベストを尽くした場合に実現する経路が最終的に決まり、現在の局面で自分が打つべき手も確定します。

 

αβ法(アルファベータ法)

Mini-Max法の計算量を削減するための改良アルゴリズムです。

 

Mini-Max法は単純なゲーム戦略ですが、探索過程において無駄な探索も生じます。そのMini-Max法の無駄を省く方法αβ法と呼びます。αβ法では評価(スコア計算)する必要のないノードは探索対象から外してしまいます。

 

Mini-Max法の探索木を順に評価していき、スコアが最小となるものを選択する局面(つまり相手の局面)で、探索する必要のない自分の枝を切り落とす行為を「βカット」と呼びます。また同様に、スコアが最大となるものを選択する局面(つまり自分の局面)で、探索する必要のない相手の枝を切り落とす行為を「αカット」と呼びます。

 

Mini-Max法の探索木で、それまでに発見した自分の番で最も大きな評価値のことを「α値」と呼び、それまでに発見した相手の番で最も小さい評価値のことを「β値」と呼びます。

 

1.5 モンテカルロ法

モンテカルロ法は、ランダムシミュレーションを用いて最適な行動を選択するアルゴリズムです。不確実性のある環境での行動選択に有効です。

 

コンピュータの処理能力が飛躍的に向上したことで、囲碁や将棋ソフトはとても強くなっていますが、どんなに工夫をしても探索するノード数は膨大です。旧来の方式では、囲碁の路盤を9路盤まで減らし、組み合わせ数をチェスよりも少なくしてもコンピュータが人間に勝つことは難しいものでした。

 

これらの事から、探索しなければならない組み合わせの数が多いということだけでなく、ゲーム盤のスコア(コスト評価)に問題があるということが分かってきました。

 

このスコアがゲームの強さを決めていますが、典型的な旧来の方式では、過去の膨大な戦歴を元に局面のスコア(コスト評価)を人間が決めていました

 

そこで、モンテカルロ法という手法が用いられることになりました。モンテカルロ法では、ゲームがある局面まで進んだら、あらかじめ決められた方法でゲームの局面のスコアを評価する事を完全に放棄してしまいます。その代わり、コンピュータが2人の仮想的なプレイヤーを演じて、完全にランダムに手を指し続ける方法でゲームを終局させてしまいます。このようにゲームを終局させることをプレイアウトと呼びます。

 

ある局面からプレイアウトを複数回実行すると、どの方法が最も勝率が高いか計算が出来るため、ゲームのスコアを評価できるのです。とにかく数多く打って最良のものを選ぶという評価方法が優れていることが分かり、9×9の囲碁ではプロ棋士レベルになりました。

 

しかし、通常の19×19の囲碁においては、モンテカルロ法によるブルートフォース(力任せ)で押し切る方法では全く歯が立たない状況が続きました。AlphaGoはブルートフォース(力任せ)の戦略ではなく、ディープラーニングの技術を使って人間の思考方法をコンピュータで実現し、人間のプロ棋士に勝利したのです。

 

2. 知識表現

 

知識表現は、AIシステムが知識をどのように表現し、処理するかを指します。G検定では、以下のトピックについて理解が求められます。

2.1 人工無脳(知識なしでも知性があると感じる)

人工無脳とは、チャットボット、おしゃべりボットなどと呼ばれているコンピュータプログラムのことです。特定のルール・手順に従って会話を機械的に処理するだけであり、実際には会話の内容を理解しているわけではないため人工無脳と呼ばれています。

イライザ(ELIZA)

人工無脳の元祖は、ジョセフ・ワイゼンバウムによって開発されたイライザ(ELIZA)と呼ばれるプログラムです。このプログラムは、相手の発言をあらかじめ用意されたパターンと比較して、パターンに合致した発言があれば、そのパターンに応じた発言をオウム返しする仕組みになっています。

 

あたかも本物の人間と対話をしているような錯覚(イライザ効果)に陥り、イライザとの対話に夢中になるユーザーもいました。

 

2.2 知識ベースの構築とエキスパートシステム

ある専門分野の知識を取り込み、その分野のエキスパート(専門家)のように振る舞うプログラムのことをエキスパートシステムと呼びます。

マイシン(MYCIN)

初期のエキスパートシステムとして最も影響力が大きかったのが、1970年代にスタンフォード大学で開発されたマイシン(MYCIN)です。マイシンは血液中のバクテリアの診断支援をするルールベースのプログラムです。マイシンは人工知能型システムの実例として大きな注目を集めました。

 

if-then構文で記述される500のルールがあらかじめ用意されており、質問に答えていくことで、感染した細菌を特定してそれに合った抗生物質を処方することができるという、あたかも感染症の専門医のように振る舞うことができました。

 

DENDRAL

スタンフォード大学のエドワード・ファイゲンバウムは1960年代に未知の有機化合物を特定するDENDRALというエキスパートシステムを開発しました。実用指向のAIを推進し、1977年に実世界の問題に対する技術を重視した「知識工学」を提唱しました。

 

2.3 知識獲得のボトルネック(エキスパートシステムの限界)

知識表現における大きな課題は、知識獲得のボトルネックです。膨大な量の知識を効率的に獲得することは、容易ではありません。

 

知識ベースを構築するためには、専門家、ドキュメント、事例などから知識を獲得する必要があります。この中でも最大の知識源である人間の専門家からの知識獲得はとても困難でした。それは専門家が持つ知識の多くは経験的なものであり、知識が豊富であればあるほど暗黙的であるため、自発的に知識を述べてもらうことはほとんど不可能だったのです。

 

このような事情から、知識獲得のために知的なインタビューシステムなどの研究も行われました。さらに、知識ベースの構築において、獲得した知識の数が数千、数万と増えてくると、お互いに矛盾していたり、一貫していなかったりしたものが出てきて、知識データベースを保守することが困難になることが分かりました。

 

常識的な知識は暗黙的であり明文化されていないことが多く、このような知識をコンピュータで扱うのはとても難しかったのです。

 

2.4 意味ネットワーク

意味ネットワーク(semantic network)は、元々は認知心理学における長期記憶の構造モデルとして考案されました。現在では、人工知能においても重要な知識表現の方法の1つになっています。

 

意味ネットワークは、概念」をラベルの付いたノードで表し、概念間の関係ラベルの付いたリンク(矢印)で結んだネットワークとして表します。特に重要な関係として、「is-a」の関係と「part-of」の関係があります。

 

「is-a」の関係(「である」の関係)

「is-a」の関係(「である」の関係)は継承関係を表しており、例えば「動物は生物である」といったことを表現します。矢印が向いている側が上位概念で、矢印の始点が下位概念になります。下位概念は例外を指定しない限り、上位概念の属性をすべて引き継ぎます。

 

「part-of」の関係(「一部である」の関係)

「part-of」の関係(「一部である」の関係)は属性を表しており、例えば「目は頭部の一部である」ということを表します。

 

2.5 オントロジー(概念体系を記述するための方法論)

Cycプロジェクト

エキスパートシステムのような知識べースのシステムが能力を発揮するためには膨大な量の知識が必要になります。また、人間のように柔軟に知的能力を実現させるには広範囲に及ぶ常識が必要になることが広く認知されるようになりました。

 

この課題に挑戦するため、1984年にダグラス・レナートによって、全ての一般常識をコンピュータに取り込もうというCycプロジェクト(サイクプロジェクト)がスタートしました。このプロジェクトでは、「すべての木は植物です」「パリはフランスの首都です」といった一般常識をひたすら入力していくのですが、驚くべきことに、このプロジェクトは現在も継続中です。

"すべての木は植物です"

(#$genls #$Tree-ThePlant #$Plant)

 

"パリはフランスの首都です"

(#$capitalCity #$France #$Paris)

 

オントロジー

知識を記述したり共有したりすることが難しいと分かってくると、知識を体系化する方法論が研究されるようになりました。それがオントロジーの研究に繋がります。オントロジー(ontology)は、エキスパートシステムのための知識ベースの開発と保守にコストがかかるという問題に端を発しています。

 

オントロジーは、本来は哲学用語で存在論(存在に関する体系的理論)という意味ですが、人工知能の用語としては、トム・グルーパーによる「概念化の明示的な仕様」という定義が広く受け入れられています。難しい表現ですが、オントロジーの目的は、知識の共有と活用なので、扱う知識や情報の意味構造をきちんと定義して扱うのは極めて自然なのです。

 

コンピュータで「知識」を扱おうとする場合、その「知識」を書く人が好き勝手に記述してしまうと、どれとどれが同じ意味(あるいは違う意味)を表しているのか分からなくなってしまいます。このため、知識を記述する時に用いる「言葉(語彙)」や「その意味」、「それらの関係性」を、他の人とも共有できるように、明確な約束事(仕様)として定義しておくのです。

 

オントロジーが用意されていれば、そこで定義された約束事に従って知識が記述されるので、ひとつの「知識」を誰が見ても同じ意味で理解できるように定義しておくということですね。ネットワークを繋げるときに使用するプロトコルの考え方を思い浮かべれば理解しやすいかもしれません。

 

また、オントロジーを構築しておけば、そこで定義されている関係性を利用して、似た意味の言葉を一緒に検索することもできます。

 

2.6 概念間の関係(is-aとpart-ofの関係)

オントロジーにおいて、概念間の関係を表す「is-a」(である)の関係と「part-of」(一部である)の関係は特に重要です。

「is-a」の関係と推移律

「is-a」の関係(「である」の関係)は、上位概念下位概念の関係を表していますが、そこには推移律が成り立ちます。推移律とは、AとBに関係が成り立っており、BとCに関係が成り立っていれば、AとCにも自動的に関係が成り立つというものです。

 

例えば、A>Bであり、B>Cであれば、A>Cという関係が自動的に成立します。しかし、ジャンケンの場合には、推移律は成り立ちません。関係の種類によって推移律が成立するものと成立しないものがあるのです。

 

「part-of」の関係と推移律

「part-of」の関係(「一部である」の関係)は全体と部分の関係を表しています。

 

例として、「日本 part-of アジア」という関係が成立し、「東京 part-of 日本」という関係が成立していれば、「東京 part-of アジア」という関係が成立するので、「part-of」の関係でも推移律が成り立ちそうに見えます。しかし実際には、「part-of」の関係の場合は推移律が成立するとは限りません。この認識は極めて重要です。

 

例として、「指 part-of 太郎」の関係が成立して、「太郎 part-of 野球部」の関係が成立していても、「指 part-of 野球部」という関係は成立しません。つまり、「part-of」の関係の場合には、推移律が成立するものと成立しないものがあるのです。

 

このように「part-of」の関係には色々な種類の関係があります。「part-of」の関係だけでも、最低5種類の関係があることが分かっています。私たちはほとんど意識せずに楽々とこれらの概念を操作していますが、コンピュータにこれを理解させるのは大変難しいのです。

 

2.7 オントロジーの構築

オントロジーの研究が進み、知識を記述することの難しさが明らかになってくると次の2つの流れが生まれました。

  • 対象世界の知識をどのように記述するべきかを哲学的にしっかり考えて行うもの
  • 効率を重視し、とにかくコンピュータにデータを読み込ませて出来る限り自動的に行うもの

それぞれ、ヘビーウェイトオントロジー(重量オントロジー)とライトウェイトオントロジー(軽量オントロジー)という2つの分類にほぼ対応しています。

 

ヘビーウェイトオントロジー

ヘビーウェイトオントロジーの場合、その構成要素や意味的関係の正当性について哲学的な考察が必要なため、どうしても人間が関わることになりがちで、時間とコストがかかります。一般常識を手動で全て取り込もうとするCycプロジェクトが1984年の開始から未だに続いているのもその一例です。

 

ライトウェイトオントロジー

ライトウェイトオントロジーの場合、完全に正しくなくても使えるものであればいいという考え方から、その構成要素の分類関係の正当性については深い考察は行わない傾向があります。

 

例えば、Webデータを解析して知識を取り出すウェブマイニングやビッグデータを解析して有用な知識を取り出すデータマイニングで利用されています。

 

こうしたオントロジーの研究は、セマンティックWeb(Webサイトが持つ意味をコンピュータに理解させてコンピュータ同士で処理を行わせる技術)やLOD(Linked Open Data:コンピュータ処理に適したデータを公開・共有するための技術)などの研究として展開されています。

 

Xでフォローしよう

おすすめの記事