タグ

ブックマーク / echizen-tm.hatenadiary.org (23)

  • 5/1は転職記念日なので記事を書く - EchizenBlog-Zwei

    転職して2年が経った。 転職は私の人生における最大の勝利であるので、2周年を記念して記事を書く。 さしあたり、現時点で考えていることを書いておくことで後々の参考にしたい。 転職してよかったか これは「よかった」と断言できる。 2年経ったのでさすがにそろそろ前の環境と比較してもよい頃合い(転職してすぐはバイアスがかかって何でもよく見えるので)なので書いておくが、あらゆる点で今の環境のほうが良い。 私が転職を考えていたころ「辞めて幸せになった」という資料が少なく、周辺の人の「すぐ辞める人は何をやってもダメ」的な論調に随分脅されたものだった。なので「転職して幸せになった」という事は何度でも繰り返し伝えていきたい。 能力の伸びと幸せ 人の能力は伸び続けると思う。成長が頭打ちになることはないという印象がある。 ではだれでも頑張れば幸せになれるのか?というとそうでもないと思う。何故かというと人生は有限

    5/1は転職記念日なので記事を書く - EchizenBlog-Zwei
  • 手元に置いておくと安心できる、情報系の人向けな日本語の本のリスト - EchizenBlog-Zwei

    最近、人にを薦める事が多くなった。とりあえずこの辺を読むといいですよ的なリストを作っておくと便利だと思ったので作ることにした。 以下、「事前知識のいらない入門」「事前知識はいらないけど格的な」「事前知識がないと何言ってるかわからないけど有益な情報が満載な」の3つにわけて列挙する。 事前知識のいらない入門 数式少なめ、脳負荷の小さめなをいくつか。何をやるにしてもデータ構造、アルゴリズム、数学はやっておくと幸せになれるよ。 情報検索と言語処理 データマイニングとか自然言語処理とかやりたい人にはとりあえずこれ。さすがに古い話が多くなってきたのでそろそろ新しい入門用情報検索がでないかなあと思っている。 図解・ベイズ統計「超」入門 伝説のベイジアン先生がベイズの基礎を教えてくれる。ベイズやりたい人はこれ。 珠玉のプログラミング データ構造とかアルゴリズムとかの考え方の基礎を教えてく

    手元に置いておくと安心できる、情報系の人向けな日本語の本のリスト - EchizenBlog-Zwei
  • 「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei

    「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。 とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。 まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。 親 → 子 (1) → (2, 3) (2) → (4) (3) → (5)この木構造は以下の重複あり集合によって表現することができる。 { 2, 4, 5, 5, 5 }これだけ書くとなんのこと?と思われるかもしれない。そこでこれから2つのことを説明する。ひとつは「何故、木構造が自然数の重複あり集合で表現できるか」、もうひとつは「重複あり集合で表現することに何の意味があるか」ということ。 何故、木構造が自然数の重複あり集合で表現

    「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei
  • 30分でわかる高性能な圧縮符号vertical code - EchizenBlog-Zwei

    検索エンジンの転置インデックスなどデータ列を小さいデータサイズで持たせたい、という状況がある。こういう場合圧縮符号を使うのが一般的でunary符号やgamma符号、delta符号など様々な種類がある。 圧縮符号の中でイチオシなのがvertical code(vcode)。これは岡野原(@hillbig)氏によって提案された圧縮符号で単純な仕組みでdelta符号並の性能を誇っている。 記事ではvcodeのポイントを絞って30分でわかるように解説してみる。 vcodeは棚にを並べる作業を連想すると理解しやすい。棚は予め高さが決まっているので全てのが入るような棚を用意する。つまり というようなものを想像する。 この棚は8冊のが並んでいるが左から5冊目のが他よりも背が高い。このため5冊目のに合わせて背の高い棚が必要になる。だが他のは5冊目のほどに背が高くないので、5冊目が

    30分でわかる高性能な圧縮符号vertical code - EchizenBlog-Zwei
    hiromark
    hiromark 2011/11/13
    あとでよむ。
  • 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei

    簡潔データ構造(Succinct Data Structure)の魅力を紹介するシリーズ。前回の記事では疎ベクトルを簡潔データ構造を使って効率的に実装する方法を紹介した。 前回の実装ではビットベクトルのサイズの上限が256だった。今回はこれを拡張して任意の大きさを扱える簡潔ビットベクトルの実装例を紹介する。 また前回はrank()を定数時間で実現する方法を紹介した。今回はこれを使ってselect()を二分探索(O(logN))で実装する。 以上の2つの改善によってビットベクトルのサイズに制限がなくrank()/select()の双方を備えた、実用性のある簡潔ビットベクトルが実現できる。 前回の記事: 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei サイズに制限のないビットベクトルは前回実装した簡潔ビットベクトルのsbvクラスを用いて実装する

    簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei
    hiromark
    hiromark 2011/08/20
    あとでよむ。
  • ブッチャーばんざい!「Information Retrieval(Buttcher本)」を読み始めたよ - EchizenBlog-Zwei

    タイトルのブッチャーばんざい!は某ロマンシングなRPGより。 以前@sleepy_yoshiさんにものすごい勢いで薦められて気になっていたButtcherこと「Information Retrieval: Implementing and Evaluating Search Engines」がようやく手元にきたので読み始めた。私は情報検索の教科書はそんなに詳しくないのだが@sleepy_yoshiさんが他書と比較しつつ書の優れている点を書いてくださっているので是非参考に。 情報検索ことはじめ〜教科書編その2 (2011年決定版) 〜 - 睡眠不足?! ざっと見た感じだと検索エンジンに必要な技術について実装から評価まで(まさしくサブタイトル通り!)広い範囲を的確にまとめている感じでとても好印象だった。擬似コードが豊富だしメモリやディスクについても意識した書き方をしていてとても参考になる。

    ブッチャーばんざい!「Information Retrieval(Buttcher本)」を読み始めたよ - EchizenBlog-Zwei
  • これからはじめる人のための機械学習の教科書まとめ - EchizenBlog-Zwei

    最近では企業における機械学習の認知度も高まっていてエンジニアの求人募集でも「望ましいスキル:機械学習」というのをよく見かける。特にweb系の企業だと当たり前のように機械学習を活用した魅力的なサービスが生み出されているようだ。 そんなわけで先日書いた機械学習の入門記事もそれなりに好評で末尾の教科書リストも結構参考にしていただいた様子。ということで、これから機械学習をはじめる人のためにオススメの教科書を10冊ほどピックアップしてみた。 幸いにして機械学習の分野には良書が多い。5年前はナイーブベイズすら知らなかった私も、これらの教科書のおかげでなんとか機械学習を使えるようになりました!(個人の体験談です。効果には個人差があります) 参考: 機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBlog-Zwei 最初に既存の機械学習の教科書まとめを挙げておくの

    これからはじめる人のための機械学習の教科書まとめ - EchizenBlog-Zwei
  • 機械学習超入門II 〜Gmailの優先トレイでも使っているPA法を30分で習得しよう!〜 - EchizenBlog-Zwei

    最近の論文で The Learning Behind Gmail Priority Inbox D.Aberdeen, O.Pacovsky & A.Slater というのがある。これはGmailの優先トレイで使っている機械学習のアルゴリズムについて解説したもの。というと難しそうな印象があるが、この論文で紹介されているPassive-Aggressiveという手法は実装がとても簡単。なので今回はこれについて解説するよ。 参考資料: Gmail - 優先トレイ Online Passive-Aggressive Algorithms K.Crammer et al. The Learning Behind Gmail Priority Inbox読んだメモ - 糞ネット弁慶 わかりやすい日語解説 機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBl

    機械学習超入門II 〜Gmailの優先トレイでも使っているPA法を30分で習得しよう!〜 - EchizenBlog-Zwei
  • テキスト圧縮はこれ一冊でOK!?な優良書籍「The Burrows-Wheeler Transform」を読んだ - EchizenBlog-Zwei

    以前より気になっていた書籍「The Burrows-Wheeler Transform Data Compression, Suffix Arrays, and Pattern matching」を読む機会を得ることができた。それなりに高額なだったので購入が躊躇っていたのだけど、これは自分用に購入してもいいかも。というくらいの良書だったので紹介しておく。 書はタイトルのとおりBWT(Burrows-Wheeler変換)に関する書籍。サブタイトルにあるようにデータ圧縮やSuffixArrayによる全文検索についても充実した内容になっている。最後のPattern matchingはテキストから検索キーとexactにマッチした、もしくは類似した箇所を取り出すよ、という話。2008年のなので比較的新しい話題も扱っていて満足度が高い。 また書の特色は圧縮ありきで始まり、そこから全文検索可能な

    テキスト圧縮はこれ一冊でOK!?な優良書籍「The Burrows-Wheeler Transform」を読んだ - EchizenBlog-Zwei
    hiromark
    hiromark 2011/01/16
    そろそろ復習しないと忘れてしまう。。。
  • 機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBlog-Zwei

    最近では機械学習の認知度も上がってきていて専門家でなくてもナイーブベイズやSVMなどの名前を知っている人も増えてきたように思う。 そんなわけでちょっと機械学習をはじめてみようかな、と思っている人も多いのではないだろうか。とはいえ「数式よくわからない」「確率嫌い」といった理由で尻込みしているケースも多いのでは。 そこで予備知識ゼロでもわかるような機械学習の入門記事を書いてみたよ。 機械学習を「作りたい」のか「使いたいのか」 まず最初に確認したいのがこれ。使いたいだけならまずはSVMを使ってみれば良い。世の中にはlibsvmやsvmlightという良いツールがあるのでそれを使おう。以下の記事は機械学習を「作りたい」「仕組みを知りたい」人向けの内容になっている。 「最も簡単な機械学習はナイーブベイズ」という幻想 機械学習といえばナイーブベイズという話がよくある。ナイーブ(単純)という名前からいか

    機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBlog-Zwei
    hiromark
    hiromark 2011/01/15
    僕は機械学習は専門家ではないけれどこれは良エントリだと思った。
  • 話題のwat-arrayを使ってBurrows-Wheeler変換(BWT)してみた - EchizenBlog-Zwei

    先日PFIの岡野原氏によってwat-arrayというライブラリが公開された。 wat-array : wavelet木を利用した高速配列処理ライブラリ : Preferred Research Blog このライブラリは内部でウェーブレット木(wavelet tree)という簡潔データ構造(succinct data structure)を使っている。このため文字列に対するrank()やselect()などの操作が効率的にできるようになっている。 ・・・といっても馴染みのない人にとっては何が嬉しいのかピンと来ないかもしれない。そこでBurrows-Wheeler変換(BWT, Burrows-Wheeler Transform)を例にとってwat-arrayの使いみちを説明してみる。 Burrows-Wheeler変換というのはテキストを同じ文字が並びやすいように変換したもので、通常ランレ

    話題のwat-arrayを使ってBurrows-Wheeler変換(BWT)してみた - EchizenBlog-Zwei
  • 「第3回自然言語処理勉強会@東京」でCSAについて発表します - EchizenBlog-Zwei

    @nokunoさんの好意で「第3回自然言語処理勉強会@東京」でCompressed Suffix Arrayについて発表させていただくことになりました。 つきましては参考のため発表資料を以下に置いておきます。参加される方はもちろん、興味のある方はご覧になっていただけるとうれしいです。 第3回自然言語処理勉強会@東京 : ATND 第3回自然言語処理勉強会@東京を開催します - nokunoの日記 なお資料は以下の皆様のアドバイスを頂きました。ありがとうございました(とくに@overlastさんには4-5時間もお付き合い頂きました。おかげさまでスライドの質が大幅アップしました。感謝)。 @overlastさん @tamago_donburiさん @tsubosakaさん @machyさん

    「第3回自然言語処理勉強会@東京」でCSAについて発表します - EchizenBlog-Zwei
    hiromark
    hiromark 2010/11/10
    この話をここまできれいにまとめるとはすばらしい。
  • Suffix Array(接尾辞配列)を学びたい人のためのリンク集 - EchizenBlog-Zwei

    私がCompressed Suffix Arrayを学ぶのに参考にした資料へのリンクをまとめてみた。 CSAだけじゃなく、これからSuffix Arrayを学ぶ人にも便利かもしれない。 解説記事 # [を] Perl による Suffix Array の実装] SUFARYの開発者、たつを氏による解説 perlで20行くらいでSuffix Arrayが作れる 入門用におすすめ # DO/Suffix Array 岡野原氏によるSuffix Arrayの解説記事 高速化などの高度な話題が豊富 中級者向け # white page Suffix Arrayのリンク集が充実 多くのライブラリが公開されている ツール・ライブラリ # SUFARY 臨時復旧ページ たつを氏によるSuffix Arrayライブラリ 非常に使い勝手が良い # sary: Suffix Arrayのライブラリとツール 高

    Suffix Array(接尾辞配列)を学びたい人のためのリンク集 - EchizenBlog-Zwei
    hiromark
    hiromark 2010/10/28
    おお、まとまっていてすばらしい。
  • CSAを使った全文検索ライブラリtsubomiを公開してみる - EchizenBlog-Zwei

    しばらく前から作っていた全文検索ライブラリtsubomiを公開しておく。 ライブラリは接尾辞配列(Suffix Array)というアルゴリズムを使っていて、入力として与えたキーワードを含む行をテキストデータから探して、その行と出現位置を取得できる。さらに圧縮接尾辞配列(Compressed Suffix Array)による圧縮もサポートしているのでインデックスサイズを小さく抑えることができる。 ライブラリは検索のためのAPIのほかに、インデックス作成、圧縮、検索を行うツールが付属している。ツールを使うだけでも、ある程度のことができる。 以下、簡単に紹介。 tsubomiはGoogleCodeでコードを管理している。詳細は下記URLを参照。 http://code.google.com/p/tsubomi/ コード管理にはsubversionを使っているので $$ svn checkou

    CSAを使った全文検索ライブラリtsubomiを公開してみる - EchizenBlog-Zwei
    hiromark
    hiromark 2010/09/05
    おお、これは GJ!
  • 圧縮接尾辞配列ライブラリ csalibの圧縮率の高さは異常 - EchizenBlog-Zwei

    圧縮接尾辞配列の第一人者、定兼先生が開発、公開してくださっているcsalibを試してみたのでメモ。 http://researchmap.jp/sada/csalib/ まずはgooglecodeからcsalibとdbwtを入手。解凍しmakeする。 $$ mkdir csalib/ $$ cd csalib/ $$ wget http://csalib.googlecode.com/file/csalib100810.zip $$ unzip csalib100810.zip $$ make $$ cd .. $$ mkdir dbwt/ $$ cd dbwt/ $$ wget http://csalib.googlecode.com/file/dbwt100730.zip $$ make $$ cd ..このライブラリはdbwtでテキストをBurrows-Wheeler変換し、その後m

    圧縮接尾辞配列ライブラリ csalibの圧縮率の高さは異常 - EchizenBlog-Zwei
    hiromark
    hiromark 2010/08/19
    メモメモ。
  • 5分でわかる(かもしれない)圧縮の基本 - EchizenBlog-Zwei

    大規模データを日常的に扱う人にとって、データ圧縮は基。絶対ないと困るわけではないけど、あると格段に世界が広がる。ドラクエで言うところのルカニみたいなもの。 でも圧縮というとデータをバイナリで持たないといけないとか、なんとなく面倒なので目を背けがち。そこで5分でわかるような感じで説明を書いておく。 基的な圧縮の方法は差分圧縮というのがある。今回はこれを説明する。 char型のデータが8つ並んでいると考える。 6 3 2 1 7 5 4 8とりあえずバイナリにしてみる。便宜上、縦に書く。 6 3 2 1 7 5 4 8 =============== 1の位:0 1 0 1 1 1 0 0 2の位:1 1 1 0 1 0 0 0 4の位:1 0 0 0 1 1 1 0 8の位:0 0 0 0 0 0 0 1 16の位:0 0 0 0 0 0 0 0 32の位:0 0 0 0 0 0 0 0

    5分でわかる(かもしれない)圧縮の基本 - EchizenBlog-Zwei
    hiromark
    hiromark 2010/08/05
    ああ、こう説明すればまずはわかりやすいのか。。。
  • Compressed Suffix Arrayの記事まとめ - EchizenBlog-Zwei

    一応CSAの記事を書き終えたので、各記事へのリンクリストを。 補足:記事を7つも読むの面倒くさい人は、↓にもう少し簡単な圧縮法の解説を書いておいたので参照されたい。 15分でわかる(とうれしい)Suffix Arrayの簡単な圧縮法 Compressed Suffix Arrayの解説(1) -Suffix Array- Compressed Suffix Arrayの解説(2) -SAの計算量- Compressed Suffix Arrayの解説(3) -圧縮の方針- Compressed Suffix Arrayの解説(4) -unary記法- Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- Compressed Suffix Arrayの解説(6) -B Vectorと Ψ Vector- Compressed Suffix

    Compressed Suffix Arrayの記事まとめ - EchizenBlog-Zwei
    hiromark
    hiromark 2010/08/04
    す、すごい。ちゃんと読む。読みますってばー。
  • 目的は主観的に、手段は客観的に考える - EchizenBlog-Zwei

    ここ数年で色々な経験をした結果 目的は主観的に、手段は客観的に考えるのが良い気がしたのでメモしておく。 ある事をやろうとする。このある事を便宜上「目的」とよぶ。客観的に目的を検証すると、利点と欠点がリストアップされる。 だが大抵欠点の方が多いので目的を諦めるのが最適解になる。これだと何もしないのが最適になってしまい何も変わらない。 そこで目的を主観的に決定する。自分が「これはッ!」と思った事を目的にする。ここは決めたら曲げない。 そして目的を実行するための「手段」を考える。手段も便宜上の表現で、具体的な手段に加えて目的を達した時のリスクやリターンについても考える。リスクがある場合には、リスクは回避できるか、回避できないならダメージをリカバーするにはどうするか、を客観的に考える。 目的フェイズのポイントはとにかく自分の気持に正直になること。良いと思った部分にとにかく目を向けること。手段フェイ

    目的は主観的に、手段は客観的に考える - EchizenBlog-Zwei
    hiromark
    hiromark 2010/08/04
    なるほどおもしろい。この発想はなかったわ。
  • Suffix Array向きのソートアルゴリズム - EchizenBlog-Zwei

    Suffix Arrayのソートアルゴリズムは以前当ブログで紹介したSAIS(参考)など、Suffix Arrayの性質を生かしたものが多い。そして一般にSuffix Arrayはバイト単位でインデックスを与えるので、これを前提としている場合が多い。大抵の場合はそれでOKなのだが、問題がある場合がある。 それは、インデックスをUTF8の文字単位で与えたい場合や、単語単位で与えたい場合。この場合、大抵のSuffix Array向けソートアルゴリズムが使えない。そこで重要になってくるのが文字列に対する高速ソートアルゴリズム。これならばインデックスが飛び飛びでも使えるので汎用性がある(Suffix Arrayに特化した手法が使えないので速度面では劣るかもしれないが。) 例えば、SUFARY(参考)で使われているmultikey-qsortという方法は古くからある方法だがシンプルかつ高速で、とても

    Suffix Array向きのソートアルゴリズム - EchizenBlog-Zwei
    hiromark
    hiromark 2010/08/04
    あとでよむ
  • perlでSGD版SVMを書いてみた - EchizenBlog-Zwei

    SVM(Support Vector Machine, サポートベクターマシン, サポートベクトルマシン)をperlで書いてみた。 実装が簡単という理由からSGDによるオンライン学習を行っている。カーネル行列(グラム行列)をメモリに持っておかないといけないので当の意味ではオンライン化されていないが、SVMを理解するためのサンプルとしてはSGDで実装するのは手頃ではないかと思う。 #!/usr/local/bin/perl # $Id$ use strict; use warnings; my $d = 3; # x ∈ R^3 my $n = 6; # number of training data my $t = 10; # iteration # label (warm color:1, cold color:-1) my @yy = (1, -1, -1, -1, 1, 1); #

    perlでSGD版SVMを書いてみた - EchizenBlog-Zwei
    hiromark
    hiromark 2010/04/19
    Perl で実装。