転置インデックスの圧縮技法
転置インデックスは、検索エンジンの実装において、中心的な役割を果たすデータ構造である。 転置インデックスのデータ構造とアルゴリズムは、クエリ処理アルゴリズムとともに、検索エンジンの性能に直結する。とくに大規模な検索エンジンにおいては、キャッシュ効率を高めてクエリ処理を高速化するために、転置インデックスの圧縮は必要不可欠となっている。 この記事では、転置インデックス、とくにポスティングリストの圧縮について、近年の手法を簡単にまとめる。 目次 転置インデックスの基本 転置インデックスのデータ構造と特性 転置インデックスのアクセスパターン 近年のインデックス圧縮技法 Variable-Byte Family VByte Varint-GB Varint-G8IU Masked-VByte Stream-VByte Opt-VByte Simple Family Simple9 Simple16
英語論文執筆のために arXiv からの例文検索サービスを作った話
arXiv の論文から例文を検索する Hyper Collocation というサービスを公開しました． 以下はあまり整理されていない製作の記録です． 英語論文執筆用の例文検索サービス 英語での論文執筆の際に，専門用語を含む例文や言い回しのパターンを知りたいことが多々あります．有用なサービスとしては ライフサイエンス辞書のコーパス検索 Springer Exemplar (2018/2/1頃に終了) がありますが， データがライフサイエンス系の論文に限られている（ライフサイエンス辞書） ソートの基準が頻度順ではないため典型的な例文が上位にこない ストップワードに近い頻出語を検索した際の 検索が重い（Springer Exemplar） 表示可能な検索結果が偏る（ライフサイエンス辞書） という不満点があったので，並行して個人的な資料から検索を行うプログラムを作って使っていました． しかし，個
機械学習の有益な書籍情報を共有します - EchizenBlog-Zwei
機械学習の有益な書籍情報を共有します。 初心者向け 最初に読む本としては「オンライン機械学習」「フリーソフトではじめる機械学習入門」「言語処理のための機械学習入門」がオススメです。 「オンライン機械学習」は3章までが入門的な内容になっています。4章以降は発展的な内容なのである程度力がついてからが良いです。オンライン機械学習という分野は実装が簡単で実用性が高いので最初に取り組むのに適しています。 広い範囲で機械学習を概観したい場合は「フリーソフトではじめる機械学習入門」がよいです。こちらは全体像がつかみやすい反面、数式の展開がわかりにくい箇所がちらほらあるので適当なスルー力が必要とされます。 「言語処理のための機械学習入門」はやや実装よりの本です。数式をみるより具体例をみたほうがわかりやすい、という人はこの本が良いと思います。 数学 何をやるにしても基礎体力は大切。数学の理解が深まれば深まる
AdaGradよりもいけていると噂のオンライン学習器Adamを実装しました - EchizenBlog-Zwei
AdaGradよりもいけていると噂のオンライン学習器Adamを実装しました。 実装がとても簡単で、ハイパーパラメータも論文に推奨値が書いてあるのが良いですね。 持っておかないといけないパラメータの数は(たぶん)AdaGradと同じです。 https://github.com/echizentm/Adam AdaGradやAdamのようなオンライン学習器は実装が簡単、省メモリなど優れた特徴があり大変実用的ですし、そろそろ有益な書物も発売されるようなので、気になった方はこれを機に学んでみると良いですよ。 しかしこうなるとAdamを改良したEveという学習器を作ってみたいですね(作るとは言っていない)。
GitHub - powturbo/TurboPFor-Integer-Compression: Fastest Integer Compression
TurboPFor: The synonym for "integer compression" ALL functions available for AMD/Intel, 64 bits ARMv8 NEON Linux+MacOS/M1 & Power9 Altivec 100% C (C++ headers), as simple as memcpy. OS:Linux amd64, arm64, Power9, MacOs (Amd/intel + Apple M1), 🆕(2023.04) Rust Bindings. Access TurboPFor incl. SSE/AVX2/Neon! from Rust 👍 Java Critical Natives/JNI. Access TurboPFor incl. SSE/AVX2/Neon! from Java as f
多腕バンディットによる表示コンテンツの最適化 - クックパッド開発者ブログ
こんにちは。技術部検索グループの原島です。 上の画像は、スマートフォン（ブラウザ版）で見たクックパッドの検索結果ページです。レシピだけでなく、ニュースも表示されていますね。献立や掲示板のスレッドなどが表示されることもあります。 クックパッドでは、検索結果ページに表示するコンテンツをクエリなどに応じて最適化しています。最適化は、膨大なログデータと最新の機械学習を用いることで、実現しています。このエントリでは、クックパッドにおけるコンテンツ最適化の裏側を紹介します。 最適化の背景 スマートフォンの普及に伴って、ユーザが利用するプラットフォームは PC からモバイルにシフトしつつあります。クックパッドにおけるモバイル利用者の割合も、ここ 2 年で 10% 以上増加しました。最近では、60% 以上のユーザがモバイルからアクセスしています。 ユーザの利用形態が変化すれば、検索結果ページもその変化に対
手元に置いておくと安心できる、情報系の人向けな日本語の本のリスト - EchizenBlog-Zwei
最近、人に本を薦める事が多くなった。とりあえずこの辺を読むといいですよ的なリストを作っておくと便利だと思ったので作ることにした。 以下、「事前知識のいらない入門本」「事前知識はいらないけど本格的な本」「事前知識がないと何言ってるかわからないけど有益な情報が満載な本」の3つにわけて列挙する。 事前知識のいらない入門本 数式少なめ、脳負荷の小さめな本をいくつか。何をやるにしてもデータ構造、アルゴリズム、数学はやっておくと幸せになれるよ。 情報検索と言語処理 データマイニングとか自然言語処理とかやりたい人にはとりあえずこれ。さすがに古い話が多くなってきたのでそろそろ新しい入門用情報検索本がでないかなあと思っている。 図解・ベイズ統計「超」入門 伝説のベイジアン先生がベイズの基礎を教えてくれる本。ベイズやりたい人はこれ。 珠玉のプログラミング データ構造とかアルゴリズムとかの考え方の基礎を教えてく
完備辞書（簡潔ビットベクトル）の解説 - アスペ日記
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。 LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。 また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。 この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。 今回は、このデータ構造*2について書いてみます。 完備辞書でできること ビット列に対する定数時間の rank と selectです*3。 rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。 select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。 それぞれ例を挙げます。
「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei
「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。 とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。 まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。 親 → 子 (1) → (2, 3) (2) → (4) (3) → (5)この木構造は以下の重複あり集合によって表現することができる。 { 2, 4, 5, 5, 5 }これだけ書くとなんのこと？と思われるかもしれない。そこでこれから2つのことを説明する。ひとつは「何故、木構造が自然数の重複あり集合で表現できるか」、もうひとつは「重複あり集合で表現することに何の意味があるか」ということ。 何故、木構造が自然数の重複あり集合で表現
パターン認識の人手最強伝説 - 武蔵野日記
午前中は機械学習の基礎勉強会の最終回。1冊全部通読できてよかった。 昼から研究室配属の説明会。誰がうちの研究室を希望してくれるかな？ 連続して学部3年生のプロジェクト実習の最終発表会。学生たちが各自チームで半年間研究した成果を発表してくれた。トップバッターの女の子4人組チームがとてもプレゼンがうまく、出した数値も段違いによく、他のチームのほぼダブルスコアで、最優秀発表賞を受賞していた。ポスター発表を聞くと、ポスターにはアルゴリズムが前面に書かれていたが、質問してみたところアルゴリズムが問題なのではなく、驚くべき手法によってその精度が達成されていた。 タスクは顔画像認識で、人物の映る画像が与えられたとき、それが誰か当てるという課題。ただ、この実験は設定が特殊で、画像に手を加えてもいいことになっていた。そこで、彼女たちは数千枚の写真画像からなる訓練事例とテスト事例の両方で、まず顔の中心点を決め
[O] 新年会 + #DSIRNLP 5 を開催しました & 動画UPしました
新年会 + #DSIRNLP 5 を開催しました & 動画UPしました Tweet [日記] 新年会とデータ構造と情報検索と言語処理勉強会 #DSIRNLP の第5回目を開催しました。 ご発表、ご参加頂いたみなさま、どうもありがとうございました。 会場を提供していただきました、スマートニュース株式会社のみなさま、どうもありがとうございました。 # スマートニュースさんは今後も各種勉強会に会場を提供してくださるそうです。 DSIRNLP 5 について 今回は参加するための条件を設けてみました。 参考文献 : http://partake.in/events/572bb762-87ed-490a-b993-8b864137e7e1 条件はとてもシンプルで、発表する方か、ググったらどんなことが得意なのかが分かる方だけが参加できる、というものです。 実際にやってみた感触として、参加者からはとても好
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
Foursquare: 機械学習のアルゴリズムがサービスを磨いてくれる - ワザノバ | wazanova
http://engineering.foursquare.com/2013/12/05/how-we-built-our-model-training-engine/ Foursquareでは、どこにチェックインしてもらうか、レコメンデーション、ディスカウント、プロモーションアップデートなどあらゆる場面で機械学習の手法を応用しています。1日あたり100万件のExplore機能のクエリと600万件のチェックインがあり、それを高速で処理するとともに、その情報は機械学習のモデルに活かされています。同社のエンジニアブログで、Data AnalystのMichael Liが、機械学習のためのModel Training Engine（MTE）の構築について語っています。 多くの機械学習モデルが線形回帰かその類似のアプローチを利用していて、データをすぐに理解するという意味では利便性は高いが、ときに非
ハミング距離の計算はホントに速いのか？
これは@sakanazensen君が主催する『Computer Vision Advent Calendar 2013』の12/8の記事です。今年はあまり活発でないようなので、小ネタですが参戦しました。 はじめに 昨今のコンピュータビジョン・パターン認識分野で特徴ベクトルのバイナリベースの記述法が流行っています。その利点の一つとして、特徴ベクトル間の距離としてコンピュータにとって計算が容易な「ハミング距離」が使える、というものがあります。これはXOR演算と PopCount演算（いくつのビットが1かをカウントする演算）で構成されており、特に近年のCPUにはまず搭載されているベクトル計算命令セットの一つ「SSE4.2」の専用命令「POPCNT」が高速演算の根拠としてよく引き合いに出されます。二つともかなりプリミティブな命令ですから確かに高速に計算できそうな感じはします。しかしながら、例えばL
やる夫が(インライン)アセンブラを使って競技プログラミングに挑戦するようです - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2013の9日目の記事です。 今年も、競技プログラミングでほとんど役に立たないネタをお送りします。 1：名無しのターゲットさん：2013/12/9(月) 00:25:07 id:jetbead ! | !l |! ! | ! | ! l | ! l |! | !ll |! l |!| !l | ! ! | !l |! ! | ! !ll |! l !| l !ll |! l !| | ! l il i (ヽ＝＝＝＝＝＝＝＝ | |! ! | ! | ! l | l | !| ! l | ! l ノ￣ﾉ￣ﾉ￣ﾉ￣ﾉ￣ﾉ ある日の競技プログラミング終了直前のやる夫家 |! l |! ノ
計算量のはなし - 赤い黒歴史を蓄積する
どうも華麗なるキャッツパーです。キャットアッパーです。 この記事はCompetitive Programming Advent Calendar Div2013, 12/7の記事です。 私は過去に、暇に任せてこのようなスライドを作ってしまいました。 有名アルゴリズムとそれの計算量について列挙するのが楽しすぎて作ってしまいました。後悔しております。 本記事では「計算量ってどうやって計算するの？」みたいな話を競プロの観点からします。 計算量とはなんぞやということについては上のスライドを読んでください。 計算量の種類 競技プログラミングで気にする計算量は2種類あります。最悪計算量と償却計算量です。 最悪計算量というのは、ある処理にどのような入力を与えても、それ以上に速い計算量になる、というもので、一種の上界です。競技プログラミングでは作問者が最悪計算量になるテストケースをかならず入れてきますから
PageRankアルゴリズムを使った人事評価実験 | 株式会社サイバーエージェント
2-2-1.一般的な360度評価による評価方法 問題点 一般的に評価プロセスが公開されていないため、最終評価までのプロセスが不透明である 全員が全員を評価するのは多数の社員がいる場合は不可能である ランダム抽出によるお互いの評価を行うと、まったく違う専門分野を評価したり、まったく関わりあいのない人を評価することになり精度が下がる 2-2-2.専門分野での評価者による評価方法 問題点 *評価者になる人材の不足 高い専門スキル、会社とのビジョンマッチ、メンバーからのその専門分野での高い信頼の全てを備えている人材が専門分野毎に必要。 さらに、評価の納得性を保つためにはメンバーからの信頼がある人材ではないと評価できない。 *評価者によって評価ポイントの違いがある 同じ分野の技術者でも、スキルの価値をどこに置いているかというスタンスの違いから評価ポイントにゆらぎが発生する。 さらに評価者自体
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
Packing Santa's Sleigh | Kaggle
partake.in