学術論文の実装: ElasticsearchとLuceneから学んだ教訓

主要AIや機械学習プラットフォームとシームレスに連携できます。無料のクラウドトライアルを開始してElasticの生成AI機能を探索するか、今すぐローカルマシンでお試しください。

この投稿では、学術論文をソフトウェア アプリケーションに実装するための戦略を紹介します。他のエンジニアが私たちの経験から学べるよう、Elasticsearch と Lucene の例を参考にしています。これらの戦略を読んで、「でもこれは単なるソフトウェア開発だ！」と思うかもしれません。そしてそれは確かに真実です。エンジニアとして私たちはすでに適切な方法とツールを持っており、それらを新たな課題に適応させる必要があるだけです。

背景

Elasticsearch を開発しているときに、解決するための単純なアプローチや確立されたアプローチがない重要な問題に遭遇することがあります。「うーん、これについて言及している学術論文はあるのだろうか？」と疑問に思うのは当然です。時には、学術的な仕事がインスピレーションの源となることもあります。新しいアルゴリズムやデータ構造を提案する論文に出会うと、「これはとても便利だろう！」と思うでしょう。Elasticsearch と Apache Lucene が学術研究にどのように組み込まれているか、いくつかの例を次に示します。

• カーディナリティ集計 のための HyperLogLog++
• 適応型レプリカ選択 のための C3アルゴリズム
• Lucene における最近傍ベクトル検索のための階層的ナビゲート可能スモールワールドグラフ (HNSW)
• 機械学習の分類を改善する ための MIC統計
• Lucene でトップヒット検索を高速化 する ブロック最大 WAND
• ... その他 多数

学術論文は、データ集約型システムを開発するエンジニアにとって貴重なリソースです。しかし、それらを実装するのは困難で、エラーが発生しやすくなります。アルゴリズムの説明は複雑であることが多く、重要な実用的な詳細が省略されています。そして、テストは本当に難しいです。たとえば、出力がデータセットに大きく依存する機械学習アルゴリズムを徹底的にテストするにはどうすればよいでしょうか。

ソフトウェアの依存関係と同じように論文を評価する

新しいソフトウェア依存関係を追加するには、慎重な評価が必要です。他のパッケージが正しくなかったり、速度が遅かったり、安全でなかったりする場合は、プロジェクトも同様になる可能性があります。依存関係を導入する前に、開発者は必ずその品質を評価します。

実装を検討している学術論文にも同じことが当てはまります。アルゴリズムが論文で発表されているので、そのアルゴリズムは正しく、パフォーマンスも優れているに違いないと思われるかもしれません。しかし、査読プロセスに合格したとしても、学術論文には問題がある可能性があります。おそらく、正しさの証明は現実的ではない仮定に依存しているのでしょう。あるいは、「実験」セクションではベースラインよりもはるかに優れたパフォーマンスが示されていますが、これは特定のデータセットにのみ当てはまります。たとえ論文の質が優れていたとしても、そのアプローチがプロジェクトに適していない可能性があります。

学術論文に「依存」するかどうかを考えるときは、ソフトウェア パッケージの場合と同じ質問をすると役立ちます。

• ライブラリは広く使用され、「実戦テスト済み」ですか?→ 他のパッケージでもこの論文は実装されていますか? また、うまく機能しましたか?
• パフォーマンスベンチマークは利用可能ですか?これらは正確かつ公平と思われますか?→論文には現実的な実験が含まれていますか？それらはうまく設計されていますか?
• パフォーマンスの改善は複雑さを正当化するほど大きいですか?→ この論文は強力なベースラインアプローチに匹敵しますか?このベースラインをどれだけ上回るのでしょうか?
• このアプローチは当社のシステムとうまく統合されるでしょうか?→ アルゴリズムの前提とトレードオフは、私たちのユースケースに適合していますか?

