2012/6/21のPFI全体セミナー, 「文字列データ圧縮ことはじめ」の内容です。データ圧縮の話とそれに纏わる歴史と最近の話を紹介しています。
2012/6/21のPFI全体セミナー, 「文字列データ圧縮ことはじめ」の内容です。データ圧縮の話とそれに纏わる歴史と最近の話を紹介しています。
概要 オンラインでの分類学習の世界では,CWが非常に強力なアルゴリズムとして注目されています.特に,その圧倒的な分類精度及び収束速度は圧巻の一言であり,自然言語処理を中心に様々な分野で応用例や派生アルゴリズムが提案されています*1. 一方で,ノイズデータのが混入していた場合に精度がガタ落ちする性質がCWの重大な欠点として多くの人から指摘されていました.ノイズが予め取り除かれている実験設定ならば良いのですが,ノイズが含まれている可能性の高い実データにはCWは中々不便.この問題を解決するため,ノイズ耐性の強いCW系アルゴリズムの決定版(?)として,SCW (Soft Confidence-Weighted)アルゴリズムがICML2012という会議で提案されました.本エントリでは,SCWの紹介を行います. Exact Soft Confidence-Weighted Learning, Wang
ICML2008で発表されたDredzeらのConfidence Weighted Linear Classificationを読んだ。これは線形分類器を学習する新しいオンライン学習型アルゴリズムの提案である。すぐに使える実装としてはOLLというオープンソースのライブラリがあり、実際に良い実験結果が出ているようだ。 Confidence Weightedのアイデアは、よく出てくる素性に関しては一回の更新における数値の変更量を減らしてやり、あまり出てこない素性に関しては、一回の更新でぐっと値を変更してやろう、というものである。 こういった新しい更新方法を考案した動機を明らかにするために、Perceptronを使って、単語を素性として評判分類の学習を行うような問題を考えてみる。肯定的な評価のサンプルとして"I liked this author."というものがあったとすると、このサンプルの分類
2. 自己紹介:徳永 拓之 ● twitter id:tkng ● (株) Preferred Infrastructure 勤務 ● 守備範囲:レコメンド・NLPなど ● カレーを食べるのが趣味 ● 上野デリーのコルマカレーが好きです ● 早売りの週刊少年ジャンプを読むのも好き 3. 宣伝:NLP2011で発表します C4-6 日本語かな漢字変換における識別モデル の適用とその考察 ○徳永拓之, 岡野原大輔 (PFI) 3月10日(木) 13:00-15:30 (A1-201教室) ● 今日の発表でここが一番NLPっぽい 4. 発表の概要 ● ランク学習とは ● Confidence Weightedとは ● Confidence Weightedによるランク学習 中身の薄い発表なのでゆったりと リラックスした気持ちで聞くのが オススメ!
Statistics Favorites 0 Downloads 0 Comments 0 Embed Views 0 Views on SlideShare 0 Total Views 0 機械学習のPythonとの出会い(1):単純ベイズ基礎編 — Presentation Transcript 機械学習のPythonとの出会い (1) 単純ベイズ:入門編 神嶌 敏弘 ( http://www.kamishima.net/ ) Tokyo.Scipy #4 (2012.06.18) 1 自己紹介• 専門について • 機械学習やデータマイニングが専門と名乗ってます • PRML本とか翻訳しましたが,変分ベイズとか,MCMC とか複雑 なことは全然してません • 手法を深掘りすることよりも,新しい問題設定を考えて,できるだ け簡単な方法で解くようにしたいと思ってます• NumPy / Sc
最終更新日: 2000-11-14 (公開日: 2000-11-14) Suffix Arrayは巨大なテキストを高速に検索するためのデータ構造 です。テキストのサフィックスを辞書順 (ABC順) に並べ、それに 対するポインタを配列として格納したものが Suffix Array です。 サフィックスとはテキスト中のある位置からテキスト末尾までの文 字列のことをいいます。テキストへの検索は Suffix Array を用い て 2分探索の要領で行います。 では、 Suffix Arrayの構築に移りましょう。ここでは ``abracadabra''というテキストに対して Suffix Array を作成す ることにします。 まず最初に、テキストに対してインデックスポイントを割り当てる 必要があります。インデックスポイントは、検索が行える位置を指 定したものです。この例では、どの位置からでも
FreeBSD - The Power To Serve why GNU grep is fast (なぜGNU grepは高速なのか)といったタイトルの興味深いメールがFreeBSD開発者メーリングリストに投函された。メールを出したのはGNU grepのオリジナル開発者であるMike Haertel氏。Mike Haertel氏はFreeBSDユーザでもあり、FreeBSD開発者メーリングリストで興味深いやりとりがあったため、このメールを流したとしている。Mike Haertel氏の紹介する内容はgrep(1)の実装のみならず、高速な文字列処理を実現するひとつの方法として参考になる。紹介されているGNU grep高速さの秘訣は次のとおり。 GNU grepは入力バイトのすべてをチェックするようなことは避けている。 GNU grepはバイトごとに適用する操作を極力最小限に減らしている。 G
はじめに この文書は、 Steven Bird, Ewan Klein, Edward Loper 著 萩原 正人、中山 敬広、水野 貴明 訳 『入門 自然言語処理』 O'Reilly Japan, 2010. の第12章「Python による日本語自然言語処理」を、原書 Natural Language Processing with Python と同じ Creative Commons Attribution Noncommercial No Derivative Works 3.0 US License の下で公開するものです。 原書では主に英語を対象とした自然言語処理を取り扱っています。内容や考え方の多くは言語に依存しないものではありますが、単語の分かち書きをしない点や統語構造等の違いから、日本語を対象とする場合、いくつか気をつけなければいけない点があります。日本語を扱う場合にも
本稿では,sasanqua_neufのチューリング完全性を証明します.具体的には,チューリングマシンのエミュレータを構成することでチューリング完全性を示します. 概要 sasanqua_neufのテープTをチューリングマシンのテープと「概ね」同一視し,チューリングマシンの状態をCの値によって「概ね」表現します.C言語風にエミュレータの概要を記すと,全体の構造としては int Cq=1; while(Cq != n+1){ switch(Cq){ case 1: //qの添え字が1 switch(T[H]){ //T[H]にσが格納されている case 1: //σの添え字が1 T[H] = [δ_2(q_1,σ_1)]; //T[H]をテープと同一視 H += [δ_3(q_1,σ_1)]; //ただしLeft=-1,Right=+1と見て while(T[H] == 0){getchar
ふと、ビット並列アルゴリズムを使った編集距離を計算するアルゴリズムを書きたくなったので書いてみた。 まず、通常の編集距離であるLevenshtein Distanceを求めるアルゴリズムは以下のように書ける int levenshteinDistance(String A, String B) { int m = A.length(); int n = B.length(); int dp[] = new int[n + 1]; int next[] = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i; for (int i = 1; i <= m; i++) { next[0] = i; for (int j = 1; j <= n; j++) { if (A.charAt(i - 1) == B.charAt(j - 1))
[pukiwiki] Pythonで名寄せするプログラムを書いてみました。 (まだ年賀状のリスト作りには早いですけれども。) 参考文献 -[[【PDF】 圧縮を用いた類似度判定のための計算実験:http://www.tani.cs.chs.nihon-u.ac.jp/g-2008/shu/tyukan_shu.pdf]] 文字列類似度の判定には、こちらの式を、ほぼ そのまま使用しています。 [/pukiwiki] [pukiwiki] zlib(gzip)による圧縮を利用しているので、たぶん [[Nグラム>ググる:Nグラム]]による比較に近い結果が得られるんじゃないかという期待から、上記のアルゴリズムを使用しました。 —- 具体的には、表記にブレのある住所録ファイルsample.csvについて、似た文字列同士が隣り合わせになるように並べなおします。 (むしろ、クラスタリングに近いかも) 動
Church Numerals と Lambda Calculus アルゴリズムとデータ構造入門 補足 後半は佐藤雅彦先生に教えてもらいました. SICP Exercise 2.4 〜 Exercise 2.6 誤解を恐れずに大雑把にいうと, λ計算では名前つきのシンボル (名前付きの手続き) による再帰呼出しや special form が使えないところが Scheme と違うところです. そのため, λ計算を Scheme で行うためにはいろいろな工夫が必要となります. そのポイントは closure (閉包) と呼ばれる構造です. 自然数 n の Church numeral を c(n) とすると, c(n) f x = (f ... (f x)), ただし, f は n 回出現. となることを利用します. まず, c0 と successor を定義します. (SICP Ex.
「ノンパラメトリック」って言うくらいだからパラメータ無いんかと思ってたら、パラメータめっちゃあるし。 機械学習のネーミングのひどさはこれに始まった話じゃあないけど、それにしたって。 ノンパラの一番素朴なやつ( K-means とか)は本当にパラメータ無くてデータだけだから納得なんだけど、だんだん欲が出てパラメータ足しちゃったり派生させちゃったりしてるうちに、よくわかんなくなってきちゃったんだろうかねえ。まったく。 どれどれ、と英語版 Wikipedia の "Non-parametric statistics" を見たら、なんか意味が4種類くらい書いてあるし。じゃあ名前分けろよ。 en.wikipedia.org とりあえずここで言う「ノンパラ」とは、変数の個数決めなくていい「分布の分布」なメタっぽいやつのこと。つまりディリクレ過程とか、ディリクレ過程とか、そこらへん。 「あー、ノンパラベ
以前より気になっていた書籍「The Burrows-Wheeler Transform Data Compression, Suffix Arrays, and Pattern matching」を読む機会を得ることができた。それなりに高額な本だったので購入が躊躇っていたのだけど、これは自分用に購入してもいいかも。というくらいの良書だったので紹介しておく。 本書はタイトルのとおりBWT(Burrows-Wheeler変換)に関する書籍。サブタイトルにあるようにデータ圧縮やSuffixArrayによる全文検索についても充実した内容になっている。最後のPattern matchingはテキストから検索キーとexactにマッチした、もしくは類似した箇所を取り出すよ、という話。2008年の本なので比較的新しい話題も扱っていて満足度が高い。 また本書の特色は圧縮ありきで始まり、そこから全文検索可能な
本日 1/16(日) にニフティさんにて開催された 第9回 データマイニング+WEB 勉強会@東京 にのこのこ参加してきました。主催の @hamadakoichi さん、運営の @doryokujin さん、講演者、参加者、そして会場を提供して下さったニフティさん、各位ありがとうございました。 前回参加したときに、はまださんに「機械学習の全体像を話して」という無茶振りされて、うーん直球でそれにぶつかるのはさすがに難しすぎる。いろいろ考えてみて、そっちの専門じゃあないエンジニアが機械学習を学ぶには、という話にさせていただいた。 資料はこちら。 機械の代わりに人間が学習入門 from Shuyo Nakatani 前半はパワポの画面切り替えを駆使したちょいとした仕掛けがあったんだけど、slideshare にすると全く意味が無くなってしまうので、バッサリ削除。内容はあんまり変わってないので大丈
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く