【速報】ランダムネスが捕まった - とりマセ
数学セミナー2011年2月号 特集◎ランダムネスを捕まえる数学セミナー 2011年 02月号 [雑誌]出版社/メーカー: 日本評論社発売日: 2011/01/12メディア: 雑誌購入: 1人 クリック: 1回この商品を含むブログ (2件) を見る 二ヶ月以上遅れて速報とはこれ如何に。 ランダムネスに関するランダムな年表（チョイスはかなり偏ってます）西暦出来事1919フォン・ミーゼスがランダム性を数学的に定式化しようと試みる1920--6Xランダム性の定式化に辿り着くまでの多数の数学者による試行錯誤の時代1933コルモゴロフによる確率論の公理化ランダムネス誕生の時代1960ソロモノフが現在コルモゴロフ複雑性と呼ばれる概念を導入（数年後にコルモゴロフが同じ概念を独立に発見）1966マーティン=レフによる構成的ランダム性の定式化1970ソロヴェイはランダム強制法を導入し， の部分集合が全てルベー
[NLP][機械学習] 言語モデル覚え書き - tsubosakaの日記
この文章について 最近言語モデル方面にも少し興味があるので自分の知識を整理する意味で書いてみた。NLPは専門ではないので、おかしなことを書いてある可能性がありますがその場合はご指摘ください。 本文章ではn-gramモデル、単語の出現確率がn-1個前の単語のみに依存するモデルを考える。 問題 who is * という文が与えられたときに*にくる文字の確率を求めることを考える。この場合だと*には例えばheが当てはまるかもしれないが, isが入ることはまずなさそうに思える。このことは文法的にも説明ができると思うが、文法のルールを作るのは大変だし、文法的に正しい単語の中でどれが出やすいかということはできない。 一方で機械学習を使った言語モデルの文脈では文法的知識を余り持たず、与えられたコーパスから自動的に出やすい単語/表現を学習する方針をとる。 最尤推定 一番簡単なモデルとしては最尤推定を使うもの
![[NLP][機械学習] 言語モデル覚え書き - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/fd5873fc29a8487ca585cedd187a3197a9282658/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030005%2F1557332435)
階乗を求める - d.y.d.
22:56 10/09/04 階乗を求める 去年聞いた中で、私が一番感動した式の話。 k! = limn→∞ nk / nCk kの階乗は、「nのk乗 ÷ n個のものからk個選ぶ組み合わせの数」という式で n を無限に大きくしていったときの収束先、である。 特に難しい証明が要るとかではなくて、nCk = n(n-1)(n-2)...(n-k+1) / k! であることを使うと、 limn→∞ nk / nCk = limn→∞ nk k! / n(n-1)(n-2)...(n-k+1) で、n が k に比べて十分大きければ n も n-k+1 もほとんど同じ値なので、 分子も分母もだいたい n を k 個かけているわけでして、 その部分が相殺して、k! が残るという寸法。 （厳密な表現ではないので、気になる人は厳密に証明してください。） 実装 と、この式自体はそんなに不思議ではないのです
玉を取れ！ 〜石取りゲーム必勝法〜 - イガブロギュ
新しい記事をアップしました。こちらの方が簡潔です。 http://d.hatena.ne.jp/igaris/20110903/1315040936 タイトルは, 変な意味ではありません. 科挙とかじゃないですよ. 今回は, 石取りゲームとか, うんたらかんたらと言われる, 二人でやるゲームについての考察です. 有名なので, 知ってる方も多いのでは？ その昔, 平成教育委員会でも取り上げられたことがあります. 「ルール」 ・玉が 個あります. ・一度に取れる玉の数は 個以上 個以下です. ・二人が交互に玉を取ります. ・最後の玉を取った方が負けです. ちなみに, このゲームは「二人零和有限確定完全情報ゲーム」と呼ばれるものの一種です. ・二人 → 二人でやるんだよっ. ・零和 → 二人の勝ち負けポイントを足すと常に . 例えば, 勝ちを , 負けを , 引き分けを とすると, 勝負がついた
正規表現とオートマトン：イプシロン指標 - 檜山正幸のキマイラ飼育記 (はてなBlog)
タイトルに「正規表現とオートマトン：」が付いた記事は、いちおう続きものになる予定です。「この機会にマスターしようぜ、正規表現、構文図、オートマトン」から始まる形式言語理論入門シリーズだともいえますが、これから扱う話題はあまり一般的じゃありません。特論ですな。「Catyの正規表現型：なぜ明瞭正規表現なのか」で触れた明瞭正規表現についてハッキリと述べることが目的です。この目的に必要な概念や手法を順に説明していきます。 今日はイプシロン指標の話です。「イプシロン指標」は僕の造語です。とても重要な概念の割には名前がないので命名しました。でも、ある種の対象物／概念にε（イプシロン）という記号を使うことは伝統的なのです。 内容： 言語、オーマトン、正規表現 イプシロンの話 言語演算とε指標 ε指標の計算 ε指標の使いどころ 言語、オーマトン、正規表現 アルファベット、つまり基本記号の集合をAとしましょ
この機会にマスターしようぜ、正規表現、構文図、オートマトン - 檜山正幸のキマイラ飼育記 (はてなBlog)
正規表現と構文図について解説します。オートマトンについても詳しく述べます。オートマトン・スゴロクで遊びましょう！ 世間でよく知られている／使われている概念・方法にはこだわらず、僕（檜山）の感覚で一番わかりやすいと思われる筋書きと用語法／図式法を使って説明します。この記事に目を通して“感じ”が掴めたら、形式言語理論の教科書を読み始めることが出来るでしょう。 [追記]この記事の内容に対する具体例は、「正規表現とオートマトン：なんだ簡単じゃん、JavaScriptによる実装」にあります。[/追記] 内容： 正規表現 正規表現の例 構文図 基本記号 連接 選択 省略可能 繰り返し ストレートワイヤーによるレイアウト調整 有限状態オートマトン 有限状態オートマトンの実行 バックトラックと先読み スゴロクとオートマトン コマをたくさん使うスゴロクと並列処理 非決定性オートマトンと決定性オートマトン 正
Leftist Heap - 言語ゲーム
Chris Okasaki の Purely Functional Data Structures という本を買ってみました。これは、副作用を使わないでいろいろなデータ構造のアルゴリズムを実装するという大変面白い本で、これを読むと、副作用無しで○○が出来るわけがない！という時の○○がだいぶ減ると思います。 サンプルは Standard ML で書かれているのですが、良くわからないのでHaskell で書き直しながら読んでみます(巻末に Haskell での実装例が載ってるけど見ないふり)。 17 ページに Heap というコレクションが紹介されています。これは次の性質をもったコレクションです。 要素は大小関係を持つオブジェクト。 最小の要素だけを取り出す事が出来る。 ようするにあるリストをソートして最小の奴を取り出したいという場合、取り出す物が最小の物だけならばソートするより効率の良い方法
ブログ目次
ごちゃごちゃ書いてきてどれがなにかわからなくなった。これではほんとうに「Write-Only-Memory」になってしまってメモの意味がない。so-net blogの「マイカテゴリー」は階層表示できないし。しょうがないので思い出しながら内容分類を作ることにした。 献立やその場限りの話題を除いて、「マイカテゴリー」の分類ではなくて内容ごとに分類して内容に対するコメントとリンクを置いておく。内容によっては重複して現れる項目もある。同じ分類内部では古いものが先に、新しいのが後に並んでいる。ブログとは逆。でも順番としてはこちらが正しい。 大分類 物理/数学関係 プログラミング パソコン関連 音楽 ギター 読書 その他 中分類 物理/数学関係 光の偏光に関する計算 フラウンホファ回折の計算 電磁場の解析 光学薄膜 FFT (Fast Fourier Transform)のアルゴリズム 複雑系 その他
Rubyのハッシュテーブルの仕組みを徹底的に理解する - ザリガニが見ていた...。
ハッシュとは 一般的に理解すると抽象的で分かり難くなってしまうが、ハッシュとは、あるデータから、一定の計算をして求めた、目的に沿った数値、と思っている。それでは、どのような目的に利用されるのか？自分の知識で考えてみた。 暗号化 webアプリケーション等で、パスワードをDBに保存する時、生のパスワードをハッシュに変換して保存する。 Digest::SHA1.hexdigest等で求めたハッシュから、元のデータを復元するのが非常に困難という特性を利用する。 保存しているパスワードハッシュが、たとえ漏洩したとしても、不正利用を防止できる。 パスワードを照合するときも、ハッシュに変換して、保存しているパスワードハッシュと一致するかどうかで判断する。 同等の確認 長い文字列データを比較する時、全ての文字が等しいかチェックするのは非常に時間がかかる。 しかし、長い文字列データをハッシュに変換しておき、
C++: 編集距離を求めるアルゴリズム
編集距離(edit distance)とは二つの文字列がどの程度異なっているかを示す数値であり、レーベンシュタイン距離(Levenshtein distance)を指すことが多い。文字の挿入、削除、置換それぞれを一つの操作として必要な操作の最小数を求めるものだ。例えば、kittenとsittingの編集距離を求める場合、下記のように3回の操作でkittenをsittingに変更できるので編集距離は3となる。 1. sitten (k を s に置換） 2. sittin (e を i に置換） 3. sitting (g を挿入) そこで今回は編集距離を求める複数のアルゴリズムについてC++で実装してみた。 動的計画法 編集距離を求めるもっとも一般的なアルゴリズムは、動的計画法(dynamic programming)だろう。計算時間はO(mn)であり、手軽だ。C++で書いたコードを下に示
【インフォシーク】Infoseek ： 楽天が運営するポータルサイト
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://nlpwp.org/book/
http://nlpwp.org/book/index.xhtml
Google Code Archive - Long-term storage for Google Code Project Hosting.
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