自然言語処理における半教師あり学習のテキスト - 武蔵野日記
最近移動続きであまり研究に時間は割けないのだが、本は読めるということで本を2冊、サーベイ的な記事を3本(うち2本はチュートリアルスライドつき)を紹介する。まず Semisupervised Learning for Computational Linguistics (Chapman & Hall/CRC Computer Science & Data Analysis) 作者: Steven Abney出版社/メーカー: Chapman and Hall/CRC発売日: 2007/09/17メディア: ハードカバーこの商品を含むブログ (4件) を見る を読む。この本の著者の Steven Abney はブートストラッピングの理論的解析をした人で、 Steven Abney. Bootstrapping. 40th Annual Meeting of the Association fo
Algorithm Implementation - Wikibooks, open books for an open world
The purpose of this wikibook is to show how common algorithms are written in various programming languages, providing code implementations and explanation. The plan for this book is initially to collect code from some Wikipedia articles. Then the code can be expanded upon, perfected, and heavily commented to provide insight into how it works.
新はてなブックマークでも使われてるComplement Naive Bayesを解説するよ - 射撃しつつ前転 改
新はてブ正式リリース記念ということで。もうリリースから何週間も経っちゃったけど。 新はてなブックマークではブックマークエントリをカテゴリへと自動で分類しているが、このカテゴリ分類に使われているアルゴリズムはComplement Naive Bayesらしい。今日はこのアルゴリズムについて紹介してみる。 Complement Naive Bayesは2003年のICMLでJ. Rennieらが提案した手法である。ICMLというのは、機械学習に関する（たぶん）最難関の学会で、採択率はここ数年は30%を切っている。2003は119/371で、32.1%の採択率だったようだ。 Complement Naive Bayesの位置づけは 実装が簡単 学習時間が短い 性能もそこそこよい という感じで、2003年段階にあっても、絶対的な性能ではSVMに負けていた。しかし、学習が早いというのは実アプリケーシ
終了いたしました。
作者ホームページサービス（hp.vector）は終了いたしました。 長らくのご利用、ありがとうございます。 ご不明な点があれば、お問い合わせページをご覧の上、お問い合わせください。 ※15秒後にトップページに戻ります。 (c) Vector HOLDINGS Inc.All Rights Reserved.
Google Research Publication: MapReduce: Simplified Data Processing on Large Clusters
MapReduce: Simplified Data Processing on Large Clusters Jeffrey Dean and Sanjay Ghemawat Abstract MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with t
d.y.d.構文解析の話をしよう
16:46 08/03/30 YZ1.DLL 0.30 リリース しました。 具体的には、ヘッダの格納ファイル数フィールドに実際より大きい値が入ってると変なとこ読もうとして落ちるバグ修正。 GreenPad の修正は来週くらいには…。 Booooooost Boost 1.35.0 来てました。 Asio と Fusion と GIL の三枚看板がでかいですが、Bimap が地味に便利だ。 あと、mbさんのEgg のレビューが明日からでしょうか。（また スケジュール から消えてますが…Protoが入る前までロールバックしてる？） 他人事ながらドキドキ。 17:36 08/03/28 ケース 十年来の疑問なんですが、"case" に単独で対応する日本語ってなんになるんですかね。 "case-insensitive" や "lowercase" の "case"。単に "case-insens
初音ミクとかの音声合成のしくみ
２００７年に「初音ミク」という歌声合成ソフトがブレイクしました。 そこで、わけもなく「音声合成のしくみ」を簡単に解説します。 とはいっても、VOCALOIDシリーズは手法が明かされていないので、 かなり推測が入っています。 その推測した部分が誤っていたので、 この色で加筆します（２００８年３月２９日）。 誤っている部分もそのまま残してあります。 また、手法もかなり明かされているようです。 ところで、結構たくさん図がありますが、 あまり正確ではありません。 また、内容そのものもかなり簡易化してあります。 音声合成って何？ まずは音声合成とはなんぞやという話なのですが、 一般的には、文字を音声信号にすることです。 イメージとしてはこんな感じです。 初音ミクの場合、そこに音程や音の長さやその他いろいろも入ってくるので、 イメージとしてはこうなります。 音声波形を拡大してみる 一般に、音声波形はな
音声認識のしくみ
音声認識を紹介するページ とにかくここでは、 だらだらと「音声認識」というモノを紹介します。 全体が（ほぼ）このページ一枚に収まっています。 ところどころにリンクがありますが、 そのリンク先には、 難しい話やこぼれ話みたいなものがちょこちょことあります。 ところで、話を簡単にするために、 ちょっと嘘を混ぜています。 そうでないと、ものすごく複雑な話になるので。 音声認識ってなにさ 簡単に言ってしまえば、 人間が喋った声を機械が文字に直すことです。 図で描くとこんな感じです。 左側が音声波形（つまり、声を図に表している）で、 右側がそれをひらがなに直したものです。 左側の音声波形を少し詳しく見てみる 人間は耳で音を聞きますが、 機械はマイクで音を聞きます。 そして、マイクで収録された音をそのまま表示させると、 下のような感じになります。 横軸が時刻で、縦軸が振幅です。 音声というのは、ようす
GC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）
GCアルゴリズム詳細解説 日本語の資料がすくないGCアルゴリズムについて詳細に解説します トップページページ一覧メンバー編集 × GC 最終更新： author_nari 2010年03月14日(日) 20:47:11履歴 Tweet このWikiが目指す所 GCとは？ GCを学ぶ前に知っておく事 実行時メモリ構造 基本アルゴリズム編 Reference Counter Mark&Sweep Copying 応用アルゴリズム編 IncrementalGC 世代別GC スナップショット型GC LazySweep TwoFinger Lisp2 Partial Mark and Sweep -Cycle Collection- Mostly Parallel GC train gc MostlyCopyingGC(Bartlett 1989) TreadmillGC(Barker 1992)
Chord - Wikipedia
Chordでは、コンテンツのハッシュ値を求める関数にSHA-1を採用するのが一般的である。ネットワークに参加するノードは、SHA-1のハッシュ値の値域を満たす一意なが割り当てられる。 ここで、という関数を定義する。この関数は、ハッシュ値が与えられたとき、値を増加させる方向で次に存在しているノードのを返す。なお、とは接続されていると考える。 ネットワークで情報を共有する際には、共有したい情報のハッシュ値をとしてを満たすを持つノードが、実際に情報を保持しているノードの位置を示すIPアドレス等の情報を保持する。 また、ネットワークに参加するノードは、自身のをとした場合、 , ただし のをもつノードのIPアドレスをルーティングテーブルとして保持する。 共有されている情報を検索する際には、検索したい情報のハッシュ値をとしたとき、としてが割り当てられているノードを各ノードのルーティングテーブルを利用し
ConsistentHashing - コンシステント・ハッシュ法
ConsistentHashing - コンシステント・ハッシュ法 目次 この文書について コンシステント・ハッシュ法 実例 実装 用途 コンシステント・ハッシュ法 この文書について "Tom White's Blog: Consistent Hashing" の日本語訳です. http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html 推敲歓迎: 誤訳, タイポ, 訳語の不統一, そのほか... 原文のライセンス: http://creativecommons.org/licenses/by-nc-sa/2.0/ 私は今までに何度かコンシステント・ハッシュ法にとりくんだことがある。 このアイデアをあらわした論文 ( David Karger らによる Consistent Hashing and R
Diary 2005-1
１９９７年 １月 ２月 ３月 ４月 ５月 ６月 ７月 ８月 ９月 １０月 １１月 １２月 １９９８年 １月 ２月 ３月 ４月 ５月 ６月 ７月 ８月 ９月 １０月 １１月 １２月 １９９９年 １月 ２月 ３月 ４月 ５月 ６月 ７月 ８月 ９月 １０月 １１月 １２月 ２０００年 １月 ２月 ３月 ４月 ５月 ６月 ７月 ８月 ９月 １０月 １１月 １２月 ２００１年 １月 ２月 ３月 ４月 ５月 ６月 ７月 ８月 ９月 １０月 １１月 １２月 ２００２年 １月 ２月 ３月 ４月 ５月 ６月 ７月 ８月 ９月 １０月 １１月 １２月 ２００３年 １月 ２月 ３月 ４月 ５月 ６月 ７月 ８月 ９月 １０月 １１月 １２月 ２００４年 １月 ２月 ３月 ４月 ５月 ６月 ７月 ８月 ９月 １０月 １１月 １２月 ２００５年 １月 ２月 ３月 ４月 ５月 ６月 ７月 ８月 ９月 １０月 １１月
チェッカーの解法 - 186 @ hatenablog
昨日日経新聞に出てた. J. Schaeffer, N. Burch, Y. Björnsson, A. Kishimoto, M. Müller, R. Lake, P. Lu, S. Sutphen. "Checkers Is Solved " -- Science 最善手を打ち続けると両者引き分け. 1989年から回し続けてたらしい. 概要を読むと引き分けと書いてあるが, これAIの論文じゃないか? 本当に引き分けなのだろうか. Science読むか (面倒臭い). Chinook - World Man-Machine Checkers Championに実装されている. Publicationsの項から2005年のを流し読みした. このときはある開始状態からの探索を全て行ったらしい. 2007年に全ての定石を調べた終わったということか. 一般化チェッカーと一般化オセロの複雑さにつ
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
乱数生成器 - lethevert is a programmer
昨日の調査で分かってきたこと。 システムが提供する（可能性のある）乱数生成器には次の４種類がある。 情報理論的な'真'の乱数生成器 各ビットが１ビットのエントロピーを持つ乱数を生成する。OSなどがハードウエアを通して外部のエントロピー源から情報を得て生成する。 暗号理論的な擬似乱数生成器 (CSPRNG) 暗号理論的に予測不可能な乱数を生成する。乱数生成のアルゴリズムは既知であっても、乱数種が暗号理論的に推測不可能なため、生成される乱数が予測不可能。たとえば、Blum-Blum-Shab法は、RSAなどと同じく素因数分解をベースにしている。 統計学的な擬似乱数生成器 統計学的に健全な乱数を生成する。しかし、セキュリティ用途には不適。たとえば、Mersenne Twisterの標準的な実装であるMT19937の場合は、624個の出力を観察すれば、それ以降の出力を予測可能になる。 不完全な擬似
The Sorting Algorithm Demo
Sorting Algorithms The animations on this page illustrate a number of different sequential and parallel sorting algorithms. The relative execution times of the animations give a very rough idea of the relative speeds of the algorithms. Each algorithm is finished when its colored lines disappear. Speed and Efficiency Analysis. Bubble Sort is a sequential algorithm, with an average case time of O(n2
suffix array
更新履歴 2004/01/07 O(N) 構築アルゴリズム三種追加（Ko &Alulu, Kim & al., Karkkainen & Sanders) Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、 (1)大規模なデータに対して、高速に検索、情報抽出を行うことができる (2)BWTとしてデータ圧縮に用いることができる。 ことが挙げられます。(1)に関しては自然言語処理において、膨大な量のコーパスから情報（例えば、単語の出現回数など）を調べるときににSuffix Arrayを用いると非常に高速に求めることができます。 膨大な量のコーパスに基づいた自然言語処理が盛んになってきている今、Suffix Arrayが注目を集めています。 また、ゲノム情報を調べるバイオインフォマティクスにおいても、ここの配列と似ている部分（例えばCCAG）を調べるといった場合
「ナンプレ」パズルの良問を自動・大量生成する新システム
「SUDOKU」（数独）の名称で人気のパズル「ナンバープレース」（ナンプレ）。同パズルの高品質な問題を自動的に大量生成できるシステムを、タイムインターメディアが開発した。一般的なPCで短時間に問題を作成できる上、パズル作家の考え方を取り入れることで「良問」を生成できるようになっているという。 ナンプレ自体は19世紀末にフランスで登場したものがルーツ。日本の出版社「ニコリ」が「数独」と名付けて1984年に掲載し、1997年に日本で数独の本を目にしたニュージーランド人が2004年11月から英Timesに連載を始め、翌年、ブームに火が付いた。 人気が広がるにつれて問題の需要も増えているが、これに対し「良い問題」の供給が足りていないのが現状という。新システムの開発に当たった同社常務・知識工学センターの藤原博文さんによると、主流はコンピュータによる自動生成だが、良問と悪問の区別がつかない「にわかパズ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp: Algorithms: A Functional Programming Approach (International Computer Science Series): Rabhi, Fethi A., Lapalme, Guy: 本
RenderNote - RenderNote