どういうわけか、ソフトウェア パッケージが競合製品とのパフォーマンス比較を公開すると、そのパッケージが常に最速であると出てきます。第三者がベンチマークを設計した場合、よりバランスが取れる可能性があります。同じ現象が学術論文にも当てはまります。アルゴリズムが元の論文だけでなく、他の論文でも強力なベースラインとして優れたパフォーマンスを示している場合、そのアルゴリズムは信頼できる可能性が非常に高くなります。

テストを創造的に行う

学術論文のアルゴリズムは、私たちが日常的に目にするタイプのアルゴリズムよりも動作が洗練されていることがよくあります。おそらく、これは精度と引き換えに速度を向上させる近似アルゴリズムです。あるいは、大規模なデータセットを取り込み、（場合によっては予期しない）出力を生成する機械学習の手法である可能性もあります。アルゴリズムの動作を単純な方法で特徴付けることができない場合、これらのアルゴリズムのテストをどのように記述できるでしょうか?

不変量に焦点を当てる

ユニット テストを設計するときは、例に基づいて考えるのがよくあります。つまり、アルゴリズムにこの例の入力を与えると、その出力が得られるはずです。残念ながら、ほとんどの数学アルゴリズムでは、例に基づくテストではその動作を十分にカバーできません。

Elasticsearch が検索リクエストをどのノードが処理すべきかを判断するために使用する C3 アルゴリズムを考えてみましょう。ノードの以前のサービスと応答時間、およびキュー サイズを組み込んだ微妙な計算式を使用して各ノードをランク付けします。いくつかの例をテストしても、式を正しく理解できたかどうかは実際には確認できません。一歩下がって不変条件のテストについて考えてみると役に立ちます。サービス時間が長くなると、ノードのランクは下がりますか?キューのサイズが 0 の場合、論文で主張されているように、ランクは応答時間によって決定されますか?

不変条件に焦点を当てると、次のような多くの一般的なケースで役立ちます。

• このメソッドは順序に依存しないものになるのでしょうか?もしそうなら、入力データを異なる順序で渡すと同じ出力が得られるはずです。
• アルゴリズムの何らかのステップでクラス確率が生成されますか?もしそうなら、これらの確率の合計は 1 になるはずです。
• 関数は原点を中心に対称ですか?もしそうなら、入力の符号を反転すると、出力の符号も単に反転するはずです。

C3 を初めて実装したとき、式にバグがあり、応答時間の代わりに応答時間の逆数を誤って使用していました。つまり、より遅いノードの方が上位にランク付けされる可能性があるということです。問題を修正する際には、将来のミスを防ぐために不変チェックを追加するようにしました。

リファレンス実装と比較する

論文とともに、著者らはアルゴリズムの実装も公開したようです。(論文に実験が含まれている場合は特にこの可能性が高くなります。多くのジャーナルでは、著者が結果を再現するためのコードを投稿することを求めているためです。)このリファレンス実装に対してアプローチをテストし、アルゴリズムの重要な詳細を見逃していないことを確認できます。

最近傍検索用の Lucene HNSW 実装を開発する際に、論文の著者による参照ライブラリに対してテストを行いました。同じデータセットに対して Lucene とライブラリの両方を実行し、結果の精度と実行された計算の数を比較しました。これらの数値がほぼ一致する場合、Lucene がアルゴリズムを忠実に実装していることがわかります。

アルゴリズムをシステムに組み込む場合、複数のコアに拡張したり、パフォーマンスを向上させるためにヒューリスティックを追加したりするなど、変更や拡張を行う必要があることがよくあります。最初に「バニラ」バージョンを実装し、リファレンスに対してテストしてから、段階的な変更を加えるのが最適です。そうすれば、カスタマイズを行う前に、すべての重要な部分を確実にキャプチャできます。

既存のアルゴリズムとの決闘

