はじめに 焼きなまし法について、問題へ適用する際のメモ。 焼きなまし法とは Simulated Annealing, SA 物理現象の焼きなましのコンセプトを組み合わせ最適化問題の探索過程に導入した、確率的近似解法の一つ 現在の解の近傍から良い解に移動することを繰り…

はじめに RangeCoderのメモ。 中途半端な理解で適当に書き写そうとしたらひどいことになったので、まとめておく。。。 RangeCoderとは エントロピー符号の一種 シンボル列をある数値で表現する 以下、桁上りありの場合について下記サイトを参考に作成してみ…

はじめに 読んでる論文に出てきてたElias-Fano Encodingをちょっと書いて遊んでみた。 Elias-Fano Encodingとは 単調増加整数列の表現方法のひとつ 他の方法としては、ちょっと情報が古いけど http://d.hatena.ne.jp/jetbead/20110918/1316373030 など 厳密…

はじめに XBWをWaveletMatrixを使って、試しに実装してみた。 XBWとは 効率よくTrie木を表現する方法 Burrows-Wheeler Transform(BWT)の(木への)拡張 詳しい解説や作り方は以下のページや「高速文字列解析の世界」などを参照 https://research.preferred.jp/…

はじめに 100-nlp-papersで紹介されてた一番最初の論文に、クナイザーネイスムージングのスッキリな実装が載っていたので書いてみる。Joshua Goodman: A bit of progress in language modeling, MSR Technical Report, 2001. Kneser-Ney smoothingとは 言語…

はじめに 確率文脈自由文法での生成規則の適用確率の推定アルゴリズムで紹介されている「Inside-Outsideアルゴリズム」について、Webで検索してみても、最尤導出の構文木や内側確率の計算例などはあっても、外側確率や生成確率の推定などまで計算例を書いて…

はじめに ここしばらくサボってしまっているので、(のんびりと)いろいろ勉強していきたい。 コンテスト系などでもよい成績を残している勾配ブースティング木について試してみた。 勾配ブースティングとは Gradient Boosting 加法的モデルH(x)=Σρ_t * h_t(x)…

はじめに 最近よく見かける「t-SNE」という非線形次元圧縮手法を試してみた。 t-SNEとは t-Distributed Stochastic Neighbor Embedding SNEと呼ばれる次元圧縮手法の問題点を改善した手法 SNEは、「各点間の"ユークリッド距離"を、類似度に相当する"条件付き…

はじめに 形態素解析とかの解析時に使うラティス(形態素候補をグラフにしたもの)のうち、1番ベストな解だけが欲しい場合が多いが、2番目以降の解も欲しい場合がある。 N番目までの解を効率よく求める方法があり、使いたいケースが出てきたのに書いてみる。 N…

はじめに https://pycon.jp/2015/ja/proposals/vote/11/ Pycon2015で発表された「Pythonで作って学ぶ形態素解析」で紹介されていた辞書データ構造の「Minimal Acyclic Subsequential Transducer」について、勉強のために書いてみた。 Minimal Acyclic Subseq…

はじめに http://live.nicovideo.jp/watch/lv228162988 先週のNL研のニコ生で、ベイズ的最適化についての招待講演を見ていて「SEは滑らかすぎる」という発言がよくわからなかったので、GP-MIを試してみる。 Contal et al., Gaussian Process Optimization wi…

はじめに プロフェッショナルな「深層学習」本で紹介されているRNNの一種のElman netを書いてみる。 Recurrent Neural Network(RNN)とは 再帰型ニューラルネット ネットワーク内部に内部有向閉路を持つようなニューラルネットの総称 Feedforwardの時は、入力…

はじめに FeedForwardNeuralNetwork。プロフェッショナルな「深層学習」本のバックプロパゲーションの導出が丁寧にされていてわかりやすかったので、それに合わせて書いてみる。各層の活性化関数はロジスティック(シグモイド)関数、出力層の活性化関数はソフ…

エイプリルフールネタです:) 見ればわかりますが、30分ぐらいで作ったものなので、言ってることもコードもデータも結構適当です:p はじめに インターネット上で扱われる文書(Twitterや2ch、ニコニコ動画など)には、特殊な用語や言い回しをしているものがあり…

はじめに 勉強会で、学習率を改善(自動調整)する事で学習時間を短縮し、ファンタジスタドールを見る時間を多く確保できる事が示されていた。 AdaGrad等をさらに改良したらしいAdaDeltaがあるようなので、ロジスティック回帰に適用してみた。 AdaDeltaとは M.…

