論文――――――――――――――――――――――――――――――――――――

情報検索における相対的問合せの表現とその処理方法
Relative Query Specification and Their
Query Processing Methods in Information
Retrieval

中島 伸介♥

田中 克己♦

Shinsuke NAKAJIMA

Katsumi TANAKA

従来の情報検索手法のほとんどは，検索しようとするデータ領域に対して，ユーザが数値やキーワード等の絶対的条件を指定することにより，この条件に合致したデータを取得しようとするものである．これらの検索方法では，ユーザは目的のデータに関する何らかの絶対的条件を認識している必要があるが，ユーザが情報検索を行う際に，これらの条件を認識しているとは限らない．人間同士のコミュニケーションにおいては，既知の他のデータと比較，すなわち相対的表現に基づく問合せにより，目的のデータの特徴を表現することがある．本研究では人間としては自然ともいえる相対的表現に基づく問合せを行う場合の，問合せの表現方法とその処理方法について述べる．
Most conventional information retrieval systems
require absolute condition like keywords from users inorder to retrieve data that the users want to retrieve.
Thus, users have to know keywords or metadata of thedata. However, we cannot say that users must know themetadata even if they have images of the data that theywant. On the other hand, we often express the data that
we want by comparing it with the recognized data. We
believe that it is natural for us to express a favorite datausing relative evaluations. Therefore, we propose relative
retrieval queries based on user’s relative evaluations.
Furthermore, this paper describes their query processing.

1. はじめに
従来の情報検索技術は，ユーザが得ようとする情報の絶対的条件を指定することによって検索するものが多い．Web 情報に対する検索エンジンでのキーワード検索，データベースに対する属性条件による検索，画像データベース等に対するコンテンツベース検索などがこれに当てはまる．これらの方法は，検索しようとするデータ領域に対してユーザが数値やキーワード等の絶対的条件を指定することにより，この条件に合致したデータを検索する．したがって，ユーザは得ようとするデータに関する十分な知識を持っている必要があるが，未だ見ぬデータに関する絶対的条件を把握しているとは限らない．
♥学生会員 京都大学大学院情報学研究科博士後期課程
nakajima@dl.kuis.kyoto-u.ac.jp♦正会員 京都大学大学院情報学研究科
tanaka@dl.kuis.kyoto-u.ac.jp

1

DBSJ Letters Vol.2, No.2

実世界の人間同士のコミュニケーションでは，「この集合の中では，これが好き」といった相対的な評価により自分の好みを表現することがある．このような相対的評価により自分の要求を表現することは，人にとっては自然な行動である．
したがって，本研究では相対的表現による問合せ方法と，この相対的問合せの処理方法について検討する．
相対的問合せは以下のように定義される．
ユーザが，あるサンプル集合の中からデータを選択した際の，サンプル集合に対する選択データの相対的関係に基づいて，生成される問合せ
サンプルデータ集合を S ，選択されたデータを x とすると，相対的問合せ Q は，以下のように表現できる．

Q = ( x, S ) （ただし， x ∈ S ）この相対的問合せにより，ユーザは欲しい情報の絶対的条件を指定する必要はなく， このデータ集合の中ではこれ！という直感的かつ簡易な指定方法により，検索の問合せを指定できるメリットがある．これにより，検索に関する高度なノウハウを有しないユーザでも，直感的かつ効率的な検索が実現できると考えている．
この相対的問合せの処理方法としては，差異増幅処理[1][2]や，相対的マッピング処理[3]などを検討している．
差異増幅処理とは，ユーザによる相対的問合せにおいて，サンプル集合内での選択データと非選択データとの差異を増幅することで，ユーザの意図をより強く反映した処理を行うものである．相対的マッピング処理とは，ユーザによる相対的問合せにおいて，サンプル集合内での選択データの相対的関係を取得し，他のデータ集合（ターゲットデータ集合）において，サンプル集合内での相対的関係を満たすデータを検索するものである．本論文では，上記相対的問合せの処理方法のうち，相対的マッピング処理について述べる．
ここで，相対的マッピング処理について，デパートでのジャケット購入を例にとって説明する．
＜相対的マッピング処理が適切な例＞
店員から提示された幾つかのジャケットの中に比較的ユーザの要求を満たすものがあるが，全て高級ブランドのものであり購入できない．したがって，この時のジャケット集合の中でのユーザの要求を満たす別のブランドのジャケットを提示してもらおうとする．
この時，ユーザは満足度の高いジャケットを見つけたものの，サンプルとして提示された集合そのものに問題があるため，このユーザは 選択したデータのサンプル集合内での相対的関係 を満たすデータを，（明示的にユーザが指定した）問題のない集合の中で検索しようとする．つまり，相対的問合せの相対的マッピング処理は，ユーザが選択したデータのサンプル集合内での相対的関係を取得し，ユーザが明示的に指定したターゲット集合において，この相対的関係を満たすデータの検索が可能な方法である．
以下，2章において相対的マッピング処理の厳密な定義について述べ，3章において相対的マッピングの近似処理方法について述べる．4章において，相対的マッピング処理に基づく画像検索について述べ，5章にてまとめを述べる．

