氏名　鈴木　泉
学位の種類　博士（工学）
学位記番号　博甲第524号
学位授与の日付　平成21年12月31日
学位論文題目　P-NORM OPTIMIZATION OF AGGREGATION OF EVALUATION FUNCTIONS IN SEARCHING SYSTEMS　（探索システムにおける評価関数の統合問題のP-ノルム演算による最適化）
論文審査委員
　主査　教授　三上　喜貴
　副査　教授　大里　有生
　副査　教授　福村　好美
　副査　教授　山田　耕一
　副査　准教授　湯川　高志
　副査　国立情報学研究所教授　相澤　彰子

• 論文目次
• 論文要旨
• 論文審査の結果の要旨

［平成21（2009）年度博士論文題名一覧］ ［博士論文題名一覧］に戻る．

1　INTRODUCTION
　1.1　Background　p.1
　1.2　Applications　p.2
2　THEORETICAL FOUNDATION
　2.1　Aggregation problem of evaluation functions　p.5
　2.2　Fuzzy Set　p.6
　2.3　Basic operations on fuzzy sets　p.6
　2.4　T-Norms　p.7
　2.5　Average operators　p.11
　2.6　Weighted average operators　p.13
　2.7　Order of T-operators and average operators　p.15
　2.8　Which p-norm operator should be used?　p.15
3　FUZZY IDENTIFICATION OF THE USER REQUIREMENT
　3.1　Introduction　p.18
　3.2　Problem description
　3.2.1　Machine system　p.19
　3.2.2　Purpose　p.20
　3.2.3　Problem description as an aggregation problem　p.21
　3.3　Algorighm
　3.3.1　Process　p.22
　3.3.2　Use of p-average operators　p.23
　3.4　Experiments　p.24
　3.5　P-norm optimization
　3.5.1　Identification of the user requirement　p.28
　3.5.2　Presented environments　p.29
　3.5.3　Discussion　p.29
4　MONOTONICALLY INCREASING BINARY SIMILARITY AND ITS APPLICATION TO AUTOMATIC DOCUMENT ACQUISITION OF A CATEGORY
　4.1　Introduction
　4.1.1　Background　p.32
　4.1.2　Review of text classification　p.33
　4.2　Formation of automatic document acquisition　p.39
　4.3　Monotonically increasing similarity
　4.3.1　Definition　p.39
　4.3.2　Application to document acquisition　p.40
　4.3.3　Problem description as an aggregation problem　p.42
　4.4　Experiments　p.46
　4.5　Discussion　p.49
5　A DOCUMENT RE-RANKING TECHNIQUE FOR WEB SEARCHING
　5.1　Introduction
　5.1.1.　Background　p.50
　5.1.2.　Search engines　p.53
　5.1.3.　Search assist techniques　p.55
　5.2　Problem description　p.59
　5.3　Re-ranking process
　5.3.1.　Re-ranling search score　p.60
　5.3.2.　Proposed technique　p.60
　5.3.3.　Problem descriotion as an aggregation problem　p.62
　5.4　Experiments
　5.4.1.　Noise and search score　p.63
　5.4.2.　Compaative human model　p.64
　5.4.3.　Data collection　p.68
　5.4.4.　Results　p.72
　5.5　Discussion　p.73
6　DISCUSSION
　6.1.　Factors common to each application　p.75
　6.2.　Weighted p-operator aggregation　p.76
7　CONCLUSION
　7.1.　Guidelines for the use of logical operators　p.79
　7.2.　Application for machine translations　p.79
　7.3.　Search engines in the future　p.81
REFERENCES　p.83
APPENDICES

　情報検索およびマン・マシンシステムにおいて、ユーザ要求を探索するシステムを3例提案する。それぞれの応用例には、（1） 複数の評価関数の評価値をt-ノルム演算によって統合する、および、（2） 統合された1個の評価関数を独立変数とする目的関数を最適化する、という共通の構造が存在する。本論文では、評価関数の統合方法として、幅広いt-ノルム演算をカバーし、パラメトリックな解析が可能なp-ノルム演算に対象を絞った。その上で、目的関数を最適化するpの値を決定するタイプの探索問題として3個のシステムを再構成した（第2章）。具体的な事例を用いて実験した結果、いずれのシステムにおいても、pの値を無限大に設定した場合が最適であるという結果を得た。

　第1のシステムは、ユーザが要求するマシン環境を環境全体の集合上のファジィ集合として探索し特定する（第3章）。その際、ユーザへの環境の提示とそれに対するユーザからの応答を繰り返す。1回の提示、応答によって、全体集合の一部についてユーザーの要求であるファジィ集合が特定される。ここで、ファジィ集合のメンバーシップ値に重みを付加することによって、集合の一部であることを定義した。最後に、現時点までに得られた部分的なファジィ集合を重み付きp-ノルム平均演算によって統合し、1個のファジィ集合を作成する。目的関数として、提示する環境は現時点までに得られたユーザの要求により従うという要請を指標化した。

