お手軽に文章ベクトルを比較して入門した

文章を実数値ベクトルとして表現したものを文章ベクトルと呼びます。文脈によっては文章埋め込みや文章の分散表現とも呼ばれます。離散的な文章データを機械学習などに応用するにはベクトル表現が必要なことが多く、「どうすれば文章の特徴をよく表現したベクトルが得られるか？」は伝統的に重要なタスクです。

さて近年では、学習済みモデルやライブラリが整備されているおかげで、大規模なコーパスやハイスペPCを用意しなくても、それなりに品質の良い文章ベクトルが得られます。文章ベクトルがあれば、お手軽に検索したりクラスタリングしたりできるので、とてもありがたいです。

しかし、機械学習ビギナーのわたしには、どのベクトルをどう用いるのが良いのか経験的にわからないです。そこで年末年始の暇な時間を使って、教師なしでお手軽に得られる文章ベクトルを比較して遊んで入門してみようと思います。

続きを読む

シンプルで強いFrontCoding文字列辞書を紹介したい

本記事では、文字列集合を保存し検索するためのシンプルで強いデータ構造であるFrontCoding文字列辞書（以下、FC辞書）を紹介します。このために使われるデータ構造としてはハッシュ表やTrieがメジャーです。それに対して、FC辞書はあまり使われていない印象で、実際に公開されているライブラリも少ないです。

しかし、FC辞書もハッシュ表やTrieに負けない利点を備えたデータ構造ですので、用途やデータセットによっては効率的に文字列辞書を実現することができます。例えば、SIGIR 2020でのクエリ補完に関する論文 [1] では、伝統的なTrie辞書よりもFC辞書の方が高速に検索できることを示しています。また、DB圧縮などで使われるDictionary Encoding (or Domain Encoding)1 でもFC辞書は有益です [2,3]。そのため、FC辞書について知っておくと、文字列データを扱うときに幸せになれるかもしれません。

以降では、[2] の論文の内容を参考にFC辞書を解説します。

  1. 辞書を使って文字列などの可変長データを単純な固定長の整数値に置き換える技法です。固定長データは配列に保存しやすかったり比較が高速であったりと様々な利点を持つので、文字列データを扱う多くの用途でDictionary Encodingは有益です。↩
続きを読む

C++でファイルを後ろ向きに読み込むときはバッファリングに気をつけようって話

C++でファイルを読み込むとき、std::ifstream を使うのが一般的だと思います。本記事では、ifstream でファイルを後ろ向きに読み込む場合には、バッファリングに気を付けて実装しないと読み込みがとても遅くなってしまうことについて解説します。

以下、固定長バッファを使いつつ文字を一文字ずつ後ろから読み込みたい場合を想定します。

TL;DR

  • ifstream は内部でバッファリングしてくれてる。
  • 後ろ向きに読み込む場合はバッファリングがうまく機能せず激遅になる。
  • FILE など使ってちゃんとバッファリングしながら読み込もう。
続きを読む

高速な圧縮辞書ライブラリXcdatをリリースしました

圧縮ダブル配列を利用したトライ辞書ライブラリXcdatをリリースしました。

github.com

頑張って整備したので、簡単ではありますが解説記事を書いて宣伝したいと思います。Star頂けるととても喜びます。

続きを読む

お勉強メモ：混合ベルヌーイ分布とEMアルゴリズム

前回の最尤推定法に引き続き、ITエンジニアのための機械学習理論入門で勉強したのでメモ。今回は７章のEMアルゴリズム。

ベルヌーイ分布での最尤推定

N 個の観測点 \{ X_n \}_{n=1}^N が与えられて、観測点は D 次元の２値ベクトルとする。つまり X = (x_1, \dots, x_D )^{T} , x_i \in \{ 0,1\} 。

各次元はベルヌーイ分布に従うと仮定したとき、 x_i = 1 である確率 u_i \in [0,1] をパラメータとして x_i の確率密度関数は

\displaystyle p_i(x_i \mid u_i ) = {u_i}^{x_i} (1 - u_i)^{1 - x_i}

パラメータベクトルを U = (u_1, \dots , u_D)^T とすると、X の確率密度関数は

\displaystyle p(X \mid U ) = \prod_{i=1}^{D} p_i(x_i \mid u_i )

このとき、観測データ \{ X_n \}_{n=1}^N の尤度関数は

\displaystyle P = \prod_{n=1}^{N} p(X_n \mid U )

これを最大化するパラメータは手を動かせば解くことができて、以下の通り

\displaystyle U = \frac{1}{N} \sum_{n=1}^{N} X_n
続きを読む

お勉強メモ：最尤推定法

機械学習の知識を忘れるたびにITエンジニアのための機械学習理論入門で勉強し直してる。いい加減この輪廻を断ち切るため簡単にでもメモを残していくべき。今回は３章の最尤推定法。

パラメトリックモデル

以下のステップで予測モデルを決定する手法

  1. パラメータを含むモデルを設定
  2. パラメータを評価する基準を設定
  3. 最も尤もらしいパラメータを決定

最尤推定法もパラメトリックモデルであり、与えられた N 個の訓練データ \{ (x_n, t_n ) \}_{n=1}^{N} から以下のように尤もらしいモデルを決定する。

続きを読む