More Related Content Similar to Learning to rank for IR
Similar to Learning to rank for IR (20) Learning to rank for IR2. 目次
1. ランクチューニングと機械学習
1. Googleでのランクづけ
2. ランクづけでの問題
2. 機械学習とは
3. 機械学習を使って、どうランクチューニングするか
1. ランキングの評価方法
2. 正解ランクをどうやって決めるか
3. ランキング学習手法分類
4. 具体的な計算(SVM Rank)
5. Googleでのランクづけ
● Googleが重視している項目
○ 200個のパラメータでランクを決めている?
○ 2009年当時
○ http://www.searchenginejournal.com/200-parameters-in-google-
algorithm/15457/#ixzz1Io4iBrJI
6. Googleでのランクづけ
例 ● Visitorプロファイル
○ Visitor数
● ドメイン関係
○ Visitor統計(性別とか)
○ ドメイン取得日
● ペナルティ
○ ドメイン取得からの期間
○ 過去のペナルティ
● サーバ
○ 重複コンテンツ
○ 稼働時間
○ 過去のハッカーによる攻撃
○ 設置場所(国とか?)
● 設計
○ URL構造
○ HTML構造
● コンテンツ
○ 言語
○ ユニーク性
○ コンテンツ量(text vs HTML)
● 内部リンク
○ ページ内内部リンク数
○ ページ内内部リンク(with anchor text)数
● Webサイト
○ サイト更新頻度
○ サイトサイズ(ページ数) ウェブサイトの様々な特徴を
検索結果ランクに取り込んでいる
● 外部リンク
○ ドメイン内外部リンク数
○ ページ内外部リンク数
○ リンクされているサイトの質
○ 404, error pageなどへのリンク数
8. 例
● 新しさ f
○ より新しいdocのランクが上
○ 数値化例
■ 昨日の記事 -1
■ 20日前の記事 -20
● 文書に含まれている検索キーワードの数 c
○ 数が大きいほうがランクが上
● 文書部分ごとの検索キーワードの数 cpn
○ 数が大きいほうがランクが上
○ titleタグ n=1
○ h1タグ n=2
ランク R(大きいほど上位)
R = wf f + wc c + wcp1 cp1 + wcp2 cp2
w*は各情報に対するウエイト
(現実的にはtf-idf, BM25を使用したりもするが、例なので省く)
11. Learning to Rank for IRの歴史
● 2000頃 -
○ 商用検索エンジンにランキング学習が使われ始める(学術目的ではなく)
● 20??
○ Google
■ 機械学習だけを使用しているわけではないらしい
■ 2008 http://www.webcitation.org/getfile.php?
fileid=49a8c1e6d41579005211a7841646a44431cfd6e5
● 2002
○ AltaVista
● 2004
○ Yahoo/Inktomi
● 2005
○ Bing
● 2009
○ Yandex(Russian search engine)
● 2009
○ Yandex, machine-learning competition "Internet Mathematics 2009"
● 2010
○ 米Yahoo, machine-learning competition "Learning to Rank Challenge"
引用:http://en.wikipedia.org/wiki/Learning_to_rank
19. 機械学習の例
方法1
● サポートベクターマシン(Support Vector Machine, SVM)
● 線形判別分析
方法2
● k近傍法(k Nearest Neighbor, knn)
● 最短距離法
方法3
● 決定木
● ランダムフォレスト(Random Forest, 集団学習)
その他の方法
● 単純ベイズ分類器(Naive Bayes, スパム分類とか)
● ニューラルネットワーク(Neural Network)
● ...
29. 上位四つまでで評価するなら、
NDCG=0.37
(もっと多くの検索キーワードを使
う場合は平均値)
Gain DCG IDCG NDCG
(Discount (Ideal DCG) (Normalized
Cumulative DCG)
Gain)
d1 20 - 1 0 / log 2 15 / log 2 0 / 49.83
(rd1=0) =0 =0 = 49.83 =0
d2 23 - 1 0 + 7 / log 3 49.83 + 14.67 / 64.5
(rd2=3) =7 = 14.67 7 / log 3 = 0.23
= 64.5
d3 24 - 1 0 + 14.67 + 49.83+64.5+ 39.58 /
(rd3=4) =15 15 / log 4 3 / log 4 119.31
= 39.58 = 119.31 = 0.33
d4 22 - 1 0 + 14.67 + 49.83+64.5+ 43.87 /
(rd4=2) =3 23.7 119.31 119.31
+ 3 / log 5 +0 / log 5 = 0.37
= 43.87 = 119.31
30. 正解ランクをどうやって決めるか
今までに使用されてきた方法
1. 人手による適合性評価
○ 評価には主観が入るため、何人かで評価し総合する
1. クリックログ (click-through log)
○ [Joachims 02] http://www.cs.cornell.edu/People/tj/publications/joachims_02c.pdf
○ [Dou+ 08] http://research.microsoft.com/pubs/79335/CT_Ranking_Paper.pdf
引用元:https://kaigi.org/jsai/webprogram/2010/pdf/355.pdf
32. Pointwise(Bipartite)手法
検索キーワードk1 検索キーワードk2
文書1 文書5
文書2 文書6
文書3 文書7
文書4 文書8
検索キーワードk1 検索キーワードk2
に対して に対して
文書1 is good 文書5 is bad
文書2 is bad 文書6 is bad
文書3 is good 文書7 is bad
文書4 is good 文書8 is bad
33. Pairwise手法
検索キーワードk1 検索キーワードk2
文書1 文書5
文書2 文書6
文書3 文書7
文書4 文書8
検索キーワードk1 検索キーワードk2
に対して に対して
文書2 > 文書1 文書5 > 文書7
文書3 > 文書4 文書8 > 文書6
... ...
34. Listwise手法
検索キーワードk1 検索キーワードk2
文書1 文書5
文書2 文書6
文書3 文書7
文書4 文書8
検索キーワードk1 検索キーワードk2
に対して に対して
文書2 > 文書1 > 文書3 > 文書4 文書5 > 文書7 > 文書8 > 文書6
36. Pairwise手法でランキング学習してみる
学習データ ランク予測の
# query 1
データフォーマット 3 qid:1 1:1 2:1 3:0 4:0.2 5:0 NDCGによる評価
"正解ランク" qid:"キーワードID" 1:特徴量1 2:特徴量2 ... 2 qid:1 1:0 2:0 3:1 4:0.1 5:1
1 qid:1 1:0 2:1 3:0 4:0.4 5:0
特徴量: titleに検索キーワードを含んでいる数など 1 qid:1 1:0 2:0 3:1 4:0.3 5:0
# query 2
NDCG1=0.48
1 qid:2 1:0 2:0 3:1 4:0.2 5:0
2 qid:2 1:1 2:0 3:1 4:0.4 5:0
NDCG2=0.85
1 qid:2 1:0 2:0 3:1 4:0.1 5:0
1 qid:2 1:0 2:0 3:1 4:0.2 5:0
NDCG3=0.86
# query 3
2 qid:3 1:0 2:0 3:1 4:0.1 5:1
NDCG4=0.86
3 qid:3 1:1 2:1 3:0 4:0.3 5:0
4 qid:3 1:1 2:0 3:0 4:0.4 5:1
データとしてMicrosoft Researchが提供している 1 qid:3 1:0 2:1 3:1 4:0.5 5:0
データ LETOR を使いたかったが、時間がなかったため割愛
http://research.microsoft.com/en-
us/um/beijing/projects/letor/
①
テストデータ
5 qid:4 1:1 2:1 3:0 4:0.3 5:0
② モデル ③ ランク予測
1.40287793
ω=
4 qid:4 1:1 2:0 3:0 4:0.2 5:1 2.43987615
(1.5231243, -0.064747944, -0.5231243
2 qid:4 1:0 2:0 3:0 4:0.2 5:1 0.91675182
4, -0.18499486, 0.95375079)
1 qid:4 1:0 2:0 3:1 4:0.2 5:0 -0.56012331
37. 参考文献
● http://www-tsujii.is.s.u-tokyo.ac.jp/T-FaNT/T-FaNT.
files/Slides/Li.pdf
● http://en.wikipedia.org/wiki/Learning_to_rank
● http://en.wikipedia.org/wiki/Discounted_cumulative_gain
● http://d.hatena.ne.jp/sleepy_yoshi/20110723/p1
● http://www2009.org/pdf/T7A-LEARNING%20TO%
20RANK%20TUTORIAL.pdf