「お兄ちゃんのえっち…」 の 「の」 の文法的解釈 - 今日の一撃 - tak-shonai's "Today's Crack"
xl1blue さんが Twitter で "「お兄ちゃんのえっち… 」の「の」は文法的にはどんな説明が与えられますか" と tweet しておられる （参照）。ふぅむ、言われてみればちょっと難しい。「えっち」がお兄ちゃんの所有物というわけでもないから、所有を表す助詞というわけではない。 同じことは、「お母さんのばかぁ！」「夕日の馬鹿野郎ぉ～！ 」などにも言える。こんなのは、その辺の自動翻訳サービスにかけたら、"mother's fool!" "Foolish guy of sunset!" なんて結果になりかねない。日本語ってなかなか難しい。 とりあえず、辞書を引いてみる。Goo辞書というのは、背後で三省堂の『大辞林』が動いているから、無料サービスだからといって馬鹿にしたもんじゃない。この辞書で調べると（いや、別に辞書で調べなくても）、格助詞の「の」であることは明白だ。 そして格助詞の
KyTea (京都テキスト解析ツールキット)
English 京都テキスト解析ツールキット(KyTea、「キューティー」)は、日本語など、単語(または形態素)分割を必要とする言語のための一般的なテキスト解析器です。 特徴 ダウンロード・インストール プログラム仕様 解析：手法の詳細, 入出力の形式, API 学習：モデル学習, 入手可能なモデル KyTeaを使った分野適応 開発情報 特徴 KyTeaには以下の機能が揃っています： 単語分割：分かち書きされていないテキストを適当な単語または形態素に分割する。 読み推定・品詞推定：かな漢字変換や音声認識、音声生成のために単語の発音を推定することができ、品詞を推定することもできます。 線形SVMやロジスティック回帰などを用いてそれぞれの分割点や読みを個別に推定するため、部分的にアノテーションされたデータを利用してモデルを学習することも可能です。 分類器の学習にはLIBLINEARを使用してい
関数最適化サンプルプログラム
関数最適化サンプルプログラム 2002年10月3日更新 ここでは，GAによるF1関数最適化プログラムを公開します． F1関数最適化プログラムドキュメント C言語ソースファイル C言語ヘッダーファイル データファイル
NLP2010 言語処理学会チュートリアル - DO++
今日から開催されている言語処理学会のチュートリアルで ”超高速テキスト処理のためのアルゴリズムとデータ構造” というタイトルで発表させていただきました。 チュートリアル資料はこちら(pdf)です。（出典などは適宜追加します） 今までいろいろなところで話してきた、オンライン学習、文字列、疎ベクトルデータ構造を最新の話を追加して、さらに乱択化（Hash Kernel, 乱択化SVD)を解説しています。 発表自体は途中でブルースクリーンが出るということもありましたが、なんとか終えられてよかったです。 これに付随していろいろツールを公開する予定だったがまにあわなかった。そのうち公開します
EM アルゴリズム実装(勉強用) - 木曜不足
最近忙しくて*1、PRML の予習が滞り中。 しかし、次の PRML 読書会に徒手空拳で行ったら、気持ちよく昇天してしまいそうなので、なんとか頑張って読んでみる。 EM アルゴリズムは何となくわかるが、変分ベイズがわからん…… というわけで、Old Faithful の混合正規分布での推論を K-means と EM と変分ベイズについて、Ｒで実装してみる。 K-means Old Faithful + K-means については、すでに 前回の記事でお試し済み。 その記事では、イテレーションを１行で書いてネタっぽくしてしまってたので、わかりやすく整理したのが以下のコード。 距離を取るところは少し変えて短くしてある。 # Old Faithful dataset を取得して正規化 data("faithful"); xx <- scale(faithful, apply(faithful,
CHM lib
CHM lib0.40 CHMLIB is a library for dealing with Microsoft ITSS/CHM format files. Right now, it is a very simple library, but sufficient for dealing with all of the .chm files I've come across. Due to the fairly well-designed indexing built into this particular file format, even a small library is able to gain reasonably good performance indexing into ITSS archives. 2009-05-23, 8:25 AM PST: Releas
Data Compression Explained - Matt Mahoney
Data Compression Explained Matt Mahoney Copyright (C) 2010-2012, Dell, Inc. You are permitted to copy and distribute material from this book provided (1) any material you distribute includes this license, (2) the material is not modified, and (3) you do not charge a fee or require any other considerations for copies or for any works that incorporate material from this book. These restrictions do
SimString - A fast and simple algorithm for approximate string matching/retrieval
A fast and simple algorithm for approximate string matching/retrieval SimString is a simple library for fast approximate string retrieval. Approximate string retrieval finds strings in a database whose similarity with a query string is no smaller than a threshold. Finding not only identical but similar strings, approximate string retrieval has various applications including spelling correction, fl
上手に描くコツはどこに？プロのマンガ家に学ぶ「絵の描き方」 - はてなブックマークニュース
はてなブックマークでも度々注目を集めるのが「絵の描き方」についてのエントリー。絵が上手な人は、同じものを描く場合でも一体どんなところに注意して描いているのでしょうか？今回は、プロのマンガ家やイラストレーターが教える「絵の描き方」についてのエントリーを集めました。 ■ササッと「似顔絵」を描くコツは？ 本格的に絵を描くまではいかなくても、自分や友達、有名人などの似顔絵を短時間でササっと描けると楽しいですよね。まずはそんな時に参考にしたいこちらのエントリーです。 ▽@nifty：デイリーポータルZ：絵が苦手でもイラストを描く方法 こちらは絵が苦手だという筆者が、べつやくれいさんら3人のイラストレーターに似顔絵を描くコツを教わるという企画。どうやら、イラストレーターの人たちの絵には次のような特徴があるようです。 すっきりと見やすく描いている。 特徴を見ようとしている。 大きな特徴さえ押さえれば他は
http://alpha.mixi.co.jp/dist/maptest.cc
/************************************************************************************************* * Writing test of map utilities *************************************************************************************************/ #include #include #include #include #include #include #include #include #include #define RECBUFSIZ 32 // buffer for records using namespace std; struct stringhas
CMPH - C Minimal Perfect Hashing Library
Motivation A perfect hash function maps a static set of n keys into a set of m integer numbers without collisions, where m is greater than or equal to n. If m is equal to n, the function is called minimal. Minimal perfect hash functions are widely used for memory efficient storage and fast retrieval of items from static sets, such as words in natural languages, reserved words in programming langua
DASTrie: Static Double Array Trie
Static Double Array Trie (DASTrie) Introduction Trie is a data structure of ordered tree that implements an associative array. Looking up a record key (usually a string) is very efficient, which takes O(1) with respect to the number of stored records n. Trie is also known for efficient prefix matching, where the retrieved key strings are the prefixes of a given query string. Double-array trie, whi
An Implementation of Double-Array Trie
Contents What is Trie? What Does It Take to Implement a Trie? Tripple-Array Trie Double-Array Trie Suffix Compression Key Insertion Key Deletion Double-Array Pool Allocation An Implementation Download Other Implementations References What is Trie? Trie is a kind of digital search tree. (See [Knuth1972] for the detail of digital search tree.) [Fredkin1960] introduced the trie terminology, which is
Sparse matrix - Wikipedia
An important special type of sparse matrices is band matrix, defined as follows. The lower bandwidth of a matrix A is the smallest number p such that the entry ai,j vanishes whenever i > j + p. Similarly, the upper bandwidth is the smallest number p such that ai,j = 0 whenever i < j − p (Golub & Van Loan 1996, §1.2.1). For example, a tridiagonal matrix has lower bandwidth 1 and upper bandwidth 1.
waf チュートリアル - 純粋関数型雑記帳
waf - The flexible build system http://code.google.com/p/waf/ wafというものを最近知り一目惚れしてしまったので、紹介記事を書きます。ユーザーが増えると嬉しいな。 wafとは何か？特徴・利点・使うべき理由 wafはPythonベースのビルドシステムです。同様のことを行うツールとして、Autotools、Scons、CMake、Antなどがあります。Sconsからの派生で、比較的新しいソフトウェアです。 分かりやすい Pythonで書かれており、スクリプトもPythonで記述します。シェルスクリプトと謎のマクロが入り混じるAutotoolsや、独自言語のCMakeなどに比べて扱い易いです。Pythonを知っていれば非常にすんなりと使いこなすことが出来ます。Pythonを知らなくても、他の独自言語を覚えるよりは実りがあるかと思います
Compressed Suffix Arrayの解説(4) -unary記法- - EchizenBlog-Zwei
< Compressed Suffix Arrayの解説(3) -圧縮の方針- < | > Compressed Suffix Arrayの解説(5) -Succinct Bit Vector- > ================================================ まずは下準備。数値列をunary記法でbit列に変換する方法を説明。 unary(ユナリィ)記法というのは数値の数だけの0を並べて、最後に1を置くというもの。具体例を挙げると 数値 unary 0 1 1 01 2 001 3 0001 4 00001 5 000001となる。 unary記法では1が数値間の境界を表すために各数値毎のbitサイズを固定長にする必要がない。例えば数値列 1 1 2 2 1 2は各数値をそれぞれ1byteで表したとすると全体で48bit(6byte)必要になる。一方で
Text Indexing Resources - Donaldson Group
A considerable number of text indexing solutions exist. This document discusses some of the more widely-known open source solutions. ht://Dig - a search engine solution for individual Web sites Hyper Estraier - a reasonably well-utilised solution by other software systems and applications Lucene - arguably the most popular text indexing solution in current use, original implementation in Java with
第4回 全文検索エンジン「Lucene/Solr」の用途と良さ
情報インフラの発展に伴い，私たちが接する情報の絶対量は増加の一途をたどっています。そのため，目的とする情報をすばやくピンポイントで入手するのが困難な状況も増えています。 一方で情報提供側にとっても，情報を確実に利用者に届けることがビジネスの成功に重要な要素となってきており，これを実現するための努力が日々続けられています。 このような状況で，高速で柔軟性が高い検索処理のニーズが高まってきており，全文検索エンジンが注目を集めています。ここでは，オープンソースの全文検索エンジンである「Lucene/Solr」を紹介します。 Lucene/Solrとは Lucene/Solrは，Apache Software Foundation（ASF）のLuceneプロジェクトで開発されているソフトです。LuceneはPure Javaで実装された全文検索エンジンで，単独では実行不可能なライブラリの形式で提供
Naive Bayesの罠 - EchizenBlog-Zwei
< Naive Bayesの実装 < | > ---- > ================================================ Naive Bayes(NB,ナイーブベイズ)には気になる事があるよ、という話。前回、文書{バナナ,カレー}が「甘い」クラスと「辛い」クラスそれぞれに属する確率(対数尤度)をナイーブベイズ分類器で求めた。 その結果、文書{バナナ,カレー}は「辛い」クラスに属することがわかった。しかしバナナもカレーも「甘い」クラスに入っているのに「辛い」クラスのほうが対数尤度が大きいというのはちょっと直感に反するかもしれない。以下ではこの点について考察する。 前回求めた対数尤度の計算式は以下の通り。 lnP(甘い|{バナナ,カレー}) = lnP(カレー|甘い) + lnP(バナナ|甘い) + lnP(甘い) = 0.69 + 0.69 - (2 -
Compressed Suffix Arrayの解説(2) -SAの計算量- - EchizenBlog-Zwei
< Compressed Suffix Arrayの解説(1) -Suffix Array- < | > Compressed Suffix Arrayの解説(3) -圧縮の方針- > ================================================ Suffix Arrayの計算量について解説。 計算量には空間計算量、時間計算量の2種類がある。 空間計算量とは、あるデータ構造を保持するのに必要となるメモリ、ディスクの大きさを表す。 時間計算量とは、あるアルゴリズムがデータを処理するのにかかる時間を表す。 計算量はデータ数などの関数として表現され、たとえばデータ数がNのとき O(N) O(NlogN) O(N^2)などと表される。動かすマシンの性能ではなく、単純にデータ数が非常に大ききなった場合のデータ構造、アルゴリズムの性能を検討する際に計算量の考え方が用
senna の NFKC と gcc-4.2.1 - odz buffer
senna を NFKC 有効*1で gcc-4.2.1 でコンパイルしようとすると swap あわせて 256 MBytes の仮想マシンでもメモリが足りなくて落ちるんだけど。 でまぁ、lib/nfkc.c をみるとものすごい勢いで case ラベルが並んでいる訳だ。まぁ、これだと最適化がすごいことになりそうだよな。なんか、ICU を使って生成しているらしんだけど、そのまま ICU のソースを流用ではまずいのかな。 *1:デフォルトで有効
Compressed Suffix Arrayの解説(1) -Suffix Array- - EchizenBlog-Zwei
< ---- < | > Compressed Suffix Arrayの解説(2) -SAの計算量- > ================================================ 最近(でもないか)話題のCompressed Suffix Array(CSA)について解説してみる。 CSAとはSuffix Array(SA)のインデックスを圧縮して小さくしたもの。大規模テキストデータに対する検索インデックスを作る場合など少しでもインデックスを小さくしたい場合に使われる。 CSAを知るにはSAから！ということで今回はSAの解説を。 Suffix Array(SA)とはデータ構造の一種で事前に(サイズがNの)テキストに対してインデックスを作っておくことでキーとなる文字列を入力として与えるとテキストに含まれるキーの位置をO(logN)で探索できる、というもの。 たとえば
livedoor Readerサービス終了のお知らせ
livedoor Readerサービス終了のお知らせ 2014年12月をもちまして、LINE株式会社が提供するlivedoor Readerの運営を終了しております。 長きに渡りご愛顧をいただきまして、誠にありがとうございました。 livedoorホームへ戻る
Naive Bayesの実装 - EchizenBlog-Zwei
< ---- < | > Naive Bayesの罠 > ================================================ Naive Bayes(NB,ナイーブベイズ)の実装についてメモ。 NBというのはベイズ則に基づく単純な分類器で lnP(Ci|D) = Σj{lnP(wj|Ci)} + lnP(Ci)で文書DがクラスCiに属する確率が得られるよ、というもの。(以下、Σiで添字iのすべての場合についての足し合わせを表す) これを実装する場合、まず手元にデータ集合を用意する。データ集合はクラスラベル(Ci)の付けられた単語(wj)、つまり(Ci,wj)のペアの集まり。例えば (甘い,りんご) (甘い,りんご) (甘い,りんご) (甘い,ハチミツ) (甘い,ハチミツ) (甘い,バナナ) (甘い,砂糖) (甘い,カレー) (辛い,カレー) (辛い,カレー)
ゼミで半教師あり学習のことを発表したのでスライドを公開します - yasuhisa's blog
理解が不完全だし、ゼミで再生核ヒルベクト空間のことやってなかったから途中で混ざってたりとかで大分あれな資料になってますが、公開してみるテスト。 半教師あり学習 from syou6162 次回は何を発表するか。。。
[機械学習] bayon+LSHIKITを使って画像クラスタリング - tsubosakaの日記
bayonを使って画像からbag-of-keypointsを求める - のんびり読書日記の記事を読んで、クラスタリングを行う際の入力データを作るために文献[1]にある方法が利用できると思って実験してみた。 局所特徴量を持ったデータの取扱い 画像データの分類などを行う際にSIFTのような画像中の特徴点(keypoint)を抽出するということがよく行われる。 例えばSIFTを用いる場合は各keypointは128次元のベクトルとなり、画像ごとにいくつかのkeypointが抽出される。ここで抽出されるkeypointの数は画像ごとに異なる。このため、画像間の類似性を比較するのは困難である。 これに対するアプローチとしては一つは画像中の特徴点同士の全対比較を行う、もしくはマッチングをとるという方法が挙げられるがこれは計算量が非常に大きい。 別の方法としてヒストグラムを利用するという方法がある。これ
![[機械学習] bayon+LSHIKITを使って画像クラスタリング - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/4726d0fe10c94d023f9d3751369bf10a254dda5e/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Ft%2Ftsubosaka%2F20100130%2F20100130195850.png)
Bayesian Setsによる関連文書検索システムStupa - mixi engineer blog
都会よりも田舎が好きなfujisawaです。Bayesian Setsというアルゴリズムを使って、関連する文書を高速・高精度に検索できるシステムを作成しましたので、そのご紹介をさせていただきます。 Bayesian Setsとは Bayesian Setsはいくつかアイテムを入力すると、それを補完するようなアイテムを返してくれるアルゴリズムです。原著論文の先頭に"Inspired by Google Sets"と書かれているように、Google Setsを参考にして作成されています。実際にどのような出力が得られるか、Google Setsに以下の表のクエリを検索して試してみますと、 クエリ 出力 apple, banana chocolate, strawberry, vanilla, cherry, ... apple, macintosh software, windows, mac,
bayonやCLUTOが爆速な理由 - download_takeshi’s diary
クラスタリングツールbayonを使っていて、常々「どうしてこんなに高速に処理できんのかなぁ」と疑問に感じていました。repeated bisectionという手法自体がk-means法などと比べると効率がいいのですが、それにしても、それだけでは説明がつかないほど爆速なわけです。 うまく例えられませんが、自前でk-meansのスクリプトを書いて比べてみると、自転車と新幹線くらいちがうという印象です。はじめてCLUTOを触った時、数万件程規模のクラスタリング処理が本当に「あっ」という間に終わってしまい、びっくりした記憶があります。 きっと実装面でなにか特殊なことがあるんだろうなと思い、mixiエンジニアブログでbayonの記事を改めて読み漁っていたら、以下の部分が目に止まりました。 このクラスタの評価は、クラスタの各要素とクラスタの中心とのcosine類似度の和としています。この和が大きいほど
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
livedoor ReaderのクローラとStreaming APIなどの話
Darts clone 0.32g に関する資料 - やた＠はてな日記
Google Code Archive - Long-term storage for Google Code Project Hosting.
dd, awk, less を使って PDF からテキスト抽出
http://japan.internet.com/column/developer/20100219/26.html?rss