世界を動かす技術を、日本語で。

ゼロから作るシンプルな検索エンジン

概要

  • 本記事では Word2Vec を活用した 独自検索エンジン の構築過程を解説。
  • 単語埋め込みコサイン類似度 による検索ランキング生成を詳細に説明。
  • Pythonによる REPL型検索 から Webフロントエンド への発展を紹介。
  • 効率的なデータ配信クライアントサイド処理 の工夫について言及。
  • 最後に、 検索精度の評価方法 についても触れる。

Word2Vecによるブログ検索エンジン自作記

Word2Vecの概要と検索エンジンの発想

  • Word2Vec は、単語を N次元空間(例:N=300) にマッピングする手法で、各次元が意味軸に対応することを利用すること。
  • Word2Vec from Scratch というブログ記事を参考に、内部構造や学習方法を理解すること。
  • 各ブログ記事を 単語埋め込みの総和 で表現し、検索クエリも同様に埋め込むことで、 ベクトル間の類似度 でランキングを生成すること。
  • コサイン類似度 を用いて、ベクトルの向き(意味の近さ)を評価することが直感的かつ適切であることを確認。
  • ユークリッド距離 も考えられるが、意味の一致にはコサイン類似度が優れると判断すること。

単語埋め込みデータの利用と実装

  • 10,000語のWord2Vec埋め込みデータ (12MBのpickleファイル)をChrisから受け取り、NumPy辞書形式で管理すること。
  • pickleライブラリ でデータを読み込み、必要に応じてPythonのリスト形式に変換すること。
  • 単語の埋め込みは辞書lookup、未知語はNoneを返すことでエラー回避すること。
  • 複数単語の埋め込みは、各単語の埋め込みベクトルを 要素ごとに加算 して表現すること。
  • すべての単語が未知語の場合は SyntaxError を発生させること。

ブログ記事全体の埋め込みと正規化

  • ディレクトリ再帰走査 で全Markdown記事(_posts配下)を対象に、記事ごとに単語リストを抽出すること。
  • 正規化関数(normalize_text) で大文字・記号等を除去し、単語の一貫性を確保すること。
  • 各記事の単語リストから 記事埋め込みベクトル を作成し、pickleで保存すること。

PythonによるREPL型検索インターフェース

  • code.InteractiveConsole を継承し、REPL形式で検索クエリを受け付けるSearchReplクラスを実装すること。
  • クエリ入力時、正規化→埋め込み→各記事との コサイン類似度計算 →ランキング上位N件を返すこと。
  • ベクトルのノルム計算コサイン類似度計算 はPythonで簡潔に実装できることを確認すること。
  • REPL起動時は、プロンプトやバナーをカスタマイズして利用者体験を向上させること。

Webフロントエンド化と効率的データ配信

  • ブラウザで動作するように Webフロントエンド を構築することが必要と判断すること。
  • 巨大なword2vecデータ をそのまま配信せず、 埋め込みデータ(vecs.jsonl)インデックス(index.json) に分割し、必要な部分のみHTTP Rangeリクエストで取得すること。
  • index.json は全語のバイト位置・長さのみを保持し、クライアントは必要な単語分だけvecs.jsonlから部分取得すること。
  • post_embeddings.json も分割・圧縮してキャッシュ可能にすることで、Web配信の効率化を図ること。
  • JavaScriptで 検索クエリの正規化・分割・埋め込み取得・類似度計算・ランキング表示 を実装すること。

検索精度の評価方法

  • 検索アルゴリズムの有効性 を評価するため、適切な評価データセットと定量的指標を設計すること。
  • Word2Vec埋め込み利用時単純なキーワード検索 との比較で、検索品質の向上を確認すること。

このように、 Word2Vec を活用した検索エンジンの自作過程を通じて、 単語埋め込み・コサイン類似度・効率的なデータ配信・Webフロントエンド の技術的工夫と実践例を学ぶことができる。

Hackerたちの意見

検索エンジンの話題で言うと、デイビッド・エバンスの授業がすごく良かったよ。課題は、ゼロからシンプルな検索エンジンを作ることだったんだけど、初心者向けにコーディング全般に重点を置いてるから、すごく取り組みやすかった。

SeIRPの本は、PDFで無料オンラインにあるし、従来の検索エンジンや情報検索一般についての素晴らしいリソースだよ。

死んだリンクのせいで、こっちのURLの方が適切だね。

Udacityの実際のコースリンクは404エラーだね。

