ユーザの行動履歴を利用した画像検索エンジン ∗田内 学 † ,††井手 一郎 ‡,東京大学大学院情報理工学系研究科

近年、インターネットを通じて、我々が利用できる情報量は飛躍的に増大しており、扱うメディアもテキスト、画像、音声など多岐にわたっている。増え続ける情報の中から必要な情報を検索するために、これらの情報への索引付けの必要性が高まっている。そこで、テキストとそれ以外のメディアを統合的に処理し、自動索引付けを行う研究が盛んになっているが、これらの多くは統計的手法であるため、索引とメディア内容との対応を必ずしも機構的に保証されていない。

Web 上の画像検索エンジン Image Google[1] では画像に付随するテキスト情報などを利用して自動索引付けを行っているが、索引付け精度が高いとは言えず、ユーザは検索結果として提示された各画像が適切な画像かどうかを一つ一つ判断したり、検索条件を変えて再検索を行ったりの試行錯誤を経て目的の情報にたどり着いているのが現状である。
本研究ではこうした検索時のユーザによるキーワードの再選定や画像の選択といった行動履歴をもとに画像へのキーワード索引付けを随時洗練させ、他のユーザが次回、同様の意図で検索する際に、より高品質の結果をより少ない試行錯誤で提示することを目指す。

2関連研究

2.1

Relevance Feedback による画像検索システム

Zhu らの開発した画像検索システム iFind[2] では、索引と画像特徴量とを利用した Relevance feedback による検索を行っており、同時に索引の重みも変更している。このシステムでは、ユーザの利用により最適化されるのは、索引の重みのみであり、試行錯誤における以前のクエリなどにより新たな索引が付与されにくい。

2.2

検索エンジンの利用履歴を利用した研究

杉崎らは検索エンジンの利用履歴を利用して次検索侯補単語を提示する研究を行っている [3]。その中で、検索が行われた時間間隔を利用して、単語間の関連度を導いている。単語間の関連度はユーザ i の検索語 x, y∗ “Text-based

田中 英彦 †{ manabu, sakai, tanaka}@mtl.t.u-tokyo.ac.jp,

はじめに1

坂井 修一 † ,image search engine referring to user’s behaviour”
Manabu Tauchi† , Ichiro Ide‡ , Shuichi Sakai† , HidehikoTanaka†† Graduate School of Infomation Science and Technology, The
University of Tokyo,
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan‡ National Institute of Informatics,
2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan‡‡

ide@nii.ac.jp

国立情報学研究所の使用時間差の最小値を tmixy として単語 x, y の間隔関連度 Txy を以下の式で求めている。t1 , t2 はそれぞれ適当な時間である。
Txy =assoc(tmixy )atmixy = 0
 10 < tmixy ≤ t1
assoc(tmixy ) = t2 −tmixy
t1 < tmixy ≤ t2

 t2 −t1
0t2 < tmixy
同様に、クエリ間の時間間隔が短いほど、ユーザの検索意図は近いと考えられ、クエリ間の関連性は高いと考えられる。

3

行動履歴を利用した索引付け

3.1

提案手法の概要

図 1: 提案する検索・索引付けシステムの概要
本研究において提案する検索・索引付けシステムの概要を図 1 に示す。本システムでは、検索結果をサムネイル表示し、ユーザのクリックにより原寸大に表示されるようにしている。そのため、クリックされた画像はユーザの求めていた情報であり、ユーザがクエリとして入力した検索キーワードに関連が強い画像と考えられ、逆に、クリックされなかった画像はキーワードに関連が少ない画像であったと考えられる。そこで、選択された画像に対するキーワードの重みは増やし、選択されなかった画像に対する重みは減らすことで、ユーザの判断をフィードバックする。

3.2

過去の検索との関連性

検索結果に目的の画像がない場合、ユーザはクエリを変更して再検索することが多い。再検索の後にユーザが選択した画像は過去のクエリとの関連性も高いと考えられるため、ユーザが過去に入力したクエリについてもフィードバックの際に考慮する。2.2 で紹介した

