bit vector + popcntでバイナリ素性のk-NN分類器を高速化する - シリコンの谷のゾンビこんばんは @sleepy_yoshi です．Machine Learning Advent Calendar 2012 の11日目を担当します．サモア時間ではまだ12月11日なので間に合いましたね．今日はバイナリ素性ベクトルの内積計算にSSE4.2のpopcnt命令を用いて高速化することでk-NN分類器を高速化する話について書きます． このブログでは普段である調で書いていますが，今日はなんとなくですます調で書きます． k-NN (k Nearest Neighbor) 分類器はラベルを予測したい事例に対して，訓練データとして与えられたラベル付き事例集合の中からk近傍の事例のラベルを用いて予測する，という分類器です．k近傍を求めるために，訓練データに含まれる事例全てに対する類似度を計算する必要があります．類似度には様々な尺度が利用されますが，ここでは内積とします．そのためk個の近傍を発見す