特定のトピックに特化した検索エンジンが復活することってあるのかなっていつも思う。LLMがいくつかの分野であまり正確じゃない結果を出してるし、GoogleやBingなんかも広告やうまく整理されたSEOに支配されてるから、正確で専門的な検索が求められてる気がする。

ニッチな検索には、リソースのインデックスをキュレーションすることが必要だよね。

大体のトピックはもう直接Wikipediaで検索してるよ(URLバーにショートカットを設定してる)。

そうだね、KagiやMarginaliaの(相対的な)台頭は、技術的な観点から見ると、熱心な趣味者の手の届く範囲にあることを示してる。[1] Googleが今のままの進み方を続けて、AIクローラーの数がCAPTCHAページの急増を引き起こさない限り、少数の人がコンテンツをキュレーションして、現在の一般的なWeb検索エンジンよりもはるかに良い体験を提供できるようなニッチな検索エンジンが復活することを期待してる。自己宣伝だけど、俺はリビングでプログラマー向けのそんな検索エンジンを運営してるよ、https://search.feep.dev/>。あまりメンテナンスに時間をかけてないから、ほんとに熱心な人が何をするのか見てみたいな。[1] 2004年と2014年の比較を書いたけど、その後はどんどん良くなってるよ:https://search.feep.dev/blog/post/2022-07-23-write-your-own

SVGの数式は、ダークOSテーマを使ってると読みづらいよね。ブログがOSのダーク/ライトテーマの設定を使ってるから、手動で変更するオプションもないみたいだし。

修正したと思うけど?教えてね。

OPを批判するつもりはないけど、「コサイン類似度」って言葉が嫌いで、みんなが「正規化された内積」って呼んでくれたらいいのにって思う。大学の2年生レベルの微積分を取った人ならわかるはずなのに、結局みんな新しい言葉を作っちゃったね。

これは本当に面白い読み物だった。これでブログの検索をアップグレードしない理由がなくなったな。たくさんのロングテールワード、例えば「いたずら」とかが出てくる気がする。

いいアイデアだけど、このアプローチは語彙外の単語に対してあまりうまく対処できないんだよね。これがベクトルベースの検索を使う大きな理由の一つなんだ。tf-idfやBM25のような語彙マッチングと比べて、そんなにパフォーマンスが良くなるわけでもないし、線形の複雑さのせいで遅くなるかもしれない。でも、クールではあるね。

シンプルな検索エンジンであるべきだよ。キーワードはシンプル。シンプルな検索エンジンとしてちゃんと機能してれば、それでいいんじゃないかな。

それをwordvecでどう扱うつもり?そして、同義語が正しく処理されるのが大きな利点じゃない?この実装はまだその利点を持ってるよ。

OPはコサイン類似度マッチングとナイーブマッチングの両方を持ってるから、両者の弱点を補うようなヒューリスティックな組み合わせができるね。

ベクトルベースのアプローチは、OOV用語を全く扱えないか、実装によってはパフォーマンスが悪くなることがあるよ。例えば、アルファベットと数字のトライグラムに制限すると、技術的にはすべての用語をカバーできるけど、トレーニングデータによってはうまくいかないこともある。

これはword2vecで単語を埋め込んでるけど、もう10年も前の技術だよ。せめてBERTかsentencetransformersを使おうよ :)

最近、単語ベクトルを使うのと比べてどれだけ理にかなってるか考えてたんだけど、従来のクエリはすごく短くてキーワードベース(例えば「合挽き肉」を検索して「今夜簡単に作れる合挽き肉レシピ」を探すみたいな)だから、BERTやそれに似たものが提供する文脈がほとんど欠けてるんだよね。クエリ用に別の埋め込みを使う方法もあるけど、基本的な単語ベースの検索がもっと役立つかもしれない、特にout of vocabularyの用語に対してfastTextみたいなものを使うと。

[死んでる]

この検索エンジンのアイデアは、投稿内の単語の埋め込みを足し合わせて、各投稿をこのドメインに埋め込むことなんだ。ああ、なるほど!単語レベルの埋め込みの使い方が今までよくわからなかったけど、今はもっと理解できた。

「grokked」って今は一般的な動詞なの?ムスクのAIが出るまでこの言葉すら聞いたことなかったよ。

多くの人が当たり前だと思っている技術で遊んでいる人たちが好きだな、核心的な原則を理解していないけど。

著者はLispのコンパイルに関するいいシリーズを持ってるけど、残念ながら彼の検索エンジンは「lisp」や「Lisp」でクエリしても見つけられないんだよね。[0] https://bernsteinbear.com/blog/compiling-a-lisp-0/

それってトップ10,000単語に入ってないだけなんじゃないかな :/