Header image  
ウェアラブル・ユビキタス・エンタテインメント
の研究を推進しています
 
   最終更新日 2014年10月8日
 
 
 
 


 
情報フィルタリングの数学的基盤の確立

  1. 情報の洪水に対処する
  2. フィルタリングの処理方法
  3. フィルタリング関数
  4. 応用システム
  5. おわりに
  6. 参考文献
   

1 情報の洪水に対処する

デジタル放送の開始や携帯電話への情報配信サービスの開始により,我々が日常生活で受け取る情報の量は飛躍的に増大しています.たくさんの情報は確かに我々の生活を豊かにしてくれますが,溢れる情報の中から自分に必要な情報を選び出すことはたいへんな作業です.たとえば筆者が1日に受け取る電子メールは迷惑メールも含めると数百通にもなり,とても1通1通目を通して処理することはできない量になりつつあります.

このような情報の氾濫に対して,必要な情報だけを選び出す技術が情報フィルタリングです.情報フィルタリングの定義は,「ユーザが情報に対する優先度をプロファイルとして与えることで,ユーザに送られる情報の除外や優先度の付加を行い,効率的な情報収集を支援すること」とされています.データベースに対する問合せと共通する部分も多いですが,本質的な違いはデータベース問合せ(情報検索)が過去の蓄積データに対する問合せであるのに対し,情報フィルタリングは未来のデータに対する問合せであるため,要求の意味するところやデータソースが動的に変化することであると言えます.

具体的なフィルタリング手法としては,ユーザが自分の好む情報をキーワードとして与えるキーワードマッチングや,提示された情報をユーザが評価することでシステムにフィルタリング基準を学習させる関連フィードバック,自分とよく似たタイプの人が閲覧しているものを優先するソーシャルフィルタリングなどさまざまな手法が提案されており,これらの一部はハードディスクレコーダや,インターネット上の有害情報除去ソフト,メールのスパム除去フィルタなどにすでに用いられています.

2. フィルタリングの処理方法

これまでの情報フィルタリングに関する研究は,フィルタリングアルゴリズムを提案してユーザの要求をいかに精度よく満たすかという点に注力したものがほとんどでした.しかし,実際にフィルタリングシステムを構築する場合,処理コストに注目し,より効率のよい方法でフィルタリング処理を行うことを考える必要があります.たとえば下図に示すように,複数の手法を組み合わせたフィルタリングを考えた場合,ケース1,2ともに,フィルタリングの順序を入れ替えることで処理コスト(処理するデータ数)が下がっています.しかし,ケース2の場合は入れ替えの前後でフィルタリング結果が異なっているため結果の一貫性を維持できていません.つまり,順番を入れ替えてもよいのはケース1の場合のみとなります.

filter1

同様にフィルタリングの処理方法についても変換できる場合とできない場合があります.筆者らの提案する枠組みでは下図に示す4つの処理方式を扱います.逐次処理はデータをいちいち処理するため結果を素早く受け取れる反面処理コストが高く,一括処理はコストが低い分一定時間ごとにしか結果を受け取れません.このように,それぞれの方式にはメリット/デメリットが存在し,状況に応じて最適な方式を選択利用することが必要になります.しかし,フィルタリングの種類によっては処理を変換したときに結果の一貫性が保てない可能性があります.

filter2

そこで,筆者らの研究グループではフィルタリングを関数として扱うフィルタリング関数の枠組みを提案しました.この枠組みを用いることで,フィルタリングの特性を定性的に評価でき,処理方式を変換した場合に「結果が等価になる」か「等価になるとは限らない」のどちらであるかを判断できるようになります.

3.フィルタリング関数

情報フィルタリングは,ある入力を与えたときに,その中から取捨選択をして結果を出力するという意味で関数の働きをしていると言えます.そこで,関数fに対し,データアイテム集合Tを与えるとTから一部が取り去られた結果を出力すること(減少性:f (T)⊂T),および2回以上同じ関数fを適用しても結果が変わらないこと(ベキ等性:f (f (T)) = f (T))を,関数fがフィルタリングである条件であると定義しています.こう考えることで,関数fに対して連続して到着するデータアイテム集合S,Tを4つの処理手法でそれぞれ処理することは図1に示される式で表現されます.また,下図3に示すように,例えば関数fがf (S∪T) = f (S∪f(T))という条件を満たすならば,これは一括処理の結果と逐次処理の結果が常に等価となる(逐次等価性)ことを表します.また図3右に示す性質関係より,たとえば逐次等価性を満たすフィルタリングは同時に並列等価性を満たすこともわかります.このように,フィルタリングを関数として扱うことで,フィルタリングの性質を,関数が満たす制約条件式として表現できるようになります.また,これらの制約条件間の関係や合成関数の性質を明らかにすることで,フィルタリングアルゴリズムを定性的に表現でき,フィルタリングアルゴリズムの性能比較や等価なフィルタリングアルゴリズムへの置換が行えるようになります.たとえばこれまでの成果から,逐次等価性を満たすフィルタリングは,キーワードマッチングのようにそのフィルタリングが簡単な論理演算で表現できることがわかっています.一方,逐次等価性を満たすフィルタリング同士を組み合わせた場合,その順番を変更すると結果の一貫性が保証できないこともわかっています.

