本論文は,大きく第I部と第II部から構成される.第I部は仮説推論の高速解法とその周辺であり,大量の知識が与えられたときにどのように高速に推論処理を行うかを対象とする.第II部では,文書からのキーワード抽出を扱う.ここで開発したいくつかのキーワード抽出手法は,文書からどのように知識を取り出せばよいのかという問題の基礎的な要素技術になると考えている.以下,順を追って説明する.

　推論の枠組みのひとつとして,観測から原因を予測する仮説推論がある.仮説推論は,真か偽か不明な事柄をとりあえず真と考えて推論をすすめ、矛盾なくゴール(観測事象)を導くことができれば立てた仮説は正しかったと考える推論形式である。ゴールを証明する仮説の組は複数ある場合もあるため、コストに基づく仮説推論では各仮説に重みを付与し、その重み和を最小とする解(仮説の組)を最も望ましいものとする。

　コストに基づく仮説推論は,NP完全またはNP困難である.したがって、コストに基づく仮説推論の最適解を見つけるには、最悪ケースで問題規模に対して指数オーダの推論時間がかかる。そこで、コストが最小に近い準最適解を、平均として多項式オーダの推論時間で求める研究が行われてきた。仮説推論問題を,最適化問題に変換する方法は今までにいくつか提案されてきたが,それらは最も基本的な次の2つの置き換え法にまとめられる.

　次のような節があるとする.

　p1V¬p2V¬p3　(1)

この節は3つのリテラルのうちどれかが真になればよいという要請を表わすので、真=1,偽=0を表すとすれば,以下の不等式制約と等価である.

このような線形不等式制約をへの置換を置換Lと呼ぶことにする.目的関数を

とし,置換Lによる制約に基づく問題を問題Lと呼ぶ.(ただし,wiは仮説iのコスト.)

　一方,式(1)は,

　¬(¬p1∧p2∧p3)

と変形できるので、¬p1∧p2∧p3)が偽となればよい.したがって、以下のように等式制約でも表現することができる.

　(1−xp1)xp2xp3=0　(2)

これを置換NLとよび,この制約に基づくコスト最小化問題を問題NLとよぶ.

　これらの置き換え法を利用して仮説推論の準最適解を得るSL法を開発した.SL法は,まず問題Lを解くことで実数領域の最適解を得た後,問題NLをペナルティ法で解くことで,実数最適解近傍の0-1解を得ることができる.ただし,探索が局所解に陥ることが発生するので,その際には非充足な節を矯正するように変数の値を変え,その値で固定するという処理を行う.つまり,非線形関数の降下(Slide-down)と持ち上げ(Lift-up)を交互に行う(図1).この方法では,仮説数nに対し,n1.8の多項式オーダの探索時間で準最適解を得ることができた.

　また,置換Lと置換NLという性質の異なる2つの制約を同時に扱う手法も開発した.拡張ラグランジュ法という枠組みを用い,複数の種類の異なる制約を扱う.探索の初期フェーズでは置換Lによる制約を利用し,コストの低い領域を探索する.充足していない節があれば,置換NLによる制約を順次付加していくことで,高速に質の高い解を探索することができる(図2).SL法よりもさらに高速にコストの低い解を探索することができた.

　さて,アルゴリズムの性能を正しく評価するには、用いる問題に対する考察が不可欠である.そこで,同じタイプの問題のパラメータを変えることで,問題の難しさがどのように変化するかを考察した.同じタイプの問題でも,制約を徐々に厳しくしていくと,置換Lの有効性がある領域で急激に悪くなることを明らかにした.また,問題を解く前に,どの程度難しい問題であるかを,解の数を見積もることで計算する方法についてもいくつか考案した.

　仮説推論は,人間がある知識を記述し,計算機が推論して解を提示するという仕組みであるが,これをひとつのシステムと考えたときには,どのように簡単に知識を表現すればよいか,どのように結果を分かりやすく提示すればよいかという視点も重要である.仮説推論の目的関数が複数の場合や,重要な制約を解と同時に提示するといった,仮説推論をより使いやすくする拡張についても考察した.

　第II部では,主に文書からのキーワード抽出というテーマを扱う.近年では大量の電子文書が入手可能であり,テキストマイニングの研究もさかんである.大量の文書から知識を抽出することができれば,推論の枠組みを十分に生かすことができるだろう.

　まず,ひとつの文書内における語の共起を考える.同じ文内に同時に出現した場合に1回共起し,頻出語と各単語の共起回数を数える.仮に、語ωが頻出語g∈Gと全く独立に生起するなら、語ωと語g∈Gが共起する確率は頻出語単独での生起確率と同様の分布になるはずである.一方、語ωと頻出語g∈Gの間に何らかの意味的なつながりがあれば、この確率は偏ることになる."achieve"や"case"のような一般的な語は偏りが少ないが(図3),"non-linear function"や"hypothesis"のような文書の主題と特に関連した語は偏りが大きい(図4).したがって,この偏りが大きい語をキーワードとして取り出す.ここではX2検定を用いて偏りを計る.頻出語単独での生起確率を理論確率pg(g∈G)とし、語ωと頻出語群Gの共起の総数をnω、語ωと語g∈Gの共起頻度をfreq(ω,g)とすると、統計量X2は以下の式で与えられる.

X2(ω)の大きな語ωが理論確率分布からのずれが大きな語である.この手法により,単一文書だけから従来手法を上回る性能でキーワードを取り出すことができた.

