OpenSearch における 10 億規模のユースケースに適した k-NN アルゴリズムの選定 | Amazon Web Services
Amazon Web Services ブログ OpenSearch における 10 億規模のユースケースに適した k-NN アルゴリズムの選定 この記事は、Choose the k-NN algorithm for your billion-scale use case with OpenSearch を翻訳したものです。 自然言語処理 (NLP) システムや、レコメンドエンジン、または検索システムなどの機械学習 (ML) アプリケーションを構築しようとすると、ワークフローのどこかで k 最近傍 (k-NN) 検索アルゴリズムを使用することがよくあります。データポイントの数が数億や数十億に達すると、k-NN 検索システムのスケーリングが大きな課題となります。近似最近傍 (ANN) 検索アルゴリズムは、この課題を解決するための優れた方法の 1 つです。 k-NN は、他の ML の技術と比
Hierarchical Navigable Small Worlds (HNSW) | Pinecone
Hierarchical Navigable Small World (HNSW) graphs are among the top-performing indexes for vector similarity search[1]. HNSW is a hugely popular technology that time and time again produces state-of-the-art performance with super fast search speeds and fantastic recall. Yet despite being a popular and robust algorithm for approximate nearest neighbors (ANN) searches, understanding how it works is f
RAGにおけるドキュメント検索精度向上について(概要編)
はじめまして。損害保険ジャパン株式会社 DX推進部の眞方です。普段はリードエンジニアとして、新しいサービスのアーキテクチャ検討からローンチまでの作業や、新規技術を用いたアプリのプロトタイプ実装などを行なっています。 弊社では、LLM（Large Language Models）を活用したアプリケーションの開発を積極的に検討し、既に社内でいくつかのプロトタイプをローンチしています。 本記事では、その最も一般的？なユースケースの一つとも言えるRAG（Retrieval Augmented Generative）の構築において、ドキュメント検索精度の向上にどのように取り組んだ内容の概要を紹介させていただきます。実際の詳細な手法および結果については、別記事（実践編）で解説予定です。 はじめに RAGとは？ この記事を読まれている方の中にはご存知の方も多いでしょうが、RAGとはRetrieval A
BM25を数式から説明する - Qiita
はじめに BM25は特に検索アルゴリズムに使われる自然言語処理の一つで、tf-idfの進化系である。具体的には単語の出現頻度に基づいて、文章の順位付けを行う。tf-idfとの違いはドキュメントが短いほど順位が高くつき、長いほど順位が低くつく傾向があるというところである。この記事では数式を紐どいて、BM25の性質を説明する。 数式 BM25の数式についてまず説明する。$D$を文章全体の集合(以下全文章と呼ぶ)、$d$は文章であり$D$の要素、$q$を検索クエリ($q_i\in q$)とした時のBM25の数式は以下のようなものである。 $$ score(q, d) = \sum_i idf(q_i)\times\frac{(k_1+1)f(q_i, d)}{f(q_i, d)+k_1(1-b+b\frac{|d|}{avg(dl)})} $$ $idf(q_i)$は単語$q_i$のidf、$f
GeoTools で地球地図起源の海岸線データを単純化する その３ - Relevant, Timely, and Accurate
d:id:hfu:20071211, d:id:hfu:20071212 の続きとして、ポリゴンの単純化を実際にやってみました。 geotools.rb の改変 geotools.rb を改変し、ポリゴンの単純化に必要なクラスを取り込むようにしました。このエントリのスクリプトを実行するには、http://svgmapdata.sakura.ne.jp/geotools/ にある geotools.rb (Time-stamp: <2007-12-13 05 : 47 : 35 hfu> 以降)を使ってください。 ポリゴンの単純化に必要なクラスとは ポリゴンの単純化をしてくれるクラスには以下の２つがあります： com.vividsolutions.jts.simplify.DouglasPeuckerSimplifier 地図学的なベクトルデータの単純化アルゴリズムとしては古典的であるらしい
ビンパッキング問題の解き方 - Qiita
組合せ最適化問題の解き方の工夫 組合せ最適化問題では、特有の難しさがあります。同じ問題であっても複数のモデル化の方法があり、モデルごとに優劣があります。モデル化の仕方が重要になります。 ここでは、ビンパッキング問題を例に、工夫の仕方を説明します。 ビンパッキング問題とは 容量$c(\gt 0)$の箱と$n$個の荷物$N=\{1,\dots,n\}$が与えられている。荷物$i \in N$の容量を$w_i(\gt 0)$とする。全ての荷物を詰合わせるのに必要な箱の個数を最小にする詰合わせを求めよ。
ビンパッキング問題 - Wikipedia
ビンパッキング問題（ビンパッキングもんだい）とは、離散数学の組合せ論の中のNP困難問題で、与えられた「荷物（重さや個数がついている）」をつめる「箱（ビンやコンテナなど）」の最小数を見つけるものである。問題を解くためにビン型（筒状型）の模型を使うのでこのように呼ばれる。 様々な解決方法（アルゴリズム）が考案されているが、あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない（NP困難問題）。 8台の新車をトラックで移動する。新車の重量はそれぞれ100キログラム単位で 33, 61, 58, 41, 50, 21, 60, 64 である。各トラックが、12,000 kg の重量まで運べるとき、全ての新車を一度に移動させるのに必要とされるトラックの最小数は、いくつであるか考える。まず、トラックを容量120のビンとし、新車は、そのビンに詰める荷物とする。具体的に調べる
A* - Wikipedia
A*探索アルゴリズム A*（A-star、エースター）探索アルゴリズム（エースターたんさくアルゴリズム）は、グラフ探索アルゴリズムの一つ。 最良優先探索を拡張したZ*に、さらにf値として「現時点までの距離」g と「ゴールまでの推定値」h の和を採用したもの[1]。h は ヒューリスティック関数と呼ばれる。 A* アルゴリズムは、「グラフ上でスタートからゴールまでの道を見つける」というグラフ探索問題において、 ヒューリスティック関数 h(n) という探索の道標となる関数を用いて探索を行うアルゴリズムである。h は各頂点 n からゴールまでの距離のある妥当な推定値を返す関数で、解くグラフ探索問題の種類に応じてさまざまな h を設計することが出来る。 例えば、カーナビなどで用いられる単純な二次元の地図での探索では、h としてユークリッド距離 を使うことができ、この値は道に沿った実際の距離のおおま
「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記
最近，量子コンピュータの話題をニュースや新聞で見かけることが増えてきました． その中で気になってきたのが，組合せ最適化と量子コンピュータ（特に量子アニーリング）に関する怪しい言説．私自身は（古典コンピュータでの）組合せ最適化の研究をやってきて，量子コンピュータを研究しているわけではないのですが，さすがにこれはちょっと・・・と思う言説を何回か見かけてきました． 最近の「量子」に対する過熱ぶりは凄まじいので，こういう怪しい言説が広まるのは困りものです．すでにTwitter上には，“組合せ最適化は今のコンピュータでは解けない”とか“でも量子なら一瞬で解ける”という勘違いをしてしまっている人が多数見られます*1． さすがに危機感を覚えてきたので，この場できちんと指摘しておくことにしました． 今北産業(TL;DR) “古典コンピュータは組合せ最適化を解けない” → 古典コンピュータで組合せ最適化を解
H.264の秘密 | POSTD
(編注：2020/08/18、いただいたフィードバックをもとに記事を修正いたしました。) (2016/12/11、いただきましたフィードバックをもとに翻訳を修正いたしました。) H.264は、動画圧縮コーデックの標準規格です。ネット上の動画、Blu-ray、スマホ、セキュリティカメラ、ドローンなどなど、今やあらゆるところでH.264が使われています。 H.264は注目すべき技術のひとつです。たったひとつの目標、つまりフルモーションビデオの送信に要するネットワーク帯域を削減することを目指した30年以上の努力の結晶なのです。 技術的な面でも、H.264はとても興味深い規格です。この記事では、その一部について概要レベルでの知識を得られることでしょう。あまり複雑だと感じさせないようにするつもりです。今回おはなしする概念の多くは動画圧縮全般にあてはまるものであり、H.264に限ったものではありません
ブロックアルゴリズムとB-Treeアルゴリズム
後で説明するが、ext2ではブロックグループ0の「スーパーブロック」に、パーティション内のブロックグループ全体の管理情報が格納される。 スーパーブロックには、 iノードの総数 ブロックサイズ ファイルシステムのサイズ 空きブロック数、空きiノード数 使用されているブロックグループ 最終fsck時刻 など、ファイルシステムに関するさまざまな情報が含まれている。「グループディスクリプタ」は、「データブロックビットマップ」や「iノードビットマップ」情報などを参照して空きブロックや空きiノードを探し、データを割り当てる際に最適なブロックを決定するのに使われる。 「データブロックビットマップ」と「iノードビットマップ」は、ビットマップ情報である。ビットマップ情報は、あるデータが使用中か未使用かを0か1のbitで保持している。1byte＝8bitsなので、80個のブロックの状態を10bytesで管理で
横着プログラミング 第6回: chatty: 小うるさい端末
最終更新日: 2002-09-18 (公開日: 2002-09-18) Unix Magazine 誌に 2002年1月号から 2003年2月号にかけて連載し ていた記事の元の原稿です。 才気に富んだことは個人が行うのが通例であり、信じがたきバカ さ加減は大抵組織に帰されるものである。 -- Jon Bentley *1 役に立たないソフトウェアを作るのが好きだ。面倒な作業を楽にす る横着ソフトウェアもいいが、たまには人を呆れさせるくだらない ソフトウェアを作るのも楽しい。 以前に私が開発した cdbiff*2というソフト ウェアは、メールが届くと PC の CD-ROMドライブが開いてメール の到着を通知するという役に立たないものであったが、そのくだら なさが受けて予想外の好評を得た。今回は、そうした役に立たない ソフトウェアの 1つである、小うるさい端末 chatty*3 を紹介する。
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
綱引きに蛇口当てゲーム？！ 楽しく学ぶベイズフィルターの仕組み
付き合いたくないスパムと付き合うために 受信者の意向を無視して、一方的に送りつけられる迷惑メール（スパム）は、いまやメールボックスを雑音でいっぱいにしてしまい、大事なメールを見過ごしかねないほどの量に膨れ上がり、大きな問題となっています。 残念ながら、このようなスパムを発生源から断つような根本的な対策はいまだになく、私たちは、せめてメールサーバで受け取った大量のメール群からスパムと大事なメールを仕分けしてくれる仕組みに頼らざるを得ません。 スパムを判定する方法は、次の2つに大別することができます。 本稿では前者の方法に着目します。メールを受け取った人にとっては、メールの中身を読めば、そのメールがスパムかそうでないかを判定するのは容易なことです。スパムの定義は、メールを読む人によって変わる可能性があります。例えば、まったくゴルフをしない人にゴルフの勧誘メールが来た場合はスパムといえるでしょう
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://arxiv.org/pdf/2212.10496.pdf
GitHub - erikbern/ann-benchmarks: Benchmarks of approximate nearest neighbor libraries in Python
Simplify — GeoTools 31-SNAPSHOT User Guide
ラインの単純化
https://www.ibm.com/downloads/cas/DLPX0P1V
パッキング問題 | opt100