最後のセクションでは、テスト不変条件の別のアイデアとして、アルゴリズムの出力を、より単純で理解しやすいアルゴリズムの出力と比較する方法について説明します。例として、上位の結果に表示されないドキュメントをスキップすることでドキュメントの検索を高速化する、Lucene の block-max WAND アルゴリズムを考えてみましょう。block-max WAND があらゆるケースでどのように動作するかを正確に説明することは困難ですが、これを適用しても上位の結果は変わらないはずです。したがって、テストではランダムな検索クエリをいくつか生成し、それらを WAND 最適化ありとなしの両方で実行して、結果が常に一致することを確認できます。

これらのテストの重要な側面は、比較を実行するためのランダムな入力を生成することです。これにより、思いもよらなかったケースを練習したり、予期しない問題を明らかにしたりすることができます。たとえば、Lucene の BM25F スコアリングのランダム化比較テストは、微妙なエッジ ケースのバグを検出するのに役立ちました。アルゴリズムにランダムな入力を与えるという考え方には、コンピューター セキュリティの一般的なテスト手法であるファジングの概念との密接な関係があります。

Elasticsearch と Lucene では、このテスト手法が頻繁に使用されます。2 つのアルゴリズム (TestDuelingAnalyzers、testDuelTermsQuery...) 間の「決闘」について言及しているテストを見ると、この戦略が実行中であることがわかります。

論文の用語を使用する

他の開発者があなたのコードで作業する場合、詳細を理解するために論文を参照する必要があります。Elasticsearch の HyperLogLog++ 実装に関するコメントは、次のようにうまく表現しています。「論文を読まずにこのクラスが何をするかを理解しようとするのは冒険的だと見なされます。」このメソッドのコメントも良い例を示しています。学術論文へのリンクが含まれており、元々説明されていたアルゴリズムにどのような変更が加えられたかが強調されています。

開発者は紙に基づいてコードを理解するので、まったく同じ用語を使用すると便利です。数学表記は簡潔なので、通常は「適切なスタイル」とは見なされない名前になることもありますが、論文の文脈では非常に明確になります。学術論文の数式は、Elasticsearch でrS や muBarSInverseのような難解な変数名に遭遇する数少ない例の 1 つです。

著者が推奨する論文の読み方は、大きなコーヒーを飲みながら読むことです。

著者にメールを送ることができます

難しい論文に取り組むとき、誤解しているのか、それとも単なるタイプミスなのかわからず、数式について頭を悩ませるのに何時間も費やすことがあります。これがオープンソース プロジェクトであれば、GitHub または StackOverflow で質問することができます。しかし、学術論文はどこで入手できるのでしょうか?著者は忙しそうなので、あなたのメールにイライラするかもしれません。

それどころか、多くの学者は自分のアイデアが実践されていると聞くことを喜び、メールで質問に喜んで答えてくれます。彼らが精通している製品に取り組んでいる場合は、そのアプリケーションが彼らの Web サイトに掲載される可能性もあります。

また、ソフトウェア開発で使用したのと同じツールの多くを使用して、研究者が論文を公開して議論する傾向も高まっています。論文にソフトウェア パッケージが付属している場合は、 Github でよくある質問への回答が見つかることがあります。「理論計算機科学」や「Cross Validated」などの Stack Exchange コミュニティにも、人気のある論文に関する詳細な議論が含まれています。一部の会議では、すべての論文レビューをオンラインで公開し始めています。これらのレビューには著者との双方向の議論が含まれており、アプローチに関する役立つ洞察が得られる可能性があります。

つづく

この投稿では、学術論文の選び方の基本に焦点を当て、

正しく実装しますが、アルゴリズムを実際に展開するすべての側面をカバーしているわけではありません。たとえば、アルゴリズムが複雑なシステムの 1 つのコンポーネントにすぎない場合、そのコンポーネントへの変更がエンドツーエンドの改善につながることをどのように保証すればよいでしょうか。また、アルゴリズムを統合するために、元の論文でカバーされていない大幅な変更や拡張が必要な場合はどうなるでしょうか?これらは重要なトピックであり、今後の投稿でさらに詳しく共有したいと考えています。