　共起関係をもとに,単語の共起グラフを作ることもできる(図5).各ノードは語を表し,エッジは単語間の共起を表す.このグラフは,近い概念の語同士はたがいに結ばれクラスタになっており,そのクラスタ同士が緩くつながっている"Small World"の特徴を備えたグラフとなっている.Small Worldとは,ノードがクラスタ化されているにも関わらず,任意の2点間のパス長が短いグラフである.ひとつの文書から得られた語の共起グラフもこのような構造をしており,Small World構造に対する貢献の高い語をキーワードとして抽出する.つまり,ひとつの語を取り除くことで,パス長が大きく減少するような語をキーワードとして取り出す.この手法では,重要な語と同時に一般的な語もキーワードとして抽出してしまうが,idfの指標を同時に用いることにより,よい性能を得ることができた.

　最後に,全体のまとめと今後の人工知能の方向性について述べ,結論とする.

図1:探索の様子

図2:制約プロセッサNLを加えていく2種の戦略

図3:語achieve, caseの頻出語との共起の確率分布

図4:語"non-linear function", "hypothesis"の頻出語との共起の確率分布

図5:ある論文の語の共起グラフ

　本論文は「仮説推論法と文書主題抽出法に関する研究」と題し,人工知能領域の研究にについて,第I部「仮説推論法」(第2章〜第7章),第II部「文書主題抽出法(第8章〜第11章)のそれぞれで,著者が考案した新手法について記している.

　第1章「序論」では,本論文の研究は大量の知識をいかに高速に操作し推論するかと,その大量の知識をいかに獲得するかに関する,仮説推論の高速化の研究と,自然言語文からのキーワード抽出に関する研究から成っていることを述べている.

　第I部・第2章「人工知能と仮説推論」では,人工知能研究の概観と,仮説として真偽の不明な事柄を扱う仮説推論(アブダクションの一形式でもある)について述べている.特に,仮説推論が他の知識表現とどのような関係にあるか,そして,推論速度が十分でない課題に対し,従来どのような高速推論法が提案されてきたかをまとめている.

　第3章「仮説推論の最適化問題に置き換え」では,有用性が高いコストに基づく仮説推論(与えられたゴールを充たすのに必要な重みの和が最小となる無矛盾な仮説の部分集合を探す形式の推論)を対象とする時の,高速化の有力なアプローチを考察する上での基礎事項について論じている.すなわち,知識を線形不等式制約へ変換し線形計画法により最適化問題を解くアプローチ,等式制約に変換して制約付き非線形最適化問題を解くアプローチの二つが基礎となることを述べ,それぞれの性質を明確化している.

　第4章は「SL法:線形計画法と非線形計画法による高速推論法」であり,コストに基づく仮説推論を線形計画法に変換し,探索の初期点を得た後,非線形関数の勾配法によって解を探索する手法(SL法)を考案,提示している.簡素な動作原理でありながら,非常によい準最適解を高速に見出すことができることを示している.

　第5章は「仮説推論の問題例に対する分析」である.これまで仮説推論問題の性質や分析は十分行われてこなかったが,本章では,問題を解く前に実行可能解が存在するかどうかを見積る方法と,問題制約の付加による(準)最適解を求める難易度の変化について論じている.

　第6章「2種の置き換え法の協調による推論法」では,3章で考察した2種の置き換えによる解法のそれぞれの特徴を活かし,拡張ラグランジュ法を用いて2種の置き換え方を効果的に協調させることで,柔軟で高速なアルゴリズムを構成している.第4章のSL法と比較すると,必ずしも大幅な高速化が実現されるという訳ではないが,深い考察に基づく見通しの良い構成の手法となっている.

　第7章「システムとしての仮説推論」では,使いやすい仮説推論のためには,どのような拡張が必要かについて考察している.

　第8章からは第II部であり,「自然言語からの知識獲得」と題し,まず近年の,大量の電子的な文書から効果的に知識を抽出するテキストマイニング,Webマイニング,そして以下の研究に関係するテキストからキーワード抽出の諸手法を概観している.

　第9章「語の共起情報を用いたキーワード抽出」では,自然言語のテキストにおける語の共起を統計的に処理し,共起の偏りをカイ2乗検定により検出する新しいキーワード抽出法を考案,提示している.これまで主流であった対象文書以外の大量の文書データも必要とするTF*IDFを用いる方法と比べると,この方法は単独の文書だけから高い性能でキーワードを抽出でき,かつ大変簡素な構成となっている特長がある.

　第10章「Small World構造に基づくキーワード抽出」では,前章とは別の観点からの新しいキーワード抽出法を考案,提示している.その着眼点は,語の共起は全体としてグラフを形成し,このグラフはSmall Worldと呼ばれる特徴を持つことであり,このSmall Worldの構造上重要な位置にある語をキーワードとして抽出する方法である.

　第11章は「仮説推論を利用した複数文書要約」と題し,複数文書の語の共起グラフを組合せて大きな語の共起グラフを構成し,このグラフを利用した複数文書の要約技術を考案し,提示している.この辺被覆問題を解く際に,本論文第I部の高速仮説推論法を利用している.

　以上を要するに,本論文は大量の知識をいかに高速に操作し推論するかと,その大量の知識をいかに獲得するかという観点から,人工知能における高速仮説推論の2種の新手法と,文書からのキーワード抽出の2種の新手法を創案している.いずれも対象問題を深く考察し,新手法を産み出す基盤的原理の解明を図り,それに基づき簡素で明解な構成をもつ新手法を与え,それらの性能を実験を通じて実証している.原理的新規性と共に実用的有用性も高いと考えられ,電子情報工学上貢献するところが少なくない.

　よって本論文は博士(工学)の学位請求論文として合格と認められる.