序

インターネット上で公開される情報量の増加に伴い、テキスト等のデータを効率的に分類する技術が重要となってきている。しかし、これらのデータは一般的に極めて高次元であるため、元データをそのまま扱うと、精度の高い分類器を構築することが困難、計算コストが膨大、モデルの解釈が困難などといった問題が生じる。したがって、膨大な属性の中から、分類に寄与する属性（本研究では有効分類属性と呼ぶ）を属性選択・抽出手法によって正確に特定し、分類に適したデータ表現に次元を圧縮させることが肝要となる。これまで提案されてきた次元圧縮手法は比較的少数の属性が想定されてきたが、テキスト分類等への応用の際には属性数が数万以上にも上るため、従来手法では十分に対処し切れない。したがって、高次元データから有効分類属性を効率的に特定する手法の開発が望まれている。

近年、サポートベクターマシン（SVM）と呼ばれる分類アルゴリズムが大変注目を集めている。この手法は構造リスク最小化という原理に基づいているため、高次元データに対しても過学習を起こすことなく高い汎化能力を示すことが報告されている。最近になって同手法を属性選択に用いることが提案されたが、同手法の高次元データへの有効性は属性選択においても発揮されると期待される。そこで、本研究では、高次元データからの有効分類属性の特定に関して、SVMを用いた属性選択法の有効性を示すことを目的とする。

SVM属性選択法

SVMでは「マージン」という量を定義し、マージンを最大化する線形分類器を求める。この問題は次の凸二次計画問題に帰着される。目的関数：〓最大化　(1)制約条件：〓

ただし、ここで{x1,…,xm}∈Rdは訓練データ、{y1,…,ym}∈{-1,1}はクラスラベル、αi(≧0)はラグランジュ乗数、Cは誤分類とマージンのトレードオフを決定するソフトマージンパラメータである。上の最適化問題を解くことで、判別関数は下記のように求まる。ここで、多くのαiは0となり、訓練データの一部のみが判別境界に寄与する。

最近になって、判別関数の重みWを用いた属性選択法が提案された。この手法は、属性の重みWk2がほぼ0である属性は判別境界へほとんど影響を及ぼさないと考えられることから、Wk2の大きさを属性選択の指標として用いるものである。既往の研究で同手法の高次元データへの有効性が報告されているが、次に挙げる点に関しては未だ十分な知見が得られていない。まず第1に、同手法はテキスト分類における従来手法と異なり多変量手法であるので属性間の関連も考慮されるが、その効果については十分な解析がなされていない。第2に、分類精度を低下させることなく属性数をどの程度まで削減できるかについての決定手法が確立されていない。第3点として、ソフトマージンパラメータCは属性選択の効果に大きな影響を及ぼすと考えられるが、既往の研究では十分に大きなCが用いられ、その影響については解析がなされていない。第4点として、同手法はこれまで元の属性のみに適用されてきており、抽出属性への適用例は報告されていない。本研究では以上の点に着目し分析を行った。

テキスト分類問題における次元圧縮

SVM属性選択法をテキスト分類において標準的に用いられているReuters-21578、20 Newsgroupsデータセットに適用した。分類精度の評価には、適合率と再現率の調和平均で定義されるF1値を用いた。

まず、SVM属性選択法の多変量性の効果について分析を行った。比較対象としたのは、テキスト分類において広く用いられ、その性能の高さが実証されている情報利得及びχ2指標である。属性数の減少に伴い、他の二手法は若干F1値が変動したのに対し、本手法はF1値が極めて安定であった。さらに、分類精度とWk2の累積寄与率との間に強い相関が見られた。そこで、本研究ではWk2の累積寄与率を不要属性数の推定に用いることを提案する。累積寄与率の閾値を設定し、各クラス毎に閾値に達する属性数を求め、F1値の閾値依存性を調べた。全クラスに対して計算を行った結果、本手法によるF1値は他の二手法と比べ、平均は高く、標準偏差は小さいという結果が得られ、本手法はクラスに依らず頑健に不要属性を除去できることが示された。

