Feature-Weighted Linear Stackingメモ - Negative/Positive Thinking
はじめに Sill et al., Feature-Weighted Linear Stacking, 2009 http://arxiv.org/abs/0911.0460 最近、コンペ上位者の手法としてよく見かける手法「Stacking」の一つについてメモ。 Stacking 複数の機械学習モデルの予測結果をブレンドすることで、さらによい予測結果を得る方法 アンサンブル学習やメタ学習の一種 「学習モデルを一つずつ積み重ねる＝スタックする」 一般に2段階で構成され、1段階目は入力に対して各学習モデルが結果を出力、2段階目はその各出力をまとめあげ最終結果を出力 BlendingやStacked generalization、日本語だとスタック汎化、スタッキングと呼ばれたりする http://shindannin.hatenadiary.com/entry/2015/03/13/101945
AdaDeltaを試す - Negative/Positive Thinking
はじめに 勉強会で、学習率を改善(自動調整)する事で学習時間を短縮し、ファンタジスタドールを見る時間を多く確保できる事が示されていた。 AdaGrad等をさらに改良したらしいAdaDeltaがあるようなので、ロジスティック回帰に適用してみた。 AdaDeltaとは M. D. Zeiler, ADADELTA: AN ADAPTIVE LEARNING RATE METHOD http://www.matthewzeiler.com/pubs/googleTR2012/googleTR2012.pdf 学習率を自動調整する方法の一つ 他の関連手法の問題点等を改良 過去すべての勾配を考慮→直近の勾配だけを考慮したいので、指数関数的に減衰するように考慮 グローバルな学習率を指定→second order methodsの特性を持つように、パラメータの変化について直近のパラメータの変化から計算し
Negative/Positive Thinking
はじめに 焼きなまし法について、問題へ適用する際のメモ。 焼きなまし法とは Simulated Annealing, SA 物理現象の焼きなましのコンセプトを組み合わせ最適化問題の探索過程に導入した、確率的近似解法の一つ 現在の解の近傍から良い解に移動することを繰り返す「局所探索」に対して、悪くなる解への移動を繰り返し回数や悪化の度合いに依存する確率で許すことで、局所最適解から脱出することがポイント 以前のメモ http://d.hatena.ne.jp/jetbead/20111014/1318598381 http://d.hatena.ne.jp/jetbead/20120623/1340419446 疑似コード x:=初期解, T:=初期温度, R:=初期イテレーション回数 while 終了条件 do begin for i:=1 to R do begin y:=近傍解の一つ(y
DSIRNLP#6で発表させていただきました＆懺悔とNaiveBayes教入信 - Negative/Positive Thinking
DSIRNLP#6 10/11にデンソーアイティーラボラトリさんで行われたDSIRNLP#6勉強会で発表させていただきました 聴いていただいた方、ありがとうございました。 勉強会のページ http://partake.in/events/38e416b0-5e64-4bd4-8388-4e19acd0ef97 発表資料 一部、発表時の資料を修正しています 主だって参考にした論文は以下になります Zheng&Webb, Semi-naive Bayesian Classification, 2008 http://www.csse.monash.edu.au/~webb/Files/ZhengWebb08a.pdf No Bayes No Life -Naive Bayesは今でも進化しているようです。- from phyllo 補足(2014/10/12追記修正しました) 質問への回答で、
編集距離で遊ぶ - Negative/Positive Thinking
はじめに 簡単な例としてよく出てくる「編集距離」を使って、英単語の修正を試してみる。(編集距離が小さいものを列挙するまで) dpができなすぎるので、「dpやるだけ」って言えるようになりたい。 編集距離とは ある文字列sからある文字列tへ、文字の削除、挿入、置換などの操作をするとき、最小の操作回数(または最小操作コスト) dp[i][j] := s[0..i-1]からt[0..j-1]にするのにかかる最小操作回数(または最小操作コスト) さまざまな変形や拡張が研究されてる 近似文字列照合 許可する操作による違い 編集距離(Levenshtein distance) 挿入、削除、置換 Damerau distance 挿入、削除、置換、隣接文字同士の入替 Longest common subsequence distance 挿入、削除 ハミング距離(Hamming distance) 置換の
ナップサック問題として複数文書要約を解くを試す - Negative/Positive Thinking
はじめに 複数文書要約をナップサック問題として解く、という話を聴いて、簡単に試せそうなのでやってみる。 手法 西川ら「冗長性制約付きナップサック問題に基づく複数文書要約モデル」 https://www.jstage.jst.go.jp/article/jnlp/20/4/20_585/_pdf 上記の論文中で紹介されている「動的計画ナップサックアルゴリズム」を参考に。 (論文で提案されている手法ではないことに注意) コード #include <iostream> #include <vector> #include <map> #include <sstream> class KPSummary { // T[i][k] := 文iまでで最大要約長がkのときの最適解値 // U[i][k] := 経路復元用(文iを利用したかどうか) std::vector< std::vector<int
SCWを試す - Negative/Positive Thinking
はじめに 分類器の決定版(？)的なSoft Confidence Weighted Learningを試してみた。 Soft Confidence Weighted Learningとは 2012年に提案された、各重みを正規分布と考え更新時にその分布が変わるようにしたConfidence Weighted(CW)関係のノイズに強くなった版 オンライン学習 http://icml.cc/2012/papers/86.pdf 詳しい解説記事 http://d.hatena.ne.jp/kisa12012/20120625/1340616659 使用したデータ LIBSVMのページにあるUCIデータセットのa9aを用いた http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ 学習データ : a9a テストデータ : a9a.t コード 毎
トピックモデルメモ - Negative/Positive Thinking
はじめに トピックモデルについてメモ。 トピックモデルとは 文書は、何らかの話題について書かれていたりする 「ある文書内に一緒にでてくる単語は、意味的な関連性が強い」など考えられる トピックモデルは、文書から「何らかの話題(＝トピック)」を発見するための統計的なモデルのこと トピックモデルのいろいろ Unigram Mixtures ナイーブベイズでクラス数kと各パラメータをEMで繰り返し推定していく http://www.kamalnigam.com/papers/emcat-mlj99.pdf Probabilistic Latent Semantic Indexing(PLSI) 検索技術であった潜在意味解析(LSI,1990年)を確率的に解析、開発された生成モデル(1999年) 各単語ごとに別なトピックから生成されたと仮定する http://cs.brown.edu/~th/pap
Locality Sensitive Hashによる類似ベクトル検索を試す - Negative/Positive Thinking
はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 Locality Sensitive Hash 類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関数のこと 高次元データの次元圧縮を行える (P1,P2,r,cr)-sensitiveなHash族とは、 2つの特徴ベクトルp,qについて(P1>P2) ||p-q||P1 ||p-q||>crならPr[h(p)=h(q)] を満たすハッシュ関数h:R^d->U コサイン類似度に対するLSH 2つのk次元ベクトルu,vについて コサイン類似度: u*v / sqrt(|u|*|v|) d個のk次元のランダムベクトルr_iを考え、ハッシュ関数h_i(u)を h_i(u) = 1 (r*u >=0) h_i(u)
MDS&文字列カーネルの可視化を試す - Negative/Positive Thinking
はじめに せっかく文字列カーネルで遊んでみたので、可視化も試してみる。 Multidimensional Scalingとは n個のm次元ベクトルについて、それらの距離のみが与えられる それらの距離をできる限り保存して低次元空間(1,2,3次元など)にマッピングする方法 通常、ユークリッド距離が使われる。非類似度なども。 計量的MDS(古典的MDS) 距離行列を求める センタリング(Young-Householder変換)を行う 固有値および固有ベクトルを求める 固有値が大きいものからk個(2次元なら2個)選び、対応する固有ベクトルの値を座標値とする 非計量的MDS 計量的MDSで仮定されている比率尺度以外の尺度の場合でも対応 MDSを試す アメリカの飛行場をプロットするのが流行らしいので、自分もやってみる。 使ったもの Eigen 3.1.2 http://eigen.tuxfamily
文字列カーネルで遊ぶ - Negative/Positive Thinking
はじめに ちょっと、高次元特徴空間での2つの文字列の像の内積である文字列カーネルで遊んでみる。 文字列カーネルを類似度として使いたい。遊びなので、数式はちゃんと追ってない、、、 文字列カーネル 文字列に対するカーネル カーネルKは、入力空間Xから特徴空間Fへの写像φについて、x,y∈Xに対してK(x,y)=<φ(x),φ(y)>を満たす関数のこと 2つの文字列の距離的なものを考えるのに、共通する部分列や部分文字列を考えたもの いろんな考え方ができるので、いろんなものが存在する 部分列と部分文字列の違い 部分列(Subsequence) 記号列に対して、「並び」だけを保持した部分的な記号列 「abcde」に対して、「abd」や「be」や「bcde」など 長さがkの部分列は「k-merの部分列」という 部分文字列(Substring) 記号列に対して、「隣接性」と「並び」を保持した部分的な記号
HyperLogLogで遊ぶ - Negative/Positive Thinking
はじめに 「さぁ、お前の罪の異なり数を数えろ！」と言われたときに使えそうな「HyperLogLog」という異なり数をカウントする方法を教えてもらったので、遊んでみた。 いつもながら論文ちゃんと読んでないので、条件やコード間違ってるかも。。。 HyperLogLogとは cardinalityと呼ばれる、要素の異なり数を決定する問題 かなり省メモリで精度のよい異なり数を推定できる方法 要素をそのまま保存せず、ハッシュ値に変換したものをうまくレジスタに保存しておく ので、レジスタサイズ程度しかメモリを使わない 並列化もできて、最近のbigdataとかで注目されている また、googleが並列計算用に改善したHyperLogLogを提案してるみたい http://blog.aggregateknowledge.com/2013/01/24/hyperloglog-googles-take-on-
テキスト自動要約メモ - Negative/Positive Thinking
はじめに 前から気になっててほっといてた自動要約についてメモ。 文短縮とか試してみたい。 テキスト要約 与えられたテキストをより短いテキストに簡潔にまとめること 要約率 = (要約後の文字数or文数) / (与えらえたテキストの文字数or文数) 要約の過程 以下の3つがある(とされている) 1.テキストの解析と理解 2.要約の内部表現への変換/変形 3.内部表現から要約テキストの生成 ただし、これらをすべてきちんとやるのは難しい 人間の場合は、以下のような行為が行われているとか 不要句の削除 文の結合 構文的変形 句の言い換え 句の置き換え 文の並び替え 考慮すべき点 長さ ジャンル/分野 単一文/複数文 なんのための要約か？利用方法 出力形式 重要文抽出 テキストから重要な文を抜き出す要約手法 なんらかの情報をもとに重要度を計算 要約率などの条件を満たすまで文を選択する 機械学習や確率値
ウェーブレット木を試す - Negative/Positive Thinking
はじめに 巨大な文字列でも高速にクエリ処理できる噂の木を、挙動を確認するため作ってみた。 コード アルファベット(a〜z)の文字列を扱う場合 完備辞書の操作が愚直、ビット列がvector 本を参考にしたけど、2か所間違ってる？ #include <iostream> #include <vector> #include <queue> #include <cmath> //top_kのためのタプル struct ST { int t; size_t st, en; ST(int t, size_t st, size_t en):t(t),st(st),en(en){} }; bool operator<(const ST& a, const ST& b){ return (a.en-a.st) < (b.en-b.st); } //アルファベット([a-z]+)用のウェーブレット木 cla
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
RBMで遊ぶ - Negative/Positive Thinking
はじめに 深イイ学習とかで使われているらしいRestricted Boltzmann Machineでちょっと遊んでみる。 Restricted Boltzmann Machineとは 制約Boltzmann Machine 各層内のノード間の結合がないようなBoltzmann Machine この制約によって、学習時の隠れ層の各ノードが独立に計算できる RBMの学習は、「Contrastive Divergence Learning」で行うことができる http://www.cs.toronto.edu/~hinton/absps/cdmiguel.pdf http://dl.dropbox.com/u/2048288/RestrictedBoltzmannMachine.pdf コード できたモデルからどうやって生成するのかよくわからなかったので、適当にサンプリングしてみる。 #inc
Aho-Corasick法による複数文字列(パターン)検索を試す - Negative/Positive Thinking
はじめに Rabin-Karp法による複数文字列検索に続いて、同様に複数の文字列検索を行えるAC法を試しに書いてみた。 AhoCorasick法 えいほこらしっくほう 文字列探索するときに、パターンマッチオートマトン(PMA)を使い、状態を遷移させながらO(n)でパターンマッチを行う方法 入力文字列を一文字ずつ読み込みながらPMAの状態を遷移 PMAは与えられるパターンを表現する ノードは状態、辺は対応する文字、を表す PMA構築アルゴリズムは、 パターン文字列のTrieを作成 根から幅優先探索で各ノードで遷移が失敗した場合の遷移先を決定 そこへ辺を張る、を繰り返す 失敗時の遷移先の決定 trieと違って、葉ノードまでたどりきったら終了ではなく、失敗したときに遷移するノードを決めておくことで、連続して探索を行える (図1) パターン文字列「ab」と「bcd」に対して、入力「abcde」を考
決定木メモ - Negative/Positive Thinking
はじめに 決定木についてちょっと調べてみたので、メモ。 決定木(decision tree)とは 木構造(多分木)を使って、分類・回帰問題を解く root(根)を含む各内部ノードは、「変数」を表す leaf(葉)は、変数に対する「予測値、分類値」を表す 入力xを、ルートからスタートし各ノードの条件に従って葉に来て出力yが決まる 連続if-thenだと見ると理解しやすい 出力yは、分類ならクラス、回帰なら定数値などになる 訓練データD={(x,y)}から木構造を構築することを「決定木の学習」という 見た目にもわかりやすく、扱いやすい、比較的単純な機械学習法の一つ サイズが小さめならば。 精度はあまりでない(らしい) 空間を矩形領域でしか区分しないと考えるとそんな感じもする 問題点 多くの学習方法では、特徴空間の軸に平行(x_0<3.0など)なため、平行でないような場合(x_1>2x_0+3な
言語モデル構築Toolメモ - Negative/Positive Thinking
はじめに 世の中には言語モデルを構築するToolkitはたくさんあるということで、簡単に探してみた。 言語モデルツールキット SRILM - The SRI Language Modeling Toolkit http://www.speech.sri.com/projects/srilm/ Palmkit - a statistical language modeling toolkit http://palmkit.sourceforge.net/ Kylm - 京都言語モデルツールキット http://www.phontron.com/kylm/index-ja.html CMU SLM Toolkit http://www.speech.cs.cmu.edu/SLM_info.html KenLM - Faster and Smaller Language Model Querie
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
