「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
[プログラミング] ビット並列アルゴリズムを使った編集距離 - tsubosakaの日記
ふと、ビット並列アルゴリズムを使った編集距離を計算するアルゴリズムを書きたくなったので書いてみた。 まず、通常の編集距離であるLevenshtein Distanceを求めるアルゴリズムは以下のように書ける int levenshteinDistance(String A, String B) { int m = A.length(); int n = B.length(); int dp[] = new int[n + 1]; int next[] = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i; for (int i = 1; i <= m; i++) { next[0] = i; for (int j = 1; j <= n; j++) { if (A.charAt(i - 1) == B.charAt(j - 1))
![[プログラミング] ビット並列アルゴリズムを使った編集距離 - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/abb310b76b915a8d5d10199b4b0f5418555a807c/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Ft%2Ftsubosaka%2F20091103%2F20091103000001.jpg)
ボロノイ図いろいろ - kaisehのブログ
Webエンジニアバトルロワイヤルでは、平面分割手法としてボロノイ図と「疑似築道法」というものをデモしたんですが、そのとき説明に使った4種類の2次元ボロノイ図を以下に載せます。 通常のボロノイ図 「どの母点が最も近くにあるか」にもとづいて平面を分割します。ボロノイ辺は母点の垂直二等分線になります。 マンハッタン距離にもとづくボロノイ図 ユークリッド距離の代わりにマンハッタン距離を使うと、見た目ががらっと変わって、路線図や天気予報のときの都道府県図っぽくなります。 加法的重み付きボロノイ図 (Additively Weighted Voronoi Diagram) 母点にそれぞれ重みを設定して、ユークリッド距離に重みを加算したものを距離関数としてボロノイ図を作ると、ボロノイ領域を膨らませたり縮ませたりできます。ボロノイ辺は双曲線になります。 加法的重み付きべき乗ボロノイ図 (Additivel
ビュッフォンの針の実験による円周率π
幅が一定値ａ(ａ=30)の平行線が何本かひいてあります。ここの長さl(lengthの頭文字)の針を落とします(ｌ≦ａ)。針が平行線と交わる確率ｐは、 ｐ＝２ｌ/ａπ・・・(*) となります。 ですから逆に、針が平行線と交わる確率ｐを統計的に求めれば、 円周率πの値が求められるというわけです。 (*)ｐ＝２ｌ/ａπ について 針が平行線と交わるのは、どういう条件が成立した場合なのかを考えてみます。 上の図のように、針を平行線のなす角をθ、 針の中心点から最も近い平行線までの距離をｙとします。 このとき、 ０≦ｙ≦ａ／２、０≦θ≦π であり、針と平行線が交わるのは、 ｙ≦(l/2)sinθ が成立するときです。 上のグラフでいうと、ブルーの部分が、針と平行線が交わる場合です。 ですからこのグラフの面積比から針と平行線が交わる確率を求めることができるわけです。 針と平行線が交わる確率ｐ＝（ブルー
凸包を求める - きしだのHatena
前回のようなランダムな点があったとき、その点を全部含んでへこみのない多角形を作成するという問題。 アルゴリズムとしては、「他の点でできる三角形に含まれてたら凸包上の点じゃない」という考え方で、全部の組み合わせの三角形について全部の点を走査します。最適なアルゴリズムではないですが、とりあえず今回はこれで。 で、点Pが三角形ABCに含まれるかどうかは、三角形ABCが時計周りだとしたら、三角形ABP、BCP、CAPも時計回りだということを使います。 点Pが三角形ABCの外にある場合は、三角形ABP、BCP、CAPのどれかが三角形ABCと逆周りになります。 三角形の向きは符号付面積を使うのですが、三角形の座標をそれぞれ(x1, y1)(x2, y2)(x3, y3)とすると(x1 - x2)(y1-y3)-(x1-x3)(y1-y2)で得られます。 そうやって凸包上に乗らない点を削除したら、隣り合
分布推定アルゴリズム - yukobaのブログ
分布推定アルゴリズム。遺伝的アルゴリズムを改良した物です。個体の集合を交叉・突然変異させるのではなく、個体の生成確率を進化させます。最適化問題のアルゴリズムです。以下、自分へのメモです。わかったことが増えたら追記するかも。 ビットストリング 計算量に関しては、ビット数をn、反復数をTとしています。 Population-Based Incremental Learning (PBIL) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.61.8554 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5424 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.1108 Population-ba
マーチング・キューブズ法の「14通り」の謎を解く - nursの日記
Isosurfaces: Geometry, Topology, and Algorithms 作者: Rephael Wenger出版社/メーカー: A K Peters/CRC Press発売日: 2013/07/31メディア: ハードカバーこの商品を含むブログ (1件) を見るマーチング・キューブズ法(Marching Cubes)は、３次元格子の頂点位置において定義された値（値そのものの意味は任意：温度、密度、存在確率、、などなど）をもとに、「等値面」を作成するためのよく知られた手法である。私もこれまでに何度か実装したことがあり、未熟な実装であったとはいえ、閾値を変えるにつれて等値面が変形する様を見ては楽しんだものである。 等値面を作成する上で、ある種自明と考えられなくもない手法であるにもかかわらず、特許化されたということもあり、ソフトウェア特許の功罪や難しさを語る際の代表的な事例
最大マージン kNN と SVM の関係: kNN も最近はがんばっています - 武蔵野日記
先日書いた機械学習における距離学習の続き。 kNN (k-nearest neighbour: k 近傍法)は Wikipedia のエントリにも書いてある通り、教師あり学習の一つで、あるインスタンスのラベルを周辺 k 個のラベルから推定する手法。memory-based learning と呼ばれることもある。単純に多数決を取る場合もあれば(同点を解決する必要があるが)、近いインスタンスの重みを大きくする場合もあるのだが、いずれにせよかなり実装は単純なので、他の機械学習との比較(ベースライン)として使われることも多い。 簡単なアルゴリズムではあるが、1-NN の場合このアルゴリズムの誤り率はベイズ誤り率(達成可能な最小誤り率)の2倍以下となることが示されたり、理論的にもそれなりにクリアになってきているのではないかと思う。また、多クラス分類がちょっと一手間な SVM (pairwise に
スペクトラルクラスタリングは次元圧縮しながらKmeansする手法 - 武蔵野日記
機械学習系のエントリを続けて書いてみる。クラスタリングについて知らない人は以下のエントリ読んでもちんぷんかんぷんだと思うので、クラスタリングという概念については知っているものとする。 それで、今日はスペクトラルクラスタリングの話。自然言語処理以外でも利用されているが、これはグラフのスペクトルに基づくクラスタリングの手法で、半教師あり学習への拡張がやりやすいのが利点。なにをするかというとクラスタリングをグラフの分割問題(疎であるエッジをカット)に帰着して解く手法で、どういうふうに分割するかによって Normalized cut (Ncut) とか Min-max cut (Mcut) とかいろいろある。 完全にグラフが分割できる場合はこれでめでたしめでたしなのだが、実世界のグラフはそんな簡単に切れないことが往々にしてある。それで近似してこのグラフ分割問題を解くのだが、Normalized c
Link Analysis and Related Topics - Home
2008年度 先端情報科学特論 II & IV リンク解析と周辺の話題 担当 新保 仁 shimbo@is.naist.jp 日時 2008/11/10, 11/17, 12/1, 12/8 (全 4 回) - 4限 15:10-16:40 場所 情報棟 L3 講義室 リンク解析は, グラフ (ネットワーク) データの構造から有用な情報を抽出するための, データマイニングの一研究分野です. この講義ではまず, リンク解析が取り扱う 2 種類の尺度 (重要度と関連度) について述べ, それぞれの代表的な計算手法を紹介します. 後半では, 近年機械学習分野で盛んに研究されているカーネルのうち, グラフ上の節点に対して定義されたカーネル (グラフカーネル) と, そのリンク解析への応用について紹介します. 第1回 11月10日 スライド 第2回 11月17日 スライド 第3回 12月1日
フラクタルタイポグラフィー - lab
Web Designing（2009年2月号）の特別企画「Webデザイナーのためのタイポグラフィ大特集」に掲載させていただいた「Fractal Type」についてご紹介します。 Web Designing誌にも書きましたが、アートディレクターで師匠の永原康史さんのアイデアで、「デザイン言語2.0」の装丁に使う「行間、字間、書体を文章中の各文字にバラバラに適用するグラフィック」のためのプログラムをJavaScriptで実装しているときに、フラクタル的な造形の中に文字を投げ込んでみたらどうなるかという興味で作ったものです。
ソートアルゴリズムの可聴化 - ならば
Sorting Algorithm Animationsなどのサイトでは、ソートアルゴリズムの可視化の例を見ることができる。今回は可視化に倣ってソートアルゴリズムを可聴化した。聴覚化すると、情報を分かりやすく提示するという方向から外れるけど。 ソートする対象は50から90までの整数をランダムに並べた列。可聴化の方法は、整数をMIDIノート番号とみなして、ソートアルゴリズムが各時点でポイントしている位置にある、MIDIノート番号の音高の音を鳴らすようにした。ChucKのプログラムはいつもより長くなったから最後に載せる。 録音したもの。元の整数列は全部同じで、サイズ（整数の数）は30。 バブルソート 選択ソート 挿入ソート シェルソート クイックソート マージソート ヒープソート 拡張としては、 より詳細に情報を提示する方向（例：整数同士の位置の交換時に音色を変える） サウンドアートな方向（例
計算量を具体的に見てみる 2009-01-06 - きしだのはてな
アルゴリズムの話では、計算量の解析がかかせません。 計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。 こういった話はどのアルゴリズムの本にも載ってるはずですが、具体的にどのようなプログラムを書くとそのオーダーになるかという記述はあまりありません。 ということで、やってみました。 計算時間表示のための共通処理を行うクラスは、一番最後に書いてます。 O(1) 計算時間がO(1)のアルゴリズムは、処理が入力の量によらない場合です。 配列の要素のアクセスや、ハッシュテーブルによるデータ検索、連結リストへの追加削除などがこれにあたります。 コードには入力量でのループが含まれません。 public class O1 extends ViewCompFrame{ @Override void compute(int n) { proc();
新はてなブックマークでも使われてる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に負けていた。しかし、学習が早いというのは実アプリケーシ
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
アルゴリズムコンテストの挑み方 (3) - d.y.d.
17:19 08/11/27 TopCoder Code Jam の練習に……と思ってしばらく前から TopCoder のSRMに参加してたのですが、 せっかくなので cafelier@SRM に記録をつけることにしました。 どういう試行錯誤をしながら提出した時のコードにいたったのかを、 できるだけ詳細にメモろうと思っています。 426以前のは記憶から掘り起こして書いたのでちょい大ざっぱですが。 これまで何回かここで書いたような整然とした考え方を本当に自分がしているかいうと、 してないよなー、と薄々思ってしまっているので、じゃあどういう風にやっているんだろうかと。 自分のふり見て我がふり直す。 20:26 08/11/24 論文 PLAN-X 2009 通ったみたいです。ばんざい。 ただでさえD論まったく間に合う気がしないのに、camera ready版なんて作ってる時間が… オートマトン
バイオ系雑誌に載った機械学習/計算機科学の解説記事 - Loud Minority
主に計算機科学の機械学習・データマイニング系の説明で、バイオの雑誌に載った解説記事です。ツールを使いこなす人が、中身を知りたかったり、作る人に変身したい場合や、情報科学(機械学習、データマイニング系）の人が、ゲノム解析などでどうやって利用されているのかを知るのに良いとおもう。追加する記事募集です。 決定木の解説 What are decision trees? Carl Kingsford & Steven L Salzberg Nature Biotechnology 26, 1011 - 1013 (2008) http://www.nature.com/nbt/journal/v26/n9/abs/nbt0908-1011.html EMアルゴリズムの解説 What is the expectation maximization algorithm? Chuong B Do & Se
Conjugate Gradient (CG)
概要 CG法(Conjugate Gradient Methods)はM.R.HestenesとE.Stiefelによって1952年に提案された方法である[1]。 CG法は正定値対称行列に対して使われる連立一次方程式を反復法で解くための手法である。 行列の正値対称性 ベクトルの内積をのように書く。 実行列が正定値対称とは、 ということであり、が対称であるということは、 が成り立つということである。 ＣＧ法の基本原理 今、次のような線形同次方程式を解くとする。 CG法は回目の反復において、次のようにこの方程式の解や誤差を用いて定義される誤差のノルム (等号成立はのとき) を最小化するような近似解を部分空間の中から見つける方法である。但し、はクリロフ部分空間(Krylov Subspace)である。 つまりCG法は次のような連立一次方程式の近似解を探すための方法である。 このように部分空間の中
高速な算術圧縮を実現する「Range Coder」
はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。 対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望ま
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムデザイン - yasuhisa's blog