これは、他の二手法が属性を個々に評価しているために組み合わさって初めて分類に寄与する属性を除去してしまう危険性があるのに対し、本手法は全属性の関連を考慮した上で属性を評価していることに起因すると考えられる。また、Wk2の累積寄与率が不要属性数の推定に有効な指標であることが示された。

次に、Cが属性選択に与える影響について分析を行った。訓練誤差が小さくなるようにCを大きくした場合、汎化誤差が小さくなるように10-fold cross-validationで決定したCを用いた場合、Cを十分に小さくした場合の3ケースに対して比較を行った。その結果、属性数が多い領域では大きなCが、属性数が少ない領域には小さなCが適していることが明らかになった。

テキスト分類においては、特異値分解に基づいて属性抽出を行い次元圧縮すると、単語間の関連が考慮され分類精度が向上することが報告されている（Latent Semantic Indexing, LSI）。しかし、この手法によって抽出された属性の重要度は分類性ではなく分散で評価されるため、必ずしも分類に適したデータ表現になっている保証が無い。そこで本研究では、より分類に適したコンパクトなLSI部分空間を求めるためにSVM属性選択法を適用した。抽出属性 の分類性は次式で評価される。〓(3)属性抽出において、クラス内に複数のクラスタが存在する場合、分類性とデータ表現性の両方を考慮する必要性が指摘されている。そこで、本研究では(3)式の値と分散の調和平均を属性選択指標として用いた。その結果、本手法で特定されたLSI部分空間は通常のLSIと同様に分類精度の向上が見られたが、最大の分類精度を実現するのに必要な属性数は通常のLSIよりも少ないことが分かった。大規模データにLSIを適用する際には、訓練・テストにかかる計算コストが大きな問題となるが、本手法を用いることで計算量の軽減が可能となる。

情報フィルタリングにおけるユーザの興味の学習

ウェブページの情報フィルタリングにSVM属性選択法を適用した。ユーザが検索エンジンを用いて研究テーマに関する検索を行い、各自の興味の有る/無しを評価したウェブページを分析に用いた。まず、SVM属性選択法で不要属性を除去した上で、LSIによって属性抽出を行い、その中からSVM属性選択法を用いて有効分類属性を特定した。その結果、比較的少数の属性数で全属性とほぼ同等の分類精度が実現できるという結果が得られた。そして、抽出された属性の中でどの属性が寄与しているかをユーザ自身に評価してもらった結果、SVM属性選択法で上位に評価された属性と大きな相違は無かった。したがって、本手法はユーザの興味を表す因子を特定するのに有効である可能性が示唆された。

非線形属性への拡張

データが線形には分類されない場合には非線形な有効分類属性を特定することが重要となる。そこで、上記のSVM属性選択法を非線形に抽出された属性に拡張した。

SVMは基本的には線形分類器を学習するが、目的関数(1)式、判別関数(2)式共に訓練データには内積形でしか依存しないという性質を利用することで、非線形の場合にも容易に拡張することができる。適切な非線形関数φを用いて元の空間よりも高次元な空間に写像すれば線形分離性を高めることができるので、写像した先の空間で線形SVMを学習できる。そこで、 を満たすカーネル関数を用意し、式(1)、(2)の内積形をこの関数で置換して解けば元の空間で非線形分類器を求めることができる。

Latent Semantic Kernel(LSK)は、カーネルを用いて非線形な属性抽出を行う手法である。具体的には、カーネル行列に対して固有値分解を行う。K=D・A・Dτ

ここで、Dは固有ベクトルからなる行列、Λは対角成分が固有値である対角行列である。LSKもLSIと同様に属性の重要度は分類性ではなく分散で評価されるので、本研究ではSVM属性選択法をLSKに適用することを提案する。各属性に対応する固有値をλk、固有ベクトルをdkとすると、非線形属性Wk2の分類性の評価指標は次式で与えられる。〓属性選択指標としては、LSIと同様に分類性と分散の調和平均を用いた。非線形な分類器が必要であることが知られているUSPSデータセットに本手法を適用した結果、本手法は通常のLSKよりも少数の属性で高い分類精度が実現できることが示され、本手法は線形属性のみならず非線形属性に対しても有効であることが分かった。

