Upgrade to Pro — share decks privately, control downloads, hide ads and more …

検索結果の品質向上 Elasticsearch入門

検索結果の品質向上 Elasticsearch入門

2019年度リクルート新人ブートキャンプ エンジニアコースの講義資料です

Recruit Technologies

June 24, 2019
Tweet

More Decks by Recruit Technologies

Other Decks in Technology

Transcript

  1. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  2. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  3. 1. アルゴリズムの設計と解析 検索ってどんな分野? The Art of Computer Programming, Volume 3:

    Sorting and Searching • 1968年から刊行 • 全7巻予定 • 2019年現在第4巻まで
  4. 2. 情報検索(Information Retrieval) Introduction to Information Retrieval Modern Information Retrieval

    スタンフォード大学の授業 CS 276 Information Retrieval and Web Search の教科書 http://web.stanford.edu/class/cs276/ 検索ってどんな分野?
  5. Java で実装された 検索ライブラリ 利用 $ grep $ awk $ sed

    の index の index 今日のターゲット 検索を実現するアプリケーションは?
  6. 特徴\タイプ 逐次検索 Index 型検索 事前処理 なし(コスト小) あり(コスト大) 検索速度 時間大 時間小

    メモリー使用量 メモリー小 メモリー大 典型的な手法 • grep • Knuth–Morris– Pratt 法 • Boyer-Moore 法 • 転置インデックス • N-gramインデックス • 形態素インデックス 2つの検索タイプ ★ 今日のターゲット
  7. Java で実装された 検索ライブラリ 利用 $ grep $ awk $ sed

    の index の index 検索を実現するアプリケーションは? 逐次型 Index 型
  8. Java で実装された 検索ライブラリ 利用 $ grep $ awk $ sed

    の index の index 検索とは何か? 逐次型 Index 型
  9. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  10. 特性 Inverted Index (転置インデックス) 1. ドキュメントに含まれる特性を キー (全文検索などでは Term) にして、集合を紐付ける

    (リスト構造=Posting List) 2. ドキュメントのリストをソート済み 3. 通常は単語の現れた位置情報も 格納 (フレーズ検索) Index Linux カーネル リリース 1 1 2 2
  11. 特性 Inverted Index (転置インデックス) 1. TAAT = Term At A

    Time 2. DAAT = Document At A Time Index Linux カーネル リリース 1 1 2 2
  12. 特性 Inverted Index (転置インデックス) 1. TAAT = Term At A

    Time = 一品ずつ食べる = 洋食 2. DAAT = Document At A Time = 全部少しずつ食べる = 和食
  13. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】Term At A Time(訳:一度にタームを) •

    Term (転置インデックスのキー) 毎にリストを取得してマージ • ひとつのキー毎に処理 • 洋食 UNIX BSD mmap kernel Linux ① ② TAAT (Term At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7
  14. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(Linux AND mmap) •

    件数の少ないキーから accumulator (マージ用リスト) を作成 • AND 検索の場合、accumulator のサイズは、もっとも件数の少ない リストより大きくなることはない。 UNIX BSD mmap kernel Linux TAAT (Term At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 ① ②
  15. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(Linux AND mmap) 1.

    「mmap」のリストから accumulator を作成 = [1, 5, …] 2. 「Linux」のリストを accumulator にマージ 「1」はある?⇒ある!⇒ stay 「5」はある?⇒ある!⇒ stay (「3」はもう見ない) UNIX BSD mmap kernel Linux TAAT (Term At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 ① ②
  16. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】OR 検索(Linux OR mmap) 1.

    どれでもよいのでキーから accumulator を作成 2. 重複を除いて全てのキーから全部のリストをマージする UNIX BSD mmap kernel Linux TAAT (Term At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7 ① ②
  17. 特性 Inverted Index (転置インデックス) 1. TAAT = Term At A

    Time = 一品ずつ食べる = 洋食 2. DAAT = Document At A Time = 全部少しずつ食べる = 和食
  18. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】Document At A Time(訳:一度にドキュメントを) •

    Document (転置インデックスのリストのアイテム) 毎にリストを取得してマージ • ひとつのドキュメント毎に処理 • 和食 UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7
  19. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(mmap AND Linux) •

    Term (mmap と Linux) 毎にカーソルを準備 • 各カーソルを移動し、共通のドキュメントを発見を発見したら、 accumulator に追加 UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7
  20. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(mmap AND Linux) accumulator

    = [] UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7
  21. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(mmap AND Linux) accumulator

    = [1] UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7
  22. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】AND 検索(mmap AND Linux) accumulator

    = [1, 5] UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7
  23. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】OR 検索(mmap AND Linux) •

    なんでも良いので、accumulator を作る • カーソルを動かして、全ての要素を重複なく追加 UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7
  24. 今でも効率的なアルゴリズムの研究が続 いている TAAT and DAAT S. Ding and T. Suel.

    Faster top-k document retrieval using block-max indexes. In Proceedings of the 34th Annual International ACM SIGIR Conference on Research and development in Information Retrieval, pages 993-1002, 2011. ↑の成果は Lucene 8 (2019/3/14 リリース) で実装 参考 https://fosdem.org/2019/schedule/event/apache_lucene_solr_8/attachments/slides/3325/export/events /attachments/apache_lucene_solr_8/slides/3325/SchindlerLucene8Slides.pdf 参考: https://medium.com/@mocobeta/lucene-8-%E3%81%AE-top-k- %E3%82%AF%E3%82%A8%E3%83%AA%E3%83%97%E3%83%AD%E3%82%BB%E3%83%83%E3%82%B7%E3%83%B3%E3 %82%B0%E6%9C%80%E9%81%A9%E5%8C%96-1-%E5%B0%8E%E5%85%A5%E7%B7%A8-5a6387076e8e
  25. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • ハイブリット index とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  26. Lucene • 転置インデックスを提供 – DAAT(Document At A Time) • 非常にネイティブな検索の機能のみ提供

    – 様々な検索機能 • RangeQuery、FuzzyQuery、BooleanQuery – スコアリング機能
  27. 50,241件 10,320件 520件 30,483件 500,020件 【戦略】Document At A Time(訳:一度にドキュメントを) •

    Document (転置インデックスのリストのアイテム) 毎にリストを取得してマージ • ひとつのドキュメント毎に処理 • 和食 UNIX BSD mmap kernel Linux DAAT (Document At A Time) 1 1 1 2 3 3 4 4 5 5 6 6 7
  28. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  29. 4,820,483件 93,832,732件 car book Posting List (Skip List) 1 3

    3 53395 53395 0件 100,000件 100,000 回見て回る!!
  30. 4,820,483件 93,832,732件 car book Posting List (Skip List) 1 3

    3 53395 53395 53395 53395 53395 53395 18395 291295 18395 291295 0件 100,000件
  31. 4,820,483件 93,832,732件 car book Posting List (Skip List) 1 3

    3 53395 53395 53395 53395 53395 53395 18395 291295 18395 291295 見回る回数が少ない!! ※ スキップの段数に依存 ※ スキップの間隔に依存 0件 100,000件
  32. Posting List (Skip List) • lucene-8.0.0/core/src/java/org/apache/lucene/codecs/MultiLevelSkipListReader.java • lucene-8.0.0/core/src/java/org/apache/lucene/codecs/MultiLevelSkipListWriter.java * Example

    for skipInterval = 3: * c (skip level 2) * c c c (skip level 1) * x x x x x x x x x x (skip level 0) * d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d (posting list) * 3 6 9 12 15 18 21 24 27 30 (df) * * d – document * x - skip data * c - skip data with child pointer
  33. インデックスのデータ構造: B+木 • 葉ノード(葉ブロック)がデータを表す • 内部ノード(内部ブロック)は index(データをもたない) • 各ノードは a

    個以上 b 個以下(例では2個以上3個以下)のエントリを必ずもつ 条件を満たすように、木の構造を変形する • 範囲指定のクエリに対して、強力に動作 • ブロックデバイス(葉ブロックと内部ブロックを格納)との相性が抜群 30 50 7 12 22 30 39 52 55 73 ブロック 15以上
  34. • ブロック単位で読み書き • ブロックの大きさはブロックサイズ • ブロックサイズは結構大きい(Linux のデフォルトは 4 KB) •

    1 bit 書き換えても、ブロックごと書き換えられる 残念ながら SSD も ブロックデバイス ブロックデバイス
  35. mmap • システムコール • システムムコールだけど、ユーザープロセスの仮想アドレス空間に作成さ れるので、コンテクストスイッチが少ない: (ユーザー空間 vs カーネル空間) •

    メモリマップトファイルとして扱えるので、追加・削除・更新が楽 • 複数のプロセス間で共有もできる • 【注意】Java の世界から逸脱している(Java のヒープ外でアロケートされ てる) • 【おまけ】C で malloc すると内部では mmap が呼ばれる
  36. Elasticsearch の推奨設定 “The standard recommendation is to give 50% of

    the available memory to Elasticsearch heap, while leaving the other 50% free. It won’t go unused; Lucene will happily gobble up whatever is left over.” 【注意】Java の世界から逸脱している(Java のヒープ外でアロケートされてる)
  37. util-mmap: Indeed の mmap • https://jp.engineering.indeedblog.com/blog/2015/02/util-mmap- %E3%81%A7%E3%83%A1%E3%83%A2%E3%83%AA%E3%83%9E%E3%83%83%E3%83%94%E3%83%B3%E3%82%B0/ • https://github.com/indeedeng/util/tree/master/mmap MappedByteBuffer

    の既知の制約を克服: – 安全にアンマップできない – サイズが 2GB (int) を超えるファイルをマップできない – スレッドセーフではない
  38. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • ハイブリット index とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  39. 50,241件 10,320件 520件 30,483件 500,020件 1. 同じキーが同じサーバーにいる必要がない ⇔ BSD が別のサーバーにあっても良い

    2. マージさえできればよい ⇔ BSD が複数のサーバーにあってもよい UNIX BSD mmap kernel Linux 分散検索 1 1 1 2 3 3 4 4 5 5 6 6 7
  40. 50,241件 10,320件 520件 30,483件 500,020件 UNIX BSD mmap kernel Linux

    分散検索: indexing 1 1 1 2 3 3 4 4 5 5 6 6 7 UNIX mmap Linux UNIX mmap Linux UNIX mmap Linux
  41. 分散検索 • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) •

    負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第!
  42. 分散検索 • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) •

    負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! Node Node Node
  43. 分散検索 • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) •

    負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! Node Node Node A Shard C Shard B Shard C Shard A Shard B Shard
  44. • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) • 負荷分散(Load

    Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! シャード A, B, C 全部が生存 欠損なしで 検索続行 分散検索: 可用性(Availability) Node Node Node A Shard C Shard B Shard C Shard A Shard B Shard
  45. Node Node Node A Shard C Shard B Shard C

    Shard A Shard B Shard 分散検索: 負荷分散(Load Balance) • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) • 負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! シャードA と B に関する 検索 シャードA と B に関する 検索 シャードA と B に関する 検索
  46. Node Node Node A Shard C Shard B Shard C

    Shard A Shard B Shard • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) • 負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! hash(XXX) mod (# of Shard) = C 分散検索: ルーティング Doc ID: XXX
  47. 分散検索 • 各サーバーをノードと呼ぶ • 各ノードは複数のシャード(部分index)をもつ – シャードは以下を提供 • 可用性(Availability) •

    負荷分散(Load Balance) • ドキュメント単位でルーティング(デフォルト) – どのシャードに格納するのかは、あなた次第! Node Node Node A Shard C Shard B Shard C Shard A Shard B Shard
  48. 分散検索: Index の構成 Shard A アイスクリーム 200円 50円 850円 120円

    Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 • サーバー(シャード)は本来非常に多い(数万台、ここでは3台) • シャードに含まれるドキュメント数には上限有り(100万等) • どのサーバーも、自分の担当の検索は非常に高速(対象が100万位しかないから) • 入り切らなくなってきたら、サーバーを足す (スケールアップではなく、スケールアウト) < 1000,000 < 1000,000 < 1000,000
  49. 分散検索: Two Phase Search, query and fetch Shard A アイスクリーム

    200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 • query phase: どのサーバーにマッチする結果がどれだけあるのか? ⇒ メモリ上+ネットワークトラフィック小で解決 • fetch phase: 見つけた結果を整形(スニペット生成、等)して返却結果を作成 ⇒ 高負荷な処理を実行
  50. 分散検索: Two Phase Search, query and fetch 【重要】各サーバは他のサーバーの安いアイスクリームを知らない!! クエリー:アイスクリーム ORDER

    BY 安い順 LIMIT 3 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円
  51. 分散検索: Two Phase Search, query and fetch クエリー:アイスクリーム ORDER BY

    安い順 LIMIT 3 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 [50, 120, 200] [10, 220, 320] [300, 500, 720] [10, 50, 120]
  52. 分散検索: Two Phase Search, query and fetch クエリー:アイスクリーム ORDER BY

    安い順 LIMIT 3 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 [10, 50, 120]
  53. 分散検索: Two Phase Search, query and fetch Q: 100位〜102位まで取ってくるには? クエリー:アイスクリーム

    ORDER BY 安い順 LIMIT 3 OFFSET 100 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 A: 各サーバーから102件取得してくる
  54. 分散検索: Two Phase Search, query and fetch Q: 嘘でしょ? クエリー:アイスクリーム

    ORDER BY 安い順 LIMIT 3 OFFSET 100 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 A: 本当です。
  55. 分散検索: Two Phase Search, query and fetch Q: 事前に準備とかできないの? クエリー:アイスクリーム

    ORDER BY 安い順 LIMIT 3 OFFSET 100 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円 A: できないです…
  56. 分散検索: Two Phase Search, query and fetch クエリー:(アイスクリーム AND すいか味)ORDER

    BY 安い順 LIMIT 3 OFFSET 100 Shard A アイスクリーム 200円 50円 850円 120円 Shard B アイスクリーム 320円 220円 10円 900円 Shard C アイスクリーム 850円 300円 500円 720円
  57. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  58. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  59. 50,241件 10,320件 520件 30,483件 500,020件 UNIX BSD mmap kernel Linux

    転置インデックス 1 1 1 2 3 3 4 4 5 5 6 6 7
  60. Lucene の世界の Term と Token Token = Term(= 文字列 +

    フィールド) + 開始位置 + 終了位置 • lucene/core/src/java/org/apache/lucene/index/Term.java • lucene/core/src/java/org/apache/lucene/analysis/Token.java これはどう作るの?! Lucene の世界では Tokenizer が分割をしてくれる!
  61. Lucene の Tokenizer • ClassicTokenizerFactory • EdgeNGramTokenizerFactory • HMMChineseTokenizerFactory •

    ICUTokenizerFactory • JapaneseTokenizerFactory • KeywordTokenizerFactory • LetterTokenizerFactory • LowerCaseTokenizerFactory • NGramTokenizerFactory • PathHierarchyTokenizerFactory • PatternTokenizerFactory • StandardTokenizerFactory • ThaiTokenizerFactory • UAX29URLEmailTokenizerFactory • UIMAAnnotationsTokenizerFactory • UIMATypeAwareAnnotationsTokenize rFactory • WhitespaceTokenizerFactory • WikipediaTokenizerFactory
  62. Lucene の Tokenizer • ClassicTokenizerFactory • EdgeNGramTokenizerFactory • HMMChineseTokenizerFactory •

    ICUTokenizerFactory • JapaneseTokenizerFactory • KeywordTokenizerFactory • LetterTokenizerFactory • LowerCaseTokenizerFactory • NGramTokenizerFactory • PathHierarchyTokenizerFactory • PatternTokenizerFactory • StandardTokenizerFactory • ThaiTokenizerFactory • UAX29URLEmailTokenizerFactory • UIMAAnnotationsTokenizerFactory • UIMATypeAwareAnnotationsTokenize rFactory • WhitespaceTokenizerFactory • WikipediaTokenizerFactory
  63. Lucene の Tokenizer • ClassicTokenizerFactory • EdgeNGramTokenizerFactory • HMMChineseTokenizerFactory •

    ICUTokenizerFactory • JapaneseTokenizerFactory • KeywordTokenizerFactory • LetterTokenizerFactory • LowerCaseTokenizerFactory • NGramTokenizerFactory • PathHierarchyTokenizerFactory • PatternTokenizerFactory • StandardTokenizerFactory • ThaiTokenizerFactory • UAX29URLEmailTokenizerFactory • UIMAAnnotationsTokenizerFactory • UIMATypeAwareAnnotationsTokenize rFactory • WhitespaceTokenizerFactory • WikipediaTokenizerFactory
  64. 英語の Tokenize は超簡単 “Elasticsearch is a distributed, RESTful search and

    analytics engine capable of solving a growing number of use cases.” WhitespaceTokenizer “Elasticsearch is a distributed, RESTful search and analytics engine capable of solving a growing number of use cases.”
  65. Lucene の Tokenizer • ClassicTokenizerFactory • EdgeNGramTokenizerFactory • HMMChineseTokenizerFactory •

    ICUTokenizerFactory • JapaneseTokenizerFactory • KeywordTokenizerFactory • LetterTokenizerFactory • LowerCaseTokenizerFactory • NGramTokenizerFactory • PathHierarchyTokenizerFactory • PatternTokenizerFactory • StandardTokenizerFactory • ThaiTokenizerFactory • UAX29URLEmailTokenizerFactory • UIMAAnnotationsTokenizerFactory • UIMATypeAwareAnnotationsTokenize rFactory • WhitespaceTokenizerFactory • WikipediaTokenizerFactory
  66. Ngram Tokenizer 一定の長さの文字列単位で分割 「敵に塩を送る」 • Unigram: 1文字単位 ⇒ 「敵」「に」「塩」「を」「送」「る」 •

    Bigram: 2文字単位 ⇒「敵に」「に塩」「塩を」「を送」「送る」 • Trigram: 3文字単位 ⇒「敵に塩」「に塩を」「塩を送」「を送る」 Q: Bigram で「塩」を検索可能?! A: No… 検索できない ⇒ N-gram ならば 2-1gram
  67. Ngram Tokenizer Unigram vs Trigram 「敵に塩を」 • 長さ3以上の term ならできることに変わりはなし(「塩」は検索できない)

    • どんどん大きくなると、完全一致のようになり、検索とは何か? という問題になる(6-gramでは「敵に塩を送」さえ検索できない) • 速度には差がでる(Unigram より Trigram の方が速い) 4個タームのマージ vs 2個のタームのマージ 「敵」「に」「塩」「を」vs 「敵に塩」「に塩を」 ※「に」「を」のPosting List などは非常に大きい(はず)
  68. Japanese Tokenizer(Kuromoji) 形態素解析エンジン。辞書ベースで分割。 「敵に塩を送った」 Surface form Part-of-Speech Base form Reading

    Pronunciation 敵 名詞,一般,*,* 敵 テキ テキ に 助詞,格助詞,一般,* に 二 二 塩 名詞,一般,*,* 塩 シオ シオ を 助詞,格助詞,一般,* を ヲ ヲ 送っ 動詞,自立,*,* 送る オクッ オクッ た 助動詞,*,*,* た タ タ
  69. Ngram vs 形態素解析 効果\方法 Ngram 形態素解析 取りこぼし: 「目黒」で「中目黒」 hit! =

    Good! No hit. = Bad… レレバンシー: 「京都」で「東京都」 hit! = Bad… No hit. = Good! Indexのサイズ 大 = Bad… 小 = Good! それぞれ、良いところと悪いところがある 解決策:両方をもつハイブリッド index
  70. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  71. コサイン類似度 価格 色 鮮度 商品A 商品B 商品C クエリー cos の値が

    • 1 に近ければ、類似している • 0 に近ければ、類似していない
  72. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  73. 理想の検索結果 C 実際の検索結果 B 再現率 A 再現率= C A 意味:どれほど網羅しているか?

    理想の検索結果(C)の内、実際の検索索結果とし て取得できた(A)割合
  74. 理想の検索結果 C 実際の検索結果 B 適合率と再現率 A 再現率= C A 適合率=

    B A • 適合率:正確性=ノイズを含まない比率 • 再現率:網羅性=取りこぼしが少ない比率
  75. C B 適合率と再現率 A 適合率↓ 再現率↓ 再現率= C A 適合率=

    B A 実際の検索結果 理想の検索結果 クエリー「東京都」
  76. C B 適合率と再現率 A 適合率↓ 再現率→ 再現率= C A 適合率=

    B A 実際の検索結果 理想の検索結果 クエリー「京都」
  77. C B 適合率と再現率 A 適合率↑ 再現率→ 再現率= C A 適合率=

    B A 実際の検索結果 理想の検索結果 クエリー「京都」
  78. 理想の検索結果 C 実際の検索結果 B A 再現率= C A 適合率= B

    A =1 • 実際の検索結果が 全て理想の検索結果 • ただし、取りこぼしが非常 に多い =理想の検索結果の一部 しか返却できていない なんでも正しい1件しか返却しない! ⇒ 最高 極端な適合率 • 適合率を上げれば再現率は下がり、 • 再現率を上げれば適合率が下がる。
  79. 理想の検索結果 C 実際の検索結果 B A =1 • 実際の検索結果が全ての 理想の検索結果が含まれ る

    • ただし、非常にノイズが多 い =理想の検索結果以外の 結果が多く含まれている 極端な再現率 • 適合率を上げれば再現率は下がり、 • 再現率を上げれば適合率が下がる。 適合率= B A 再現率= C A なんでも全件返却する! ⇒ 最高
  80. 理想の検索結果 C 実際の検索結果 B 適合率と再現率 A 再現率= C 適合率= B

    適合率(正確性)と再現率(網羅性)のバランスが重要 A A
  81. 0 5000000 10000000 15000000 20000000 25000000 1 2 3 4

    5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 検索結果の順位 (x軸)とクリック数 (y軸) のサンプル
  82. 結果:目黒 { "_score" : 656.68774, "_source" : { "nikki_kuromoji" :

    "雪の目黒", "nikki_ngram" : "雪の目黒“ } }, { "_score" : 23.361103, "_source" : { "nikki_kuromoji" : "雨の中目黒", "nikki_ngram" : "雨の中目黒“ } }
  83. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  84. TF-IDF and Okapi BM25b • 何なの? – アルゴリズム • 入力は?

    – 文章の集合 • 出力は? – 各文章の各単語にスコアを付与 • スコアは何を表すの? – 各文章の各単語の重要度
  85. TF-IDF and Okapi BM25b • 何なの? – アルゴリズム • 入力は?

    – 文章の集合 • 出力は? – 各文章の各単語にスコアを付与 • スコアは何を表すの? – 各文章の各単語の重要度 Linux: 0.3 Windows:0.1 ぶり: 4.2 Linux: 1.3 Windows:2.3 まぐろ: 3.8 Linux: 5.4 FreeBSD:10.3 大根: 2.1
  86. 2つの文章での「Linux」 Linux Linux(リナックス、他 の読みは後述)は、 UnixライクなOSカーネ ルである)。 OS オペレーティングシステム(英語: Operating System、

    OS、オーエス)とは、 コンピュータのオペレーション(操作・運 用・運転)のために、ソフトウェアの中で も基本的、中核的位置づけのシステム ソフトウェアである。通常、OSメーカーが 組み上げたコンピュータプログラムの集 合として、作成され提供されている。 … フリーなOSは、Linux、FreeBSD… … どちらの文章が「Linux」に関して重要度が高いか?! < 直感的 ? 定量的
  87. TF-IDF • TF=Term Frequency=Termの頻度 あるドキュメントの中で、どれだけそのTerm が出現したか? ⇒ いっぱい出てくる単語は重要だ • IDF:IDF=Inverse

    Document Frequency=逆文章頻度 あるTerm が全体の中でどれほどレアか? ⇒ レアな単語は重要だ • TF-IDF = TF×IDF あるドキュメント D の中の、Term T がどれほど重要か?は、 (TF: D の中でのT の頻出度)×(IDF: T の全体でのレア度)
  88. TF-IDF:IDF=Inverse Document Frequency=逆文章頻度 • Linux • である IDF = log

    Term T が現れる文章数 総文章数 • 野菜 • である • 野菜 • がある • Linux • がある • 肉 • である IDF(Linux) = log 2 5 = 0.39 IDF(である) = log 3 5 = 0.22 > 定量的 Linux である
  89. TF-IDF:IDF=Inverse Document Frequency=逆文章頻度 • 逆である意味は?! – 現れるドキュメントが、多ければ多いほど、重要度を下げたい (逆比例:「である」等は小、「しめ鯖」等は大) • log

    を取る意味は?! – 非常に大きな総文章数の場合のためのノーマライズ (ノーマラナイズしないとTFの意味がなくなる) IDF = log Term T が現れる文章数 総文章数
  90. TF-IDFの注意(良いところ) あるドキュメント D に対して Term が異なれば、TF-IDFも異なる しめ鯖 ⇒ 0.8492 Linux

    ⇒ 0.0234 月刊 Linux 2018/04/24 号 今月の月刊 Linux では、 カーネルの特集を… …ところでしめ鯖は美味し いですね。僕も…
  91. BM25: TF-IDFが不都合な場合 Linux Linux(リナックス、他 の読みは後述)は、 UnixライクなOSカーネ ルである)。 Linux Linux Linux

    Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux … TF(Linux) = 14,352 TF(Linux) =2 > これは不都合 注)IDFはどちらも一緒
  92. BM25: TF-IDFが不都合な場合 Linux Linux(リナックス、他 の読みは後述)は、 UnixライクなOSカーネ ルである)。 Linux Linux Linux

    Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux Linux … TF(Linux) = 14,352 TF(Linux) =2 > これは不都合 注)IDFはどちらも一緒 何が問題?! 単語数! 14,352 > 23
  93. BM25の定義 Linux Linux(リナックス、他 の読みは後述)は、 UnixライクなOSカーネ ルである)。 ・TF = 単語(Linux)の出現数 ・IDF

    = 単語レア度(Linuxのレア度) ・DL = ドキュメントの単語数(23) ・avgDL = 全てのドキュメントの単語数の平均 (=320) ・2つのパラメータk1, b k1 は 2 が最も最適と言われている b は 0.75 が最も最適と言われている BM25(Linux) =TF × IDF × TF+k1 ×(1-b+b× ) k1 + 1 avgDL DL
  94. BM25の意味 BM25(Linux) =TF × IDF × TF+k1 ×(1-b+b× ) k1

    + 1 avgDL DL 単に単語を沢山もつ場合は 減点↓ 単語を沢山もつ場合は 一つの単語の価値を減点↓ 単語を沢山もつ場合は減点だが それが平均に対して小さければ 加点↑ ・TF = 単語の出現数 ・IDF = 単語レア度 ・DL = ドキュメントの単語数 ・avgDL = 全てのドキュメントの単語数の平均
  95. BM25 and TF-IDF Linux はフリー のOSカーネル であり、… FreeBSDは Unix系のオー プンソースの

    … 今年のじゃがい もはとても不作 だった。 日本ではこの時 期のブリを特に 「寒ブリ」と呼ぶ • Linux: 23 • OS: 11 • カーネル: 17 • は: 0.331 • あり: 3.65 • の: 0.003 • です: 0.0001 • は: 0.000053 • の: 0.023 • FreeBSD: 65 • OS: 9 • カーネル: 5 • じゃがいも: 42 • 不作: 58 • 今年: 2 • だった:0.003 • は: 0.00428 • の: 0.00084 • 寒ブリ: 90 • 日本: 3 • 時期: 1.8 • 特に: 0.2 • の: 0.00189 レアではないワードはスコア小 特徴的 Term はスコア大
  96. 結果:目黒 { "_score" : 656.68774, "_source" : { "nikki_kuromoji" :

    "雪の目黒", "nikki_ngram" : "雪の目黒“ } }, { "_score" : 23.361103, "_source" : { "nikki_kuromoji" : "雨の中目黒", "nikki_ngram" : "雨の中目黒“ } }
  97. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  98. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  99. nDCG • nDCG (= normalized Discounted Cumulative Gain) • 直訳すると「正規化された効果減少の累積報酬」

    • ランキングの精度評価指標 • ランキングを行うシステムの評価に利用できるので、 特に、検索だけがターゲットではない。 例)レコメンドシステム、広告システム • nDCG も理想のランキングとの乖離具合を数値化
  100. nDCG:実際の検索結果 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!

    【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子
  101. nDCG:実際のカスタマーの行動 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!

    【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入
  102. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  103. nDCG:実際のカスタマーの行動 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!

    【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入
  104. nDCG:実際のカスタマーの行動 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!

    【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 2位なのに 頑張っている 4位なのに 断トツ 1位なのにたいしたことない ③が上って どういうこと?!
  105. nDCG:実際の結果 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!

    【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入
  106. nDCG:理想の結果 クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!

    【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入
  107. nDCG:理想の結果(並べ替えだけでは不十分) クエリー「からし明太子」 ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!

    【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 元々1位だったアド バンテージを考慮し ていない
  108. nDCG:スコア ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子! 【送料無料】てんこ盛り

    訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 1. 各順位の結果はスコアをもっている (例 クリック数+購入数×100) S1=150 S2=110 S3=45 S5=60 S4=250
  109. nDCG:Top5 の DCG ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1

    明太子! 【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 2. 各順位に応じて、ペナルティ を与え、全体のスコアを計算 DCG5= S1 + + + … log2 S2 log3 S3
  110. nDCG:理想の結果のDCG=iDCG (ideal DCG) ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1

    明太子! 【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 3. スコア順のDCG = iDCG を求める ⇒ DCG が MAX
  111. 現実の DCG ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!

    【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 DCG5= S1 + + + … = 439.23 log2 S2 log3 S3
  112. 理想の DCG ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!

    【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 DCG5= S1 + + + … = 518.78 log2 S2 log3 S3
  113. ちょっと改善した DCG ① 送料無料 福岡加工 辛子明太子 ゴールデンサイズ ② 当店人気No.1 明太子!

    【送料無料】てんこ盛り 訳あり ③ からし明太子高菜 80g×2パック ④【送料無料】かねふく ★極上 辛子明太子 1kg ⑤ マ・マー あえるだけ パスタソース 逸品 からし明太子 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 DCG5= S1 + + + … = 489.23 log2 S2 log3 S3
  114. nDCG の違い クリック 購入 クリック 購入 クリック 購入 クリック 購入

    クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 nDCG=0.84 nDCG=0.94
  115. MLR= Machine Learning Ranking クリック 購入 クリック 購入 クリック 購入

    クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 クリック 購入 クリック 購入 クリック 購入 クリック 購入 クリック 購入 S1=150 S2=110 S3=45 S5=60 S4=250 nDCG=0.84 nDCG=1.00 理想を目指してパラメータ調整
  116. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  117. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?
  118. ジャンルにヒットしたらスコアを上げる • filter がメインの検索 (「鈴木」さんを検索) • bool が関連のあるワードとのマッチによるスコアアップ (「野球」や「MLB」に関連する方) {

    "query": { "bool": { "should": [ { "match_phrase": { "contents": { "boost":1000, "query": "野球" } } }, { "match_phrase": { "contents": { "boost":1000, "query": "MLB” } } } ], "minimum_should_match": 0, "filter": { "bool": { "should": [ { "match_phrase": { "contents": "鈴木" } } ] } } } } }
  119. アジェンダ • 検索とは何か? • 転置インデックスとは何か? • 転置インデックスを実装するには? • 分散検索とは何か? •

    Term とは何か? • 良い検索結果とは何か? • 検索結果のスコアとは何か? • 良いランキングとは何か? • 良いランキングを作るとは何か?