グラフを用いた近似最近傍探索の理論と応用
NLP若手の会 (YANS) 第18回シンポジウム (2023) チュートリアル https://yans.anlp.jp/entry/yans2023 松井 勇佑（東京大学）https://yusukematsui.me/ 近似最近傍探索とは、「似ているベクトルを探す」というシンプルかつ基盤的な技術である。近傍探索技術は古くから様々な分野で研究が進められてきたが、現在でも活発に技術革新が進んでいる。近年ではCLIPを用いたマルチモーダル検索や、埋め込み探索によるLLMへの知識追加方式として、近傍探索技術は注目を集めている。本チュートリアルでは、特に2010年代後半から目覚ましく発展を遂げ、多くのVector Databaseのバックエンドにもなっている「グラフを用いた探索方式」に焦点を当て、その理論と応用について解説する。
中日新聞:自動車工場のガロア体 ＱＲコードはどう動くか
その誕生を地元新聞も経済新聞も記事にしなかった。２年後、『コードの情報を白黒の点の組み合わせに置き換える』と最下段のベタ記事で初めて紹介された時、その形を思い浮かべることができる読者はいなかった。いま、説明の必要すらない。ＱＲコードはなぜ開発され、どう動くのだろうか。 ＱＲコードは、自動車生産ラインの切実な要請と非自動車部門の技術者の「世界標準の発明をしたい」という野心の微妙な混交の下、1990年代前半の日本電装（現デンソー）で開発された。 トヨタグループの生産現場では、部品名と数量の記された物理的なカンバンが発注書、納品書として行き来することで在庫を管理する。そのデータ入力を自動化するバーコード（ＮＤコード）を開発したのがデンソーだ。 バブル全盛の1990年ごろ、空前の生産台数、多様な車種・オプションに応えるため、部品も納入業者も急激に増え、ＮＤコードが限界を迎えていた。63桁の数字しか
Changing std::sort at Google’s Scale and Beyond
TL;DR; We are changing std::sort in LLVM’s libcxx. That’s a long story of what it took us to get there and all possible consequences, bugs you might encounter with examples from open source. We provide some benchmarks, perspective, why we did this in the first place and what it cost us with exciting ideas from Hyrum’s Law to reinforcement learning. All changes went into open source and thus I can
BlockQuicksort: How Branch Mispredictions don't affect Quicksort
Since the work of Kaligosi and Sanders (2006), it is well-known that Quicksort -- which is commonly considered as one of the fastest in-place sorting algorithms -- suffers in an essential way from branch mispredictions. We present a novel approach to address this problem by partially decoupling control from data flow: in order to perform the partitioning, we split the input in blocks of constant s
輸送問題を近似的に行列計算で解く（機械学習への応用つき） - 私と理論
輸送問題と呼ばれる問題があります． この問題は，普通は線形計画法やフローのアルゴリズムを使って解かれます． この記事では，この輸送問題を近似的に行列計算で解くアルゴリズム（エントロピー正則化 + Sinkhorn-Knopp アルゴリズム）を紹介します． 輸送問題とは アルゴリズム 得られる解の例 なぜこれで解けるのか？ 競プロの問題を解いてみる 機械学習界隈における流行 まとめ 輸送問題とは 輸送問題とは以下のような問題です． 件の工場と 件の店舗からなる，ある商品の流通圏があるとする． 各工場には 個の在庫がある.． 各店舗では 個の需要がある． 在庫の総和と需要の総和は等しいとする （すなわち ）． 工場 から店舗 に商品を一つ運ぶためには の輸送コストがかかる． 各工場 から各店舗 への輸送量 を適切に決めて，各店舗の需要を満たしつつ輸送コストの総和を最小化せよ． 輸送問題は最適化
検索エンジンの数値インデックスを支える Bkd-Tree - 好奇心に殺される。
Computer Science / Algorithm 検索エンジンの数値インデックスを支える Bkd-Tree Elasticsearchの数値データインデックスに使われるBkd-Treeというアルゴリズムを論文を読みながらまとめました。 Overview こんにちは pon です。Elasticsearch & Lucene 輪読会を弊社で毎週開催しているのですが、そこでBkd-Treeというアルゴリズムに行き着きました。そこでBkd-Treeの論文を読んでみたので、まとめたものを共有しようと思います。 論文はこちら Bkd-Tree: A Dynamic Scalable kd-Tree LuceneでのBkd-Tree Bkd-TreeはLucene6から導入されたようで下記のようにスペース効率、パフォーマンスが大幅に改善されたようです。 以下こちらのElasticsearch公
xi-editor/docs/docs/crdt-details.md at master · xi-editor/xi-editor
This document contains a detailed description of the data structures and operations Xi uses for text. These data structures and the merge operation also form a Conflict-free Replicated Data Type (CRDT). It being a CRDT allows Xi to be used for concurrent editing of text on multiple devices, it can merge edits, including those made offline, between multiple devices and converge on a consistent docu
マギレコ2話の絶交階段を計算機として利用する - Qiita
マギアレコード 魔法少女まどか☆マギカ外伝 第2話 https://abema.tv/video/episode/26-89_s1_p2 マギレコ2話に以下の機能を持つ「絶交階段」がでてきます. 絶交階段の6段目に自分の名前,7段目に絶交したい相手の名前を書いちゃえばそれが絶交証明書！ もしも仮にも万が一仲直りなどしようものなら謝った方が鎖の化け物に攫われちゃう！ この絶交階段を使ったら計算機が作れそうですよね. 本質的には「nandゲートが構成できれば計算機が作れる」ので,この記事では絶交階段を使ってnandゲートを構成するところまで示します. 絶交階段の機能 この絶交階段の機能を理想状態での機能として解釈すると以下の通りになります. 二値($1$:現世に居る, $ 0$:鎖の化け物に攫われている)をとる人間 $a_1,a_2,...$ が無限に存在する ペア$(a_i,a_j)$を絶交
ループの添字順序を間違えた Floyd-Warshall アルゴリズムを３回繰り返すと正しい結果が得られる - Qiita
Floyd-Warshall アルゴリズム は重み付き有向グラフのすべての頂点対に対して最短路距離を求める代表的なアルゴリズムです．グラフの頂点を $V = \{1, ..., n\}$ とし，$n \times n$ 配列 $d$ の $(i, j)$ 成分をグラフの $i, j$ 間の枝長 (枝がなければ $\infty$，$i = j$ はゼロ) で初期化してから以下の３重ループを実行すると，すべての頂点 $i$, $j$ についてそれらの間の最短路長が $d[i,j]$ に入ります（ただしグラフは負閉路をもたないとします）． # Floyd-Warshall アルゴリズム for k = 1, ..., n: for i = 1, ..., n: for j = 1, ..., n: d[i,j] = min(d[i,j], d[i,k] + d[k,j]) ところで，Floyd-
Neural Turing Machines
Neural Turing Machines Alex Graves gravesa@google.com Greg Wayne gregwayne@google.com Ivo Danihelka danihelka@google.com Google DeepMind, London, UK Abstract We extend the capabilities of neural networks by coupling them to external memory re- sources, which they can interact with by attentional processes. The combined system is analogous to a Turing Machine or Von Neumann architecture but is dif
diffの動作原理を知る～どのようにして差分を導き出すのか | gihyo.jp
UNIXの基本的なコマンドの1つであるdiff。 これに実装されているアルゴリズムは実に興味深い世界が広がっています。 本稿では、筆者が開発した独自ライブラリ「dtl」をもとに「diffのしくみ」を解説します。 はじめに diffは2つのファイルやディレクトリの差分を取るのに使用するプログラムです。 ソフトウェア開発を行っている方であれば、SubversionやGitなどのバージョン管理システムを通して利用していることが多いかと思います。本稿ではそのdiffの動作原理について解説します。 差分の計算の際に重要な3つの要素 差分を計算するというのは次の3つを計算することに帰結します。 編集距離 2つの要素列の違いを数値化したもの LCS（Longest Common Subsequence） 2つの要素列の最長共通部分列 SES（Shortest Edit Script） ある要素列を別の要
Googleのヒット数を用いて意味の関わりの強さを測る手法｜Colorless Green Ideas
正規化Google距離というGoogleの検索ヒット数に基づく意味の類似性を示す尺度について紹介する。 はじめに 自然言語処理において意味を扱う際に、ある表現の意味と別の表現の意味がどれだけ関わりがあるのかということが分かると有用であることが多い。以下に紹介する文献では、検索エンジンGoogleでのヒット数を用いて、意味の関わりの強さを測る手法が提唱されている。 Cilibrasi, R. L. & Vitanyi, P. M. B. (2007). The Google Similarity Distance. IEEE Transactions on Knowledge and Data Engineering, 19(3), 370-383. （このページからPDFがダウンロード可。） 今回は、この論文の内容について紹介したい。正直言って、この辺の議論は自分の専門外で、論文もしっかり
Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
Web広告配信における多腕バンディット問題、Mortal Multi-Armed Bandits Problemとアルゴリズム - CARTA TECH BLOG
こんにちは@hagino3000です。Zucks Ad Networkという広告配信サービスの開発をしています。最近はアドネットワークの広告配信最適化に利用できるアルゴリズムの調査もしています。 本稿では調査で読んだ論文の一つ、オンライン広告配信を想定した多腕バンディット問題である、Mortal Multi-Armed Banditsを紹介します。多腕バンディット問題になじみがある読者を想定しています。 papers.nips.cc オンライン広告と多腕バンディット問題 ここでは簡単のために、クリック課金型のディスプレイ広告を前提に説明します。オンライン広告配信システムにおける問題として「最初はどの広告がどれだけクリックされるかわからないが、なるべくクリックされる広告を多く配信したい。」という物があります。これは多腕バンディット問題として知られており、探索はCTRが推定できるまで配信する事
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Computing square root floor
ReDoS 検出の最先端 recheck の紹介 / State of the Art of ReDoS Detection
The best strategies for Wordle - Things (various)
Note ranking | Birdwatch Guide
犬でもわかる Minimal Acyclic Subsequential Transducer / Introduction to Minimal Acyclic Subsequential Transducer
http://cucis.ece.northwestern.edu/projects/DMS/publications/AnomalyDetection.pdf