2. 相対的問合せの相対的マッピング処理の定義
本節では相対的問合せの相対的マッピング処理の定義について説明する．相対的問合せの相対的マッピング処理は，ユーザが選択したデータのサンプル集合内での相対的関係

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――DBSJ Letters Vol.2, No.2を取得し，ユーザが明示的に指定したターゲット集合において，この相対的関係を満たすデータを見つけ出す手法である．
したがって，相対的問合せ Q に対してターゲット集合を Tとすると，相対的マッピング処理により得られる答え
Ans(Q, T ) は，以下のように定義できる．ただし，ここではサンプル集合内のデータ数と，ターゲット集合内のデータ数は等しいものとする（|S|=|T|）．

Ans (Q, T )= Ans (( x, S ), T )= { f ( x ) | x ∈ S ， f は relative( f ( x ), f (S )) と relative( x, S )の類似度が最大となる集合 S から集合 T への全単射写像
関数｝

図2
Fig.2

ただし， relative( x, S ) は，x と S の間の相対的な関連を関数ｆによる写像
Mapping by function f

特徴ベクトルにより表現する評価関数である．つまり，この相対的問合せの相対的マッピング処理による答えは，relative( x, S ) と relative( f ( x ), f (S )) が最も等しくなる時の，写像関数 f により，選択されたデータ x を写像した f(x)となる．（図１参照）

図3
Fig.3
図1

集合 S から T への写像

Fig.1

Mapping from S to T

ここで， relative( x, S ) について以下の通り定義する．

厳密な定義での relative 関数

Strictly defined relative function

relative( f ( x ), f (S ))= relative(t i , T )r r r rr rr rr r
= (t i − t1 ) ⋅ (t i − t 2 ) ⋅ ⋅ ⋅ (t i − t i −1 ) ⋅ (t i − t i +1 ) ⋅ ⋅ ⋅ (t i − t n )サンプル集合およびターゲット集合のデータ数を n とする．関数 f は，集合 S 内の点を集合 T 内の点に写像する関数である．
（図２参照）

集合 S および集合 T のデータ数が n 個であるので，写像関数 f は n!通りのパターンが存在する．この中から，以下のコサイン相関値が最も高くなる時の関数 f を求める．

S = {s1 , s 2 ,⋅ ⋅ ⋅, s n }, andrelative (x, S ) ⋅ relative ( f (x ), f (S ))relative (x, S ) ⋅ relative ( f (x ), f (S ))T = f (S )= { f (s1 ), f (s 2 ),⋅ ⋅ ⋅, f (s n )}= {t1 , t 2 ,⋅ ⋅ ⋅, t n }relative( x, S ) は，選択データ x（ = si ）と非選択データとの差異ベクトルに基づいて定義される．（図３参照）

relative( x, S )= relative (si , S )r r r rr rr rr r
= (si − s1 ) ⋅ (s i − s 2 ) ⋅ ⋅ ⋅ (si − si −1 ) ⋅ (si − si +1 ) ⋅ ⋅ ⋅ (s i − s n )各差異ベクトルを結ぶ点 ・ は，ベクトルの連結を示す．
同様に，relative( f ( x ), f (S )) は，以下の通り定義される．

2

そこで，相対的問合せに対する相対的マッピング処理による答え Ans(Q, T ) は，最終的には以下のように表現できる．

Ans (Q, T )= Ans (( x, S ), T )= { f ( x ) | x ∈ S ， f はコサイン相関値relative (x, S ) ⋅ relative ( f (x ), f (S ))relative (x, S ) ⋅ relative ( f (x ), f (S ))が最大となる

集合 S から集合 T への全単射写像関数｝-----（A）

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――DBSJ Letters Vol.2, No.2

3. 相対的問合せに対する相対的マッピングの近似処理法の手順は以下の通りである．

前節にて，相対的問合せの相対的マッピング処理の定義について説明した．しかしながら，集合 S のデータ数が m，集合 T のデータ数が n である場合，mn 通りの写像のパターンが存在する．したがって，集合 S および集合 T のデータ数が非常に小さい値でない限り，問合せ処理を行うことは難しい．さらに，厳密な相対的マッピング処理の定義においては，|S|=|T|であることを想定して定義を行っており，|S|≠|T|である場合は同様に処理することはできない．

２）relative′ x, S を相対的特徴ベクトル x − S c として算出する．

そこで，集合 S および集合 T のデータ数がある程度大きな値をとる場合や，|S|≠|T|である場合でも，相対的問合せを処理することが可能な相対的マッピングの近似的処理方法について検討する．
相対的マッピングの近似処理は，前節の厳密な相対的マッピング処理の定義の示す式（A）のうち，relative 関数を近似的に解釈することで定義する． relative( x, S ) は，集合 S内での選択データ x の相対的位置付けを示す関数であり，厳密な定義での相対的マッピングでは選択データと非選択データとの特徴空間上の差異ベクトルを連結したものと定義される．そこで近似的処理方法では，選択されたデータ x の集合 S 内での相対的位置付けを，単純に属する集合 S の全てのデータの重心（集合 S 内全データの平均特徴ベクトル）を基にした，選択データ x の相対ベクトルによって表現する．
すなわち， relative( x, S ) の近似解， relative' ( x, S ) は，集合（図４参照）
S の重心を Sc とすると以下のように表現できる．

r r
relativ e ′( x, S ) = x − S crr
ただし， x および S は，それぞれ x および S の特徴ベクト
ルである．

図4
Fig.4

近似的 relative 関数

Approximative relative function

同様に，relative( y, T ) の近似解，relative' ( y, T ) は，集合T の重心を Tc とすると以下のように表現する．（図４参照）

r r
relativ e ′( y , T ) = y − Tcrr

ただし， y および T は，それぞれ y および T の特徴ベクトルである．
相対的問合せに対する相対的マッピングの近似的処理方

3１）ユーザは，集合 S の中から好みのデータ x を選択する．

(rr)rr３）全ての relative′(t i , T ) を相対的ベクトル t i − Tc として算出する．

()４）システムは relative′ x, S との類似度が最も高くなる
relative′(t i , T ) を特定し，この時の ti を相対的問合せの解 y とする．
したがって，相対的問合せに対する相対的マッピングの近似処理による解 Ans ' (Q, T ) は，最終的には以下のように表現できる．

Ans ' (Q, T )((x, S ), T )= Ans '

= { y | y ∈ T ，コサイン相関値(xr − Srr )⋅ (yr − Trr ) が最大｝
ccrr
x − S c ⋅ y − Tc

4. 相対的マッピング処理に基づく画像検索
4.1 プロトタイプシステム
相対的問合せおよびその相対的マッピング処理は，適用可能なコンテンツの制限はないが，本論文では画像検索に相対的問合せおよびその相対的マッピングの近似処理を適用して，プロトタイプ画像検索システムを構築した．なお，画像データの特徴量抽出方法としては，２次元離散コサイン変換（DCT）[4]を用いた．本論文では，このプロトタイプシス
テムを用いて，相対的問合せと相対的マッピングの近似処理の妥当性の検証を行う．
サンプル集合を黄色い花の画像集合として，赤い花の画像集合から画像を検索した場合と，反対にサンプル集合を赤い花の画像集合として，黄色い花の画像集合から画像を検索した際の結果を図 5 に示す．それぞれ，サンプル集合内において，中程度の大きさの花が中央に写っている画像を選んだ例を基に，ターゲット集合の画像から条件に合致する画像を検索した．それぞれ，単純な類似検索を行った際の結果と相対的問合せとして処理した結果のうち，上位３画像を示している．単純類似検索の検索結果では，サンプル集合での画像選択の際の意図である， 中程度の大きさの花の選択 が反映されているとは言い難いが，相対的問合せの検索結果では，中程度の大きさの花 が検索されていると考えられる．

4.2

相対的マッピング近似処理の妥当性の検討

相対的マッピングの近似処理手法は，集合 S と集合 T のデータ数が異なり，ある程度大きなデータ数であっても，適用可能である．しかしながら，定義した純粋な相対的マッピング処理の検索精度をどの程度保証できるのかが不明である．
したがって，近似的手法の結果が厳密な定義での手法の結果をどれだけ再現できるのかという観点から，相対的マッピングの近似処理の妥当性の評価を行う．両者の比較を行うために，実験条件を一致させる必要がある．そこで厳密な相対的マッピング処理でも計算可能な条件とするため，サンプル集合とターゲット集合のデータ数をそれぞれ５個に制限して

日本データベース学会 Letters Vol.2, No.2

論文――――――――――――――――――――――――――――――――――――DBSJ Letters Vol.2, No.2

実験を行う．
評価方法としては，サンプル集合 S の中からデータ x をランダムに選択し，これを基にターゲット集合 T からデータ検索を行う．この実験を 300 回行って，両者の結果が一致する割合を調べた．図 6 に厳密な定義での処理と近似処理の両者が一致した例と，一致しなかった例を示す．データ x はサンプル集合の中から選択されたデータであり，y は相対的問合せの相対的マッピング処理の厳密解，y’は近似解である．
300 例の実験のうち，249 例で厳密解と近似解が一致し 51例が不一致であった（83.0%の一致）．この実験結果より，相対的マッピングの近似的処理は厳密定義の相対的マッピング処理の結果と必ずしも一致しないが，近似的処理として十分適用可能であると考えられる．

5. まとめ
本論文において得られた成果を以下に示す．
・ 相対的表現による問合せとその処理方法である相対的マッピング手法を提案した．プロトタイプシステムを実装した．
・ 相対的マッピング手法の定義を行うと共に，大量のデータに対しても処理可能である相対的マッピングの近似処理方法を提案し，その妥当性について検証した．
今後は，画像以外の他のコンテンツへの適用について検討したいと考えている．

[謝辞]

図5
Fig.5

プロトタイプシステムによる実験結果
Experimental result by prototype system

本研究の一部は，平成 15 年度文部科学省科学研究費特定領域研究(2) 「Web の意味構造に基づく新しい Web 検索サービス方式に関する研究」（課題番号：15017249）による．
ここに記して謝意を表します．

[文献］[1] 木下真一，中島伸介，田中克己：差異増幅型適合フィードバックと相対的質問評価に基づく画像検索システム，
Proc. of DBWeb2002,情報処理学会シンポジウムシリーズ
Vol.2002，No.19, pp.121-128, 2002 年 12 月.
[2] Shinsuke Nakajima, Shinichi Kinoshita, and Katsumi
Tanaka: "Amplifying the Differences between Your
Positive Samples and Neighbors", IEEE International
Conference on Multimedia & Expo (ICME2003) vol.I,pp.441-444 (2003).
[3] 中島伸介，木下真一，小山 聡，角谷和俊，田中克己: 相
対的検索質問とその質問処理方式，DBSJ Letters, Vol.1,No.1, October 2002, pp.7-10 (2002).
[4] 田村英之:コンピュータ画像処理入門, 総研出版，星雲社，
pp.51, 1985年.

中島 伸介

Shinsuke NAKAJIMA

京都大学大学院情報学研究科博士後期課程在学中．1997 神戸大学大学院自然科学研究科機械工学専攻博士前期課程修了．日本データベース学会学生会員，情報処理学会，人工知能学会，環境システム計測制御学会各学生会員．

田中 克己
図6

相対的問合せの厳密解と近似解の比較実験結果の例

Fig.6 Example of Comparative experiments between
strictly defined method and approximative method

4Katsumi TANAKA

京都大学大学院情報学研究科教授．1976 京都大学大学院修士課程修了．工学博士．主にデータベースの研究に従事．情報処理学会，日本データベース学会，人工知能学会，ACM，
IEEE Computer Society 等各会員．

日本データベース学会 Letters Vol.2, No.2