間隔関連度と同様に、あるユーザ i によるクエリ q, rの入力された時間の間隔を tiqr としてクエリ間関連度
Rqr を以下のように定義することにした。
(0 < tiqr ≤ t1 ) 1

Rqr =t2−tiqr
 t2 −t1

0(t1 < tiqr ≤ t2 )(t2 < tiqr )

4

実験

4.1

実験システムImage Google より収集した果物に関する画像約 3,000枚を検索対象にし、提案手法を実装した。元となる索引情報は Image Google のもの（明らかな索引付けの間違いも含む）を利用した。この索引情報は、Image
Google において、検索キーワード k による検索結果に含まれる画像に対して、k を重み 1 で索引として与えた。このシステムでは画像 p に対する索引 k の重み wpkは、サムネイル表示されたときに、以下の式に従い一律に減らされる。
wpk− = f(w pk , max(R qr /nr |r ∈ Qk )) x(1 − c1 y) w1 < xf(x, y) =00 < x ≤ w1
x − c2 yx≤0
クリックされたときには以下の式に従ってクリックされた画像のみ重みが増える。

wpk+ = wpk + max(c3 Rqr /nr |r ∈ Qk )なお、q はサムネイル表示またはクリックされたときのクエリ、Qk は k を含むクエリ集合、nr は r に含まれる単語数であり、定数 c1 , c2 , c3 , w1 はそれぞれ0.05, 0.02, 1, 0.1 とした。

みを適合度計算の際に考慮し、wpk + (画像類似度) を画像の適合度とし、その順に表示した。画像の類似度は色コリログラム [4] の内積によって求めた。

4.2

実験と結果被験者に “りんご” の画像を実験システムを用いて検索させた。これを 4 回繰り返した。それぞれの実験において、被験者は、“りんご”、“リンゴ”、“ふじ” などとクエリを変えて、検索を行ったため、“リンゴ” が索引付けされていた画像に、新たに “りんご” が索引付けされるなどの効果があらわれ、“りんご” が索引付けされている画像は 17 個から 40 個に増加した。また、図3 に示すように、実験ごとに提示される画像の適合率は向上していった。

図 3: 単語 “りんご” が索引付けされている上位 N 個の画像における適合率5おわりに本研究では、ユーザの行動履歴を索引付け及びその重みづけにフィードバックする検索システムを提案した。実際に被検者に本手法を実装した検索システムを利用してもらい、提案手法の有効性が示唆された。同じキーワードによる検索であっても、ユーザにより検索意図は異なり、正解画像の判断が異なる場合がある
ため、複数のユーザに利用されたときに、どれだけの情報が共有できるかが問題であり、学習効果をいかに客観的に評価するかが課題である。学習前後での正解画像にたどり着くまでの時間及びステップ数の変化を測定することで、評価することを考えている。また、キーワードに対する重みと、画像の類似度をどのように統合的に扱うかが今後の課題である。

参考文献[1] “Image Google”, http://images.google.com/

図 2: 実験システムによる表示例：“りんご” で検索した場合検索結果の表示例を図 2 に示す。索引キーワードの初期値は自動的に付与されたものが多く、誤りやもれがある。そのため、検索結果として検索キーワードが索引付けされた画像以外にも、それらの画像と類似している画像もあわせて提示した。
キーワードと一致した画像で重みが 0 より大きい画像を重み順に表示し、類似画像については 0 以下の重[2] X. Q. Zhu, L. Wenyin, H. J. Zhang, and L. D.
Wu, “Image retrieval and semi-automatic annotation
scheme for large image databases on the web”, Proc.
SPIE, vol.4311, pp.168-177, Jan. 2001
[3] 杉崎正之，牧野俊朗，田中一男：“WWW 検索ログを用いた次検索侯補単語の提示方式の検討”, 情処第 61 回全国大会講演論文集, vol.3, pp.113-114, Oct. 2000
[4] J. Huang, S. R. Kumar, M. Mitra, W. J. Zhu, R.
Zabih, “Image indexing using color correlograms”,
Proc. IEEE Conf. on CVPR ’97, pp.762-768, Jun. 1997