一定期間更新がないため広告を表示しています
圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。 http://github.com/naoya/perl-algorithm-wavelettree/tree/master my $wt = Algorithm::WaveletTree->new("abccbbabca"); is $wt->rank(6, 'a'), 2; is $wt->rank(6, 'b'), 3; is $wt->rank(9, 'b'), 4; is $wt->select(0, 'a'), 0; is $wt->select(1, 'a'), 6;
「日本語入力を支える技術(IME本)」で紹介されたことで一躍市民権を得た感のあるLOUDS(Level Order Unary Degree Sequence)。LOUDSとは木の簡潔データ構造で、小さいデータサイズで木が実現できるので日本語入力の辞書引きに使うトライ木をLOUDSで実装すると効率が良い。 さて、そんなLOUDSにはパワーアップ版ともいうべきDFUDS(Depth First Unary Degree Sequence)というデータ構造がある。DFUDSはLOUDSが定数時間で扱える操作(parent(親ノードの位置を得る), i-th child(i番目の子ノードの位置を得る), degree(子ノード数を得る))に加えてsubtree size(現在のノードを根とする部分木のノード数を得る)という操作が定数時間で実現できる。よってDFUDSを使うと、トライでpredic
Javaでベイジアンネットワークを扱うライブラリを探している。 自分のソフトにベイズ統計の処理を組み込む必要があるので。 ベイジアンネット(Bayesian Network)っていうのは,条件付確率の因果関係をグラフィカルな有向非循環グラフ構造で表したもの。有向ってのはリンクが矢印で向きがついてるという意味で,非循環とはグラフ構造にループがないってこと。 ベイジアンネットは,トマス・ベイズさんが発案したベイズ理論をもとにしている。詳しくは以下を参照。 グーグル、インテル、MSが注目するベイズ理論 - CNET 一般向け解説。ベイズさんの顔が拝める。 君はベイジアン・ネットワークを知っているか? - @IT 研究の最前線についての解説アリ。MS Officeのイルカ君の悲劇も紹介。 ベイジアンネットのライブラリだけど,自分は今までMSBNを使ってました。 Microsoft Bayesian
最近では企業における機械学習の認知度も高まっていてエンジニアの求人募集でも「望ましいスキル:機械学習」というのをよく見かける。特にweb系の企業だと当たり前のように機械学習を活用した魅力的なサービスが生み出されているようだ。 そんなわけで先日書いた機械学習の入門記事もそれなりに好評で末尾の教科書リストも結構参考にしていただいた様子。ということで、これから機械学習をはじめる人のためにオススメの教科書を10冊ほどピックアップしてみた。 幸いにして機械学習の分野には良書が多い。5年前はナイーブベイズすら知らなかった私も、これらの教科書のおかげでなんとか機械学習を使えるようになりました!(個人の体験談です。効果には個人差があります) 参考: 機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBlog-Zwei 最初に既存の機械学習の教科書まとめを挙げておくの
自然言語処理や機械学習でいくつか新しい教科書的なものが登場してきたので、まとめてみようと思う。 教科書について。Introduction to Information Retrieval Introduction to Information Retrieval 作者: Christopher D. Manning,Prabhakar Raghavan,Hinrich Schuetze出版社/メーカー: Cambridge University Press発売日: 2008/07/07メディア: ハードカバー購入: 7人 クリック: 115回この商品を含むブログ (37件) を見るの翻訳が進んでいる(あとこれを研究室の輪読に使っていたりする)という話を聞いたりするのだが、やっぱり知識として知っておくべき本というのと、そこから超えていく本というのは違うものであって、どれだけ研究が進んでも、分
Google日本語入力がOSS化されたということで、気になっていたところをいくつか確認してみた。 変換アルゴリズムはどんな感じか? twitterの工藤さんの発言にも「わりと古典的な最小コスト法」とあるけれど、まさにそんな感じ。人名の処理とかでちょっと特別なコードが入ったりもしているが、ほぼ基本的な統計的かな漢字変換のモデル。係り受けの情報とかは使っていない。Viterbiでベストパスを求めて、品詞ベースで文節にまとめあげている。コストモデルは接続コストが品詞対品詞で、単語コストの方は単語毎に設定されているっぽい。 src/converter/immutable_converter.ccのImmutableConverterImpl::ViterbiがViterbiアルゴリズムの部分で、その後にMakeSegmentsで文節にまとめている。読むならImmutableConverterImp
ダブル配列のライブラリを公開しているページです. An Implementation of Double-Array Trie URL: http://linux.thai.net/~thep/datrie/datrie.html Darts: Double-ARray Trie System URL: http://chasen.org/~taku/software/darts/ Dame URL: http://www.void.in/wiki/Dame Tiny Double-Array Library URL: http://nanika.osonae.com/TinyDA/index.html Dynamic Double-Array Library URL: http://nanika.osonae.com/DynDA/index.html
人工知能基本問題研究会 (SIG-FPAI)でタイトルの題目で一時間ほど話してきました。 発表資料 [pptx] [pdf] 話した内容は - 自然言語処理における特徴ベクトルの作り方と、性質 - オンライン学習, Perceptron, Passive Agressive (PA), Confidence Weighted Learning (CW) 確率的勾配降下法 (SGD) - L1正則化, FOLOS - 索引を用いた効率化, 全ての部分文字列を利用した文書分類 で、スライドで70枚ぐらい。今までの発表とかぶっていないのはPA CW SGD FOLOSあたりでしょうか オンライン学習、L1正則化の話がメインになっていて、その両方の最終形の 確率的勾配降下法 + FOLOSの組み合わせは任意の損失関数に対してL1/L2正則化をかけながらオンライン学習をとても簡単にできるという一昔前
講義資料読み+宿題を終らせた. 今後もっと本やら論文やらを読みまくって修士での研究テーマを早めに明確にしていきたい. 前回に続いてまた「リンク解析とその周辺の話題」を読んだ記録(三日, 四日目)ですが, 内容についてはスライドを読めばわかるので, その補足的なことのみを記述します. しかし調子に乗って定理の証明をしようとしてうまくいかなくて悶絶. von Neumann カーネルと正則化ラプラシアンの比較ができたのでよかったですが, それくらいしか内容ありません:(なおプログラムは gists の埋め込みなので LDR や fastladder からは読めません.*1 証明やプログラムに誤りなどがあれば指摘していただけると助かります. おしながきスライドの訂正: 三日目 54ページの指数拡散カーネルを展開したところ von Neumann kernel による重要度と正則化ラプラシアンによ
海外のブログでお勧めはどういうのありますかとよく聞かれるのでかいてみます。 といってもそんなないけど。 Terence Tao 非常に幅広い分野の第一線で活躍している数学者のテレンスタオ[jawiki]のブログ.ブログで毎回新しい定理を証明しちゃったり、突然、相対性理論の分かりやすい証明をしたりとすごい.コメントでの議論も丁寧. ブログで書いたのをまとめた本が出るそうですが、目次を読むとブログ本の範疇をこえてる・・ natural language processing blog 自然言語処理ではたぶん一番有名なブログ. による.いろいろな手法の解説から現在ある問題(自然言語処理以外にもアカデミック的な問題とかも含め).守備範囲が大体私と似ていて読んでいて楽しい.ちなみにHal Daumeはハスケラーで、そこそこ有名なhaskel tutorialかいてたりする Google Resear
朱鷺の杜Wiki(ときのもり うぃき)† 朱鷺の杜Wikiは,機械学習に関連した,データマイニング,情報理論,計算論的学習理論,統計,統計物理についての情報交換の場です.これら機械学習関係の話題,リンク,関連事項,書籍・論文紹介などの情報を扱います. 更新されたページを確認するにはRSSリーダを使って右下のRSSリンクをチェックするか,最終更新のページを参照してください. ページの中でどこが更新されたかを見るには,上の「差分」をクリックして下さい. 数式の表示に MathJax を利用しています.数式の上でコンテキストメニューを使うと各種の設定が可能です.特に設定をしなくても数式は閲覧できますが,フォントをインストールすれば数式の表示がきれいで高速になります.詳しくは 数式の表示 のページを参照して下さい. ごく簡単なWikiの使い方がこのページの最後にあります.トップページやメニューなど
Double Arrayのコードなんて1年以上いじってないくせになにを言ってるんだこの口はと言う感じですが、Double Arrayを作るのであれば、動的更新に対応させるべきであると、そう思うわけです。 Double Arrayのメリットは Trieである 速い (Ternary Search Treeとかと比べると)サイズも小さい という感じだった訳ですが、速度はともかく、サイズではTxが使っているようなLOUDSやLOUDS++などの圧縮しちゃう方式に勝てないので、静的な辞書としては、速度が超重要なところ以外ではLOUDSやLOUDS++を使った辞書を使うのがいいのかなと思う訳です。辞書引き以外の部分がボトルネックであることも多いだろうしね。 と言うわけで、簡潔データ構造に比較してDouble Arrayでなにか便利な事ができないかなというと、圧縮をかける方式ではやはり、動的な更新が難
This is the companion website for the following book. Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press. 2008. You can order this book at CUP, at your local bookstore or on the internet. The best search term to use is the ISBN: 0521865719. The book aims to provide a modern approach to information retrieval from a co
人気記事 1 「フォートナイト」のEpic Games、Android版ストアを開設--EUではiOS版も 2024年08月19日 2 FCNTの新スマホ「arrows We2/We2 Plus」--価格や販路の違い等を写真で確認 2024年08月16日 3 携帯4社決算を読み解く--減益のドコモ、契約者急増の楽天モバイルが抱える課題 2024年08月15日 4 グーグルに批判、「Pixel優先」をインフルエンサー向けプログラムの条件に 2024年08月19日 5 Instagramで「既読」を付けずにDMを閲覧する方法 2024年03月11日 6 バルミューダ決算、新型「Mac mini」など--週間人気記事をナナメ読み(8月9日~8月15日) 2024年08月16日 7 グーグル「Pixel 9 Pro Fold」、初代モデルからの進化ぶりをチェック 2024年08月16日 8 脳イン
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く