プログラミング

Random Projectionを試す

はじめに 言語処理を行う場合、単語数を考えると高次元スパースなベクトルを扱うことが多い。 次元削減を行える手法の一つである、Random Projectionを試してみる。 Random Projectionとは 乱数を要素に持ち、各列ベクトルの大きさが1である行列Rを用意して…

Label Propagationを試す

はじめに 前から気になっていた、label propagationを試してみる。 マルチエージェントとかの合意問題っぽい感じ? Learning fron Labeled and Unlabeled Data with Label Propagation http://lvk.cs.msu.su/~bruzz/articles/classification/zhu02learning.p…

n列目まででdiff

はじめに タブ区切りなどのファイルで、n列目までを考慮したdiffなどを取りたいけど、出力はその行のすべてを表示してほしい。 コマンドの組み合わせだけでやりたいけど、いい方法が思いつかない。。 コード とりあえず1列目だけでdiff。 #!/usr/bin/perl # …

TWCNB分類器を試す

はじめに テキスト分類でよく使われるNaive Bayesにはいくつかの厳しい仮定や条件があり、それによって性能が落ちてしまっている。 経験則をいれたりして性能を向上させたTWCNB分類器を試してみる。 多項モデルによるNaiveBayes l_MNB(d) = argmax_c{ log P(…

トピックモデルメモ

はじめに トピックモデルについてメモ。 トピックモデルとは 文書は、何らかの話題について書かれていたりする 「ある文書内に一緒にでてくる単語は、意味的な関連性が強い」など考えられる トピックモデルは、文書から「何らかの話題(=トピック)」を発見す…

SCWを試す

はじめに 分類器の決定版(?)的なSoft Confidence Weighted Learningを試してみた。 Soft Confidence Weighted Learningとは 2012年に提案された、各重みを正規分布と考え更新時にその分布が変わるようにしたConfidence Weighted(CW)関係のノイズに強くなっ…

Z algorithmで文字列探索を試す

はじめに 名前がかっこいい。 codeforcesにある解説を試してみる。 Z algorithmとは 文字列Sと部分文字列S[i..]の最長共通接頭辞数をZ[i]とし、すべてのiについて、それをO(n)で求めるアルゴリズム 単純な方法だとO(n^2) 1996,97年あたりにGusfieldによって…

Locality Sensitive Hashによる類似ベクトル検索を試す

はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 Locality Sensitive Hash 類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関…

ナイーブベイズで「日本」の読み分けを試す

はじめに 「日本」は、「にほん」と「にっぽん」どちらの読み方もできる。 しかし、読み分けが必要な場合も存在する。(東京の日本(にほん)橋と大阪の日本(にっぽん)橋、会社名、など)同型異音語や多義性解消だと、よく周辺文字を素性にして分類問題を解く、 …

MDS&文字列カーネルの可視化を試す

はじめに せっかく文字列カーネルで遊んでみたので、可視化も試してみる。 Multidimensional Scalingとは n個のm次元ベクトルについて、それらの距離のみが与えられる それらの距離をできる限り保存して低次元空間(1,2,3次元など)にマッピングする方法 通常…

文字列カーネルで遊ぶ

はじめに ちょっと、高次元特徴空間での2つの文字列の像の内積である文字列カーネルで遊んでみる。 文字列カーネルを類似度として使いたい。遊びなので、数式はちゃんと追ってない、、、 文字列カーネル 文字列に対するカーネル カーネルKは、入力空間Xから…

くさいセリフ判定

はじめに くさいセリフを恋人につぶやいてドン引きされてしまう問題を自然言語処理の力で解決するため、くさいセリフかどうかを判定するプログラムを試してみる。 , -──- 、 /:::::::::::::: ::\ /::::::::::: ::∨ト、 こいつはくせえッー! :::::::::: :: レ…

HyperLogLogで遊ぶ

はじめに 「さぁ、お前の罪の異なり数を数えろ!」と言われたときに使えそうな「HyperLogLog」という異なり数をカウントする方法を教えてもらったので、遊んでみた。 いつもながら論文ちゃんと読んでないので、条件やコード間違ってるかも。。。 HyperLogLog…

ウェーブレット木を試す

はじめに 巨大な文字列でも高速にクエリ処理できる噂の木を、挙動を確認するため作ってみた。 コード アルファベット(a〜z)の文字列を扱う場合 完備辞書の操作が愚直、ビット列がvector 本を参考にしたけど、2か所間違ってる? #include <iostream> #include <vector> #include <queue></queue></vector></iostream>…

へ、変態っ!!読めないからやめてっ!bit使ったデータ構造・アルゴリズム実装集

この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。12月20日追記: Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています!必読ですね!!!!:) はじめに Y^´ ∨// /,∠ ,. ' /l//…

RBMで遊ぶ

はじめに 深イイ学習とかで使われているらしいRestricted Boltzmann Machineでちょっと遊んでみる。 Restricted Boltzmann Machineとは 制約Boltzmann Machine 各層内のノード間の結合がないようなBoltzmann Machine この制約によって、学習時の隠れ層の各ノ…

FeedforwardNeuralNetworkで遊ぶ

はじめに 最近再び注目を浴びているニューラルネットで遊んでみた。 簡単な3層の完全結合の階層型ニューラルネット(多層パーセプトロン)。 XOR 2入力1出力で、xorの出力は線形分離可能ではない (0,0)->0, (1,1)->0, (0,1)->1, (1,0)->1 単純パーセプトロンで…

Aho-Corasick法による複数文字列(パターン)検索を試す

はじめに Rabin-Karp法による複数文字列検索に続いて、同様に複数の文字列検索を行えるAC法を試しに書いてみた。 AhoCorasick法 えいほこらしっくほう 文字列探索するときに、パターンマッチオートマトン(PMA)を使い、状態を遷移させながらO(n)でパターンマ…

構文解析メモ

はじめに 「構文解析」まわりについてちょっと調べたのでメモ。 ただ、資料が少なくて内容が怪しい部分が多い。 構文解析とは 入力された文に対して、文を構成しているそれらの構文構造を同定すること 文法規則が定められたプログラミング言語、正規表現、HT…

正規表現エンジンメモ

はじめに 正規表現とそのエンジンについてちょっとメモ。 正規表現とは 文字列の集合を文字列で表現する方法の一つ 正規言語を表現するための手段 「正規言語」とは、「有限オートマトンで受理可能」な言語 正規表現と有限オートマトンは記述能力において等…

焼きなまし法で単語分割

はじめに オライリーの「入門自然言語処理」に、焼きなまし法を使った教師なし単語分割について書かれていたので、これを試す。 アプローチ 「出現単語数」+「のべ出現単語数」+「入力文の文字数(固定)」=目的関数を最小化 単語の区切り位置を温度によっ…

木メモ

はじめに 立派な庭師になるために、木についてちょっと調べてみたので、まとめておく。 木(構造)とは 閉路を含まない無向グラフを「森」という 連結な森を「木」という 与えられた頂点が全てつながっていて、閉路を含んでいない 閉路を含まない有向グラフは…

焼きなまし法で遊ぶ

はじめに 焼きなまし法について、どんな挙動で、どこを気をつけないといけないのかよくわかってないので、遊んでみる。焼きなまし法メモ : http://d.hatena.ne.jp/jetbead/20111014/1318598381 評価関数 簡単のために、4次関数を使って、初期位置は小さい山…

連立一次方程式で遊ぶ

はじめに 連立一次方程式(Ax=b)を直接法(ガウスジョルダン法)、反復法(最急降下法、共役勾配法)でちょっと解いてみた。 コード #include <algorithm> #include <cmath> #include <iostream> #include <vector> static const double EPS = 1e-8; typedef std::vector<double> vec; //ベクトル typedef std:</double></vector></iostream></cmath></algorithm>…

Rabin-Karp法による複数文字列(パターン)検索を試す

はじめに 前から気になっていたRabin-Karp法による複数文字列検索を試しに書いてみた。ここでいう問題は、「ある長い文字列の中に、複数の探したい部分文字列が含まれるかどうか、含まれる場合そのindexは?」を考える。 Rabin-Karp法 文字列探索するときに…

決定木メモ

はじめに 決定木についてちょっと調べてみたので、メモ。 決定木(decision tree)とは 木構造(多分木)を使って、分類・回帰問題を解く root(根)を含む各内部ノードは、「変数」を表す leaf(葉)は、変数に対する「予測値、分類値」を表す 入力xを、ルートから…

ノンパラベイズな言語モデルを試す

はじめに 最近「言語モデル」がマイブームなので、最近有名になりつつあるというMCMC法を使ったベイズな言語モデルとして、「階層的Pitman-Yor言語モデル(HPYLM)」を試しにちょっと作ってみた。とりあえず、文字bigramのHPYLMを試してみる。 毎度のことなが…

ノンパラの実験

はじめに ノンパラメトリックに関する論文やチュートリアルを見ていると「混合正規分布の混合数も推定できちゃうんですよぱねぇ」みたいなこと書いてあったり、その図が載ってたりする。 試してみたいなぁと思ったので、書いて実験してみる。理解が乏しいの…

ギブスサンプリングによるベイズ推定

はじめに MCMCによるベイズ推定として、正規分布に従うデータが与えられたとき、その正規分布のパラメータ(平均と分散)が従う分布および推定値を求める。尤度関数が正規分布の場合、共役事前分布はそれぞれ、平均は正規分布、分散は逆ガンマ分布になるので、…

c++でgnuplot用の簡単なプロットファイル出力

はじめに 気分転換に、よく使うgnuplotのplotファイル出力クラスを作ってみる。 状況に応じて修正して使おう。。。 コード #include <iostream> #include <fstream> #include <vector> #include <string> #include <utility> class SimpleGnuplotOutput { std::string png_filename; int png_width, png_h</utility></string></vector></fstream></iostream>…