　具体的な事例としてパソコンにおけるマウスの移動速度の設定を挙げ、実験を行った。pの値は、最終的にユーザ要求をファジィ集合化する際にはp = 1とするが、提示する環境を決定するアルゴリズムにおいては、pの値を無限大に設定した場合が最適であるという結果を得た。これは、現時点までに特定されているユーザの要求であるファジィ集合を、重み付きp-ノルム平均演算の中で定義され得る最大のものとして与えることに相当する。

　第2のシステムは、ユーザが指示する文書を初期の訓練データとして、これに最も類似した文書を訓練データに追加するプロセスを繰り返し、初期の訓練データと同一カテゴリに含まれる文書を収集するものである（第4章）。文書間の類似度が、文書の追加に関して単調増加するという性質があると、上記のプロセスの終了要件が容易に求められることを示した。また実際に、特定の言語の文書を収集する具体例を挙げて検証実験を行った。次に、文書間の類似度は、一般的な手法である線形類似度を用いた。すなわち、（1） 文書中で使用されるタームを要素として文書をベクトル化し、（2） ベクトルの各要素をベクトルのノルムで割ることによって正規化し、（3） ベクトルの内積を求める。上記（2）におけるノルム化が評価関数の統合に相当する。また目的関数は、類似度が文書の追加に関して単調増加するという、制約条件として与えられる。この制約条件を満たすためには、pの値を無限大に設定する必要があることが証明された。

　第3のシステムは、インターネット検索において、ユーザ・クエリによる検索結果を再ランク化するアルゴリズムである（第5章）。ユーザ・クエリから、重要度の低いタームの幾つかを除外することによって、ユーザ・クエリに類似したクエリーを複数個作成する。これらのクエリによって検索を実行し、複数個の検索結果を得る。個々の検索結果は、検索スコアをメンバーシップ値とするファジィ集合と考える。これらのファジィ集合を統合して1つの検索結果を作成することが、評価関数の統合に相当する。目的関数として、ユーザの要求するページのうち最も上位ランクのページが、より上位ランクとなることを指標化する。18個の検索事例で実験したところ、pの値を無限大に設定すること、つまり、検索結果のファジィ集合を最大値演算によって統合する場合が最適であるとの結論を得た。

　最後に、pの値を無限大に設定した場合が最適となった理由を考察した（第6章）。第1のシステムにおいては、少なくとも学習の初期段階ほど、その時点までに特定されているユーザの要求を最大のもの、つまり、環境全体の集合上でより広く定義したほうが、探索方法としては効率的であると考えられる。また、第2、第3のシステムに共通して存在する要因として、統合すべきデータに重みが内在している可能性に言及した。これら第2、第3のシステムにおいては、これらの重みが正確に求められないために重みを1として統合している。このことが、重みの与え方によらない最大値演算が優位となった理由の1つと考えられる。

　本論文で明らかにされた上記の知見は、インターネット検索、文書の自動判別など情報処理技術における評価値統合手法に対する設計指針となることが期待される。

　本論文は「P-NORM OPTIMIZATION OF AGGREGATION OF EVALUATION FUNCTIONS IN SEARCHING SYSTEMS（探索システムにおける評価関数の統合問題のp-ノルム演算による最適化）」と題し、6章より構成されている。

　第1章は本研究の主題及び論文で用いられる基本的な概念であるt-ノルム、p－ノルムの定義と解説に当てられる。本研究の主題は探索システムにおける評価関数の統合問題である。この問題は情報処理システム、特にマン・マシンシステムや情報検索システムにおいて中心的な問題をなしており、多くの場合、複数の評価関数による評価値を統合した結果により最終的な探索結果が導かれる。統合演算は一般的にはt-ノルム演算として扱うことができるが、このうち、幅広いt-ノルム演算をカバーし、しかもパラメトリックな解析が可能なp-ノルム演算について解説される。

　第2章は、本論文における分析の枠組みが、探索の対象である有限集合、その上で定義される複数の評価関数、これを統合する目的関数、P－ノルム演算による評価関数の統合、という各要素を用いて説明される。

　第3章から第5章までの各章は、代表的な探索問題として三つの探索問題が提示される。ユーザが要求するマシン環境を環境全体の集合上のファジー集合として探索し、特定する問題（第3章）、ある基準文書が与えられたときにこれと同じカテゴリーに属する文書を探索する問題（第4章）、ある検索クエリが与えられたときにこれに基づいて目的文書を探索する問題（第5章）という三つの探索問題について、各々についての最適探索アルゴリズムが提案され、仮想例を用いたシミュレーション結果や、提案方法が最適であるとの証明などが与えられる。

　第6章は結論を要約した部分であり、三つの探索問題を複数の評価関数の統合問題として再構成し、かつ、パラメトリックな解析が可能なp－ノルム演算を用いて統合することにより、最適化のための戦略を解析的に論じた結果、いずれもpの値を無限大としたときに最適となるという知見を得たことが述べられる。また、評価関数の統合結果がこのような挙動を示す原因についての考察が行われている。

　第7章では、上記の知見の工学的応用や今後の検討課題が述べられる。

　本論文の明らかにした知見はウェブ検索や文書の自動判別など情報処理技術への広い応用を有するものであり、よって、本論文は工学上及び工業上貢献するところが大きく、博士（工学）の学位論文として十分な価値を有するものと認める。