結論

高次元データからの有効分類属性の特定に関し、SVM属性選択法の有効性を明らかにした。特に、同手法の多変量性に由来するクラスに依存しない頑健性を実証し、不要属性数を決定する指標を提案した。また、属性選択の効果はソフトマージンパラメータに大きく依存することを示した。さらに、同手法が元属性のみならず、線形および非線形に抽出された属性にも有効であることを示した。そして、同手法を情報フィルタリングに適用し、ユーザの興味を表す因子を特定できる可能性が示唆された。

本論文は、テキスト分類などの高次元データの分類問題に対し、サポートベクターマシンを用いた属性選択法に着目し、同手法の高次元データへの有効性について論じたものである。本論文は、全7章で構成されている。

第1章では、研究の背景が述べられている。近年のデータ量の増加とともにデータを効率的に分類する技術が重要となってきているが、計算コスト・分類精度・モデルの解釈のし易さといった観点から、属性選択・抽出などの次元圧縮を行い、分類に寄与する属性（有効分類属性）を特定することが望ましい。従来の次元圧縮手法は比較的少数の属性数を想定していたが、それらの手法は現在扱われるような数万以上にも上る属性数には十分に対処しきれない。そこで、高次元データに対する効率的な次元圧縮手法が必要であるという本研究の動機付けを行っている。

第2章では、テキスト分類について概説している。テキスト分類で用いられる、ベクトル空間モデル、前処理過程、アルゴリズムの分類精度の評価指標について説明している。そして、テキスト分類で従来用いられてきた次元圧縮手法についてまとめ、それらの問題点を指摘している。

第3章では、本手法で着目する、サポートベクターマシンの原理、およびサポートベクターマシンを用いた属性選択法についての説明を行っている。同手法の利点、既往の研究で未だ十分な知見が得られていない課題点についてまとめている。

第4章では、同手法を標準的なテキスト分類データセットに適用している。属性選択に関して従来手法との比較を行い、同手法が多変量性のために、従来手法よりもクラスに依らず頑健に不要属性を除去できることを示し、不要属性数を推定する指標を提案している。さらに、ソフトマージンパラメータが同手法に及ぼす影響についての分析を行っている。ソフトマージンパラメータの設定値によって属性選択の効果が大きく異なることを明らかにし、同パラメータが大きい場合には不要属性の特定に適しており、小さい場合には少数の有効分類属性の特定に適していることを示している。その上で、両方のケースの利点を併せ持つ属性選択指標を提案している。そして、本手法をLatent Semantic Indexing (LSI)と呼ばれる属性抽出手法に適用することで、通常のLSIよりも少数の属性数で分類精度の向上を実現できることを示している。

第5章では、本手法をウェブページの情報フィルタリングに適用した結果を報告している。ユーザがウェブページを閲覧し各自の興味の有る／無しを評価した値を元に、本手法を用いてユーザのウェブページに対する興味を表す因子の特定を試みている。その結果、特定された因子とユーザ自身による自分の興味の認識との間に大きな相違が無いことが示され、ユーザの潜在的な興味を表す因子が特定できる可能性が示唆されている。

第6章では、同手法を非線形属性に拡張を行っている。手書き数字認識の分類問題に適用した結果、同手法を用いて非線形な有効分類属性を特定することにより、比較的少数で高い分類精度を実現できることを示している。したがって、同手法が線形属性のみならず非線形属性に対しても有効であることを示している。

第7章は結論であり、本研究で得られた知見がまとめられている。

以上のように、本論文は、サポートベクターマシンと呼ばれる多変量手法が、高次元データからの有効分類属性の特定に有効であることを示した研究であり、データマイニング技術のみならず、データ工学全般への発展に寄与するところが少なくない。よって、本論文は博士（工学）の学位請求論文として合格と認められる。