はじめに boostには、確率分布のquantile(分位数、分布をp:1-pに分割する点)を計算するものが用意されている。 ベータ分布の場合について、自分でも書いてみる。 コード #include <iostream> #include <cmath> //#include <boost/math/distributions/beta.hpp> class BetaDistribution { double eps; double val_a</boost/math/distributions/beta.hpp></cmath></iostream>…

はじめに Feature Hashingについて気になったことがあったので試してみた。 Feature Hashingとは Hashing trick ハッシュ関数を使って、素性群をM次元ベクトルにする 一種の次元圧縮 Bag of wordsなどの素性をそのままハッシュ値にすることで、素性とIDのペ…

はじめに S. Wang & C. D. Manning, Baselines and Bigrams: Simple, Good Sentiment and Topic Classificatioin Naive Bayes素性を利用したSVM(NBSVM)なるものを試してみる。 SVM with NB features(NBSVM) Log-count ratio r = log( (p / ||p||_1) / (q / |…

Interpolation Searchとは 補間探索、内挿探索 二分探索での範囲の中間値を利用する代わりに、範囲の両端の値から探したい値の位置にあたりをつけて、その値を利用して探索していく方法 二分探索では、配列の値に関係なく範囲の中間の値を利用して探索 探索…

はじめに 簡単な例としてよく出てくる「編集距離」を使って、英単語の修正を試してみる。(編集距離が小さいものを列挙するまで) dpができなすぎるので、「dpやるだけ」って言えるようになりたい。 編集距離とは ある文字列sからある文字列tへ、文字の削除、…

はじめに 先日北海道で行われたNLP2014(Neko Language Processing 2014)で最優秀賞だった「ビットペア法を用いた日本語-猫語翻訳アルゴリズム」を試してみました。ネコ氏の鳴き声を分析したところ特徴的なパターンが見られ、日本語とネコ語間の変換ルールを…

はじめに 複数文書要約をナップサック問題として解く、という話を聴いて、簡単に試せそうなのでやってみる。 手法 西川ら「冗長性制約付きナップサック問題に基づく複数文書要約モデル」 https://www.jstage.jst.go.jp/article/jnlp/20/4/20_585/_pdf上記の…

はじめに 悩み多き年頃なので、進捗ダメです。 KVS見てるときに出てきた、次元圧縮っぽさがあるBloom Filterを試してみる。 Bloom Filterとは 「ある要素が集合に含まれるか否か？」を扱えるデータ構造 要素をそのまま保存せず、ハッシュ値にしたものを配列…

はじめに 次元削減せずにはいられない。 0の扱いがいまいちピンとこなかったので、ちょっと調べて試してみた。 Matrix Factorizationとは Netflix Prizeという推薦システム・協調フィルタリングのコンテストで良い結果を残した手法 行列Mを、2つの行列P,Qの…

はじめに Deepな話で、簡単に試せそうだったStacked Denoising AutoEncoderを試しに遊んでみる。 あんまり詳しく調べていないので、お遊びレベルという感じで・・・注意:下記では「特徴抽出器」として利用する方法を試しています。通常は事前学習として行い…

この記事はCompetitive Programming Advent Calendar Div2013の9日目の記事です。今年も、競技プログラミングでほとんど役に立たないネタをお送りします。 1：名無しのターゲットさん：2013/12/9(月) 00:25:07 id:jetbead ! | !l |! ! | ! | ! l | ! l |! | …

はじめに 簡単だけど性能がよく、様々な実装が公開されていてマジでパナいと噂の、ランダムフォレストで遊んでみる。 ランダムフォレストとは Breimanによって発展改良された、複数の相関の低い決定木を組み合わせる集団学習の一つ 詳細な紹介や内容は「参考…

はじめに そういえばliblinearよく使うのにロジスティック回帰自分で書いた事ないなぁと思ったので、ちょっと書いてみた。 詳しい解説記事 とてもいい感じの連載がされている。 http://gihyo.jp/dev/serial/01/machine-learning L1/L2正則化については以下も…

はじめに 巨大だけどほとんどの要素がゼロであるような疎行列は、そのまま保持するより、要素がゼロじゃないところだけをうまく保持する事でメモリや計算量を減らせたりする。 扱う行列のタイプによって、効率のよい形式がいくつかあるようなので代表的なも…

はじめに 次元圧縮がマイブーム化しているので、最近はやりのAutoEncoderで遊んでみる。 べ、別に深い何かのためにやろうとしてるわけじゃn AutoEncoderとは 入力と出力が近くなるように学習するニューラルネットワーク (枠組みをさすだけでニューラルネット…