はじめに 焼きなまし法について、問題へ適用する際のメモ。 焼きなまし法とは 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で検索してみても、最尤導出の構文木や内側確率の計算例などはあっても、外側確率や生成確率の推定などまで計算例を書いて…
はじめに 勾配ブースティング木の高速化はどうすればいいだろうと調べていたら、arxivで流れているのを見かけたのでメモ。 FastBDT: A speed-optimized and cache-friendly implementation of stochastic gradient-boosted decision trees for multivariate …
はじめに ここしばらくサボってしまっているので、(のんびりと)いろいろ勉強していきたい。 コンテスト系などでもよい成績を残している勾配ブースティング木について試してみた。 勾配ブースティングとは Gradient Boosting 加法的モデルH(x)=Σρ_t * h_t(x)…
はじめに 最近よく見かける「t-SNE」という非線形次元圧縮手法を試してみた。 t-SNEとは t-Distributed Stochastic Neighbor Embedding SNEと呼ばれる次元圧縮手法の問題点を改善した手法 SNEは、「各点間の"ユークリッド距離"を、類似度に相当する"条件付き…
はじめに 検索エンジンのトークナイズ処理の部分で行われている基本処理や工夫を少し調べてみたのでメモ。 トークナイズ処理 「検索クエリ」に対してマッチする「ドキュメント」を高速に検索するためにインデクス(索引)を作成する 本の最後の方にある「用語 …
昨今、世界の砂漠化と並び、世界の絵文字(Emoji)化が進んでおり、社会問題として取り上げられています。 英オクスフォード辞書の「今年の言葉」のEmoji化 http://www.gizmodo.jp/2015/11/2015oxford.html プログラミング言語のEmoji化 http://developer.cybo…
はじめに 形態素解析とかの解析時に使うラティス(形態素候補をグラフにしたもの)のうち、1番ベストな解だけが欲しい場合が多いが、2番目以降の解も欲しい場合がある。 N番目までの解を効率よく求める方法があり、使いたいケースが出てきたのに書いてみる。 N…
はじめに 特定ジャンルの用語などをまとめて取得するのに、wikipediaの「〜の一覧」が有用だったりする。 wikipedia:一覧の一覧多くは、リスト形式で書かれていたりするが、中には表(テーブル)形式でまとめられているものもある。 いろんな取得方法が考えら…
はじめに 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。プロフェッショナルな「深層学習」本のバックプロパゲーションの導出が丁寧にされていてわかりやすかったので、それに合わせて書いてみる。各層の活性化関数はロジスティック(シグモイド)関数、出力層の活性化関数はソフ…
はじめに Sill et al., Feature-Weighted Linear Stacking, 2009 http://arxiv.org/abs/0911.0460最近、コンペ上位者の手法としてよく見かける手法「Stacking」の一つについてメモ。 Stacking 複数の機械学習モデルの予測結果をブレンドすることで、さらによ…
はじめに 今年の目標にしていた係り受け解析関係の資料について雑多にメモしておく。リンク集。 拾いきれていない、最新の論文まで追えていないので、あとで追加・整理し直す。 Wikipedia http://en.wikipedia.org/wiki/Dependency_grammar 文節単位がよいか…
エイプリルフールネタです:) 見ればわかりますが、30分ぐらいで作ったものなので、言ってることもコードもデータも結構適当です:p はじめに インターネット上で扱われる文書(Twitterや2ch、ニコニコ動画など)には、特殊な用語や言い回しをしているものがあり…
去年の反省 数理計画法と係り受け解析/構文解析とSVMについて勉強する あんまりできてない。。少なくともブログにまとめられていないので× 調べたことややったりしたことはメモを残す 調べた半分もまとめられていない 記事的には18記事 応用・動くものを作る…
はじめに 勉強会で、学習率を改善(自動調整)する事で学習時間を短縮し、ファンタジスタドールを見る時間を多く確保できる事が示されていた。 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のペ…
はじめに 複数のアルゴリズムの結果の有意差検定に使用されていたので、メモ。より詳細に紹介されているのは以下の論文。 Demsar, Statistical Comparisons of Classifiers over Multiple Data Sets, 2006 http://jmlr.csail.mit.edu/papers/volume7/demsar0…
DSIRNLP#6 10/11にデンソーアイティーラボラトリさんで行われたDSIRNLP#6勉強会で発表させていただきました 聴いていただいた方、ありがとうございました。 勉強会のページ http://partake.in/events/38e416b0-5e64-4bd4-8388-4e19acd0ef97 発表資料 一部、…
はじめに 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とは 補間探索、内挿探索 二分探索での範囲の中間値を利用する代わりに、範囲の両端の値から探したい値の位置にあたりをつけて、その値を利用して探索していく方法 二分探索では、配列の値に関係なく範囲の中間の値を利用して探索 探索…
はじめに G. Tsoumakas, I. Katakis, I. Vlahavas., Mining Multi-label Data http://lpis.csd.auth.gr/paper_details.asp?publicationID=290 マルチラベル分類問題について、メモ。 マルチラベル分類問題 1つの事例が、複数のラベル(ラベルの集合)に同時に…
はじめに Rousseau et al., Graph-of-word and TW-IDF: New Approach to Ad Hoc IR http://www.lix.polytechnique.fr/~rousseau/papers/rousseau-cikm2013.pdf 文書dのグラフ的表現とそこから計算されるTW-IDFというTermの重み付けについて、メモ。 Graph of…
