トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター
トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（1/4 ページ） プログラミングにおける重要な概念である「探索」を最速でマスターするために、今回は少し応用となる探索手法などを紹介しながら、その実践力を育成します。問題をグラフとして表現し、効率よく探索する方法をぜひ日常に生かしてみましょう。 まだまだ活用可能な探索 前回の「知れば天国、知らねば地獄――『探索』虎の巻」で、「探索」という概念の基礎について紹介しました。すでに探索についてよく理解している方には物足りなかったかと思いますが、「問題をグラフとしてうまく表現し、そのグラフを効率よく探索する」というアルゴリズマー的な思考法がまだ身についていなかった方には、得るものもあったのではないでしょうか。 前回は、「幅優先探索」と「深さ優先探索」という、比較的単純なものを紹介しましたが
フォント同士を交配させて新しいフォントを作る「genoTyp」が面白い - てっく煮ブログ
「この発想はなかった！」と驚いた。genoTyp はフォント同士を交配させて新しいフォントを生み出す実験サイトだ。早速、試しにやってみた。1. 第一世代の親を決めるgenoTyp を開いて左上の [Breed] タブをクリックすると「交配ページ」が表示される。[add original font] ボタンをクリックして、祖先となるフォントを２つ追加してみた。交配させるために２つのフォントをドラッグしてくっつけた。くっついた状態になれば交配の準備は完了だ。2. 交配させてみる中央の [cross] ボタンを押すと第一世代が誕生する。４人の子供が誕生した。父親似だったり、母親似だったり、子供によって雰囲気が異なっている。3. 第一世代でも交配別の [original font] を追加させて、第一世代の中から気に入ったものと交配させてみた。３人の子供が第二世代に誕生した。4. さらに交配！今度
統計的に正しいランキングを行う方法 - Hello, world! - s21g
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ポジティブ／ネガティブ投票による正しいランキング方法が以下の記事で紹介されています。 How Not To Sort By Average Rating この計算方法では、投票数が少ない場合には分散が大きく不正確な評価で、 投票数が多くなるにつれて分散が小さく正確な評価が得られているという事を考慮しています。以下数式 これはScoreの信頼区間を表しています。 この信頼区間の下界をランキングのスコアにすれば良い事になります。 ここで、は、 です。全体に占めるポジティブ投票数の割合ですね。 は標準正規分布上の 信頼区間の有意確率です。 さて、五段階評価によるRatingに同様のテクニックを適用する場合はどうしたらいいでしょうか
シムシティーの仕組み
シムシティーを作り始めていちばん最初に考えたのは、街を一種の生き物のように表現できないかってことだった。 僕が街についてどう考えているかはすでに説明したけど、大事なのは街を構成する建物とか道路じゃなくって、そこでどんな活動が行なわれているかってことだと思うんだ。道路を車が走り、電車が動き、人々が動き回り、常に要素が変化し続ける“動きのある”システム。街を表現する方法っていうと誰でも地図を思い浮かべると思うけど、僕は動きがない地図じゃなくって、たとえば飛行機から眺めた街、動きのある世界をディスプレイに表現しようって考えた。それこそが僕の考える街の姿だからね。 それともう一つ考えたことは、プレイヤーに伝える情報をできるだけわかりやすく、それも“面白い”って思えるような形で表現しようってことだった。シミュレーション・ソフトっていうとたいてい数値や図表がたくさん出てくるけれど、数字が並んでいるのを
【インフォシーク】Infoseek ： 楽天が運営するポータルサイト
日頃より楽天のサービスをご利用いただきましてありがとうございます。 サービスをご利用いただいておりますところ大変申し訳ございませんが、現在、緊急メンテナンスを行わせていただいております。 お客様には、緊急のメンテナンスにより、ご迷惑をおかけしており、誠に申し訳ございません。 メンテナンスが終了次第、サービスを復旧いたしますので、 今しばらくお待ちいただけますよう、お願い申し上げます。
ラムダ計算とチューリングマシンの違い 2009-04-13 - きしだのはてな
ぼくもYコンビネータがわかるようになるまではそうだったのだけど、Yコンビネータを使うとどのような処理ができるのかがよくわからなくて悩んでいる人が多いように思う。他の人のブログを見ても、名前をつけずに再帰ができるのがすばらしいとか書いてあったりするのだけど、それによってどういう処理ができるのかわからずにいた。 結論をいえばYコンビネータには、なにかの処理を便利にする能力はない。関数であらゆる計算ができるということが示せれば、あとは用なしだ。理論の礎としてうまってしまえばいい。 結局、Yコンビネータによってどのような処理ができるかというのは、ラムダ計算の要素のメリットをチューリングマシンの中に見出そうとしてるといえる。 ラムダ計算とチューリングマシンは、どちらも計算モデルという点では一致しているけど、全く違う。 無限であるか有限かの違いといってもいい。 チューリングマシンでは、データの量と処理
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
綱引きに蛇口当てゲーム？！ 楽しく学ぶベイズフィルターの仕組み
付き合いたくないスパムと付き合うために 受信者の意向を無視して、一方的に送りつけられる迷惑メール（スパム）は、いまやメールボックスを雑音でいっぱいにしてしまい、大事なメールを見過ごしかねないほどの量に膨れ上がり、大きな問題となっています。 残念ながら、このようなスパムを発生源から断つような根本的な対策はいまだになく、私たちは、せめてメールサーバで受け取った大量のメール群からスパムと大事なメールを仕分けしてくれる仕組みに頼らざるを得ません。 スパムを判定する方法は、次の2つに大別することができます。 本稿では前者の方法に着目します。メールを受け取った人にとっては、メールの中身を読めば、そのメールがスパムかそうでないかを判定するのは容易なことです。スパムの定義は、メールを読む人によって変わる可能性があります。例えば、まったくゴルフをしない人にゴルフの勧誘メールが来た場合はスパムといえるでしょう
クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた - てっく煮ブログ
集合知プログラミング を読んでいたら、K-means 法（K平均法）の説明が出てきました。K-means 法はクラスタリングを行うための定番のアルゴリズムらしいです。存在は知っていたんだけどいまいちピンときていなかったので、動作を理解するためにサンプルを作ってみました。クリックすると１ステップずつ動かすことができます。クラスタの数や点の数を変更して、RESET を押すと好きなパラメータで試すことができます。こうやって１ステップずつ確認しながら動かしてみると、意外に単純な仕組みなのが実感できました。K-means 法とはK平均法 - Wikipedia に詳しく書いてあるけど、もうすこしザックリと書くとこんなイメージになります。各点にランダムにクラスタを割り当てるクラスタの重心を計算する。点のクラスタを、一番近い重心のクラスタに変更する変化がなければ終了。変化がある限りは 2. に戻る。これ
新はてなブックマークでも使われてる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に負けていた。しかし、学習が早いというのは実アプリケーシ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