filter3

4.応用システム

筆者らは,この数学的基盤を活用したフィルタリングシステムの例として,動的な処理方法変換機能をもつフィルタリングシステムを構築しました.構築したシステムは下図4に示すように,フィルタリングSQLと呼ぶSQLベースのフィルタリング記述言語によってユーザの要求を記述すると,フィルタリング関数の体系を用いて等価変換可能な処理を導出し,自動的に最適な処理方法を選択しながらフィルタリング処理を行います.たとえば,端末の処理能力が一時的に足りなくなると自動的に逐次処理から一括処理に処理を変更したり,他の端末に処理を依頼して分散処理を行う機能をもっています.また,フィルタリングが合成されている場合には,各フィルタリングの処理コストを計測して最適なフィルタリングの実行順序への入れ替え処理を行います.

filter4

5.おわりに

本ページでは,フィルタリング関数の枠組みを通して情報フィルタリングを数学的に取り扱う取り組みを紹介しました.情報フィルタリングシステムは,今後携帯電話や情報家電など比較的処理能力の低い機器でも動作させなければならず,提案システムのように常に処理コストを抑える仕組みが必要になってくると考えられます.このような性能比較やフィルタリングの処理変換を可能にする枠組みは世界的に見てもこれまで存在せず,本研究で提案する枠組みが,これからの情報フィルタリングアルゴリズムや情報フィルタリングシステムにおいて基盤として広く利用されることを期待しています.なお,関連する論文や研究成果は下記参考文献リストを参照ください.

参考文献

[1] 澤井里枝,塚本昌彦,寺田 努,Loh Yin Huei,西尾章治郎,``情報フィルタリングの関数的性質について,'' 電子情報通信学会論文誌, Vol. J85-D-I, No. 10, pp. 939--950 (Oct. 2002).
[2] 澤井里枝,塚本昌彦,寺田 努,西尾章治郎,``フィルタリング関数におけるセレクションとランキングについて,'' 情報処理学会論文誌:データベース, Vol.43, No. SIG12(TOD16), pp. 80--91 (Dec. 2002).
[3] 澤井里枝,塚本昌彦,寺田 努,西尾章治郎,``合成フィルタリング関数の性質について,'' 情報処理学会論文誌:データベース, Vol. 44, No. SIG3(TOD17), pp. 43--53 (Mar. 2003).
[4] 澤井里枝,塚本昌彦,寺田 努,西尾章治郎,``情報フィルタリングの実行順序に関する関数的性質について,'' 情報処理学会論文誌:データベース, Vol. 44, No. SIG3(TOD17), pp. 54--64 (Mar. 2003).
[5] 澤井里枝,塚本昌彦,寺田 努,西尾章治郎,``フィルタリング関数の和積について,'' 情報処理学会論文誌:データベース, Vol. 44, No. SIG12(TOD19), pp. 86--97 (Sep. 2003).
[6] 小寺拓也,澤井里枝,寺田 努,塚本昌彦,西尾章治郎,``数学的性質を利用した処理方法最適化機構をもつ情報フィルタリングシステム,'' 日本データベース学会レターズ(DBSJ Letters), Vol. 2, No. 2, pp. 53--56 (Oct. 2003).
[7] Rie SAWAI, Masahiko TSUKAMOTO, Yin Huei LOH, Tsutomu TERADA, and Shojiro NISHIO, ``Functional Properties of Information Filtering,'' Proc. of the 27th International Conference on Very Large Data Bases (VLDB2001), pp. 511--520 (Sep. 2001).
[8] Rie SAWAI, Masahiko TSUKAMOTO, Tsutomu TERADA, and Shojiro NISHIO, ``Composition of Filtering Functions,'' Proc. of the 9th International Conference on Database Systems for Advanced Applications (DASFAA 2003), pp. 293--300 (Mar. 2003).
[9] Rie SAWAI, Masahiko TSUKAMOTO, Tsutomu TERADA, and Shojiro NISHIO, ``Composition Order of Filtering Functions for Information Filtering,'' Proc. of the 1st International Conference on Mobile Computing and Ubiquitous Networking (ICMU 2004), pp. 166--171 (Jan. 2004).
[10] Rie SAWAI, Masahiko TSUKAMOTO, Tsutomu TERADA, and Shojiro NISHIO, ``Union and Intersection of Filtering Functions for Information Filtering,'' Proc. of the 10th International Conference on Database Systems for Advanced Applications (DASFAA 2004), pp. 738--749 (Mar. 2004).
[11] Takuya KODERA, Rie SAWAI, Tsutomu TERADA, Masahiko TSUKAMOTO, and Shojiro NISHIO, ``An Information Filtering System that Optimizes the Processing Method Based on Mathematical Properties,'' Proc. of IASTED International Conference on Communications, Internet, and Information Technology (CIIT 2004), pp. 274--279 (Nov. 2004).

連絡先

mail

tsutomu[[at]]eedept.kobe-u.ac.removehere.jp