最適化超入門
本スライドは、弊社の梅本により弊社内の技術勉強会で使用されたものです。 近年注目を集めるアーキテクチャーである「Transformer」の解説スライドとなっております。 "Arithmer Seminar" is weekly held, where professionals from within and outside our company give lectures on their respective expertise. The slides are made by the lecturer from outside our company, and shared here with his/her permission. Arithmer株式会社は東京大学大学院数理科学研究科発の数学の会社です。私達は現代数学を応用して、様々な分野のソリューションに、新しい高度AIシステム
「最強最速アルゴリズマー養成講座」関連の最新 ニュース・レビュー・解説 記事 まとめ - ITmedia Keywords
最強最速アルゴリズマー養成講座： そのアルゴリズム、貪欲につき――貪欲法のススメ アルゴリズムの世界において、欲張りであることはときに有利に働くことがあります。今回は、貪欲法と呼ばれるアルゴリズムを紹介しながら、ハードな問題に挑戦してみましょう。このアルゴリズムが使えるかどうかの見極めができるようになれば、あなたの論理的思考力はかなりのレベルなのです。（2010/9/4） 最強最速アルゴリズマー養成講座： 病みつきになる「動的計画法」、その深淵に迫る 数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。（2010/5/15） 最強最速アルゴリズマー養成講座： アルゴリズマーの登
javascript - でデータを圧縮/伸張する : 404 Blog Not Found
2009年03月02日09:00 カテゴリLightweight Languages javascript - でデータを圧縮/伸張する これでもまだ税率が高かったので。 404 Blog Not Found:javascript - Yet Another Base64 transcoder Base64の利点は、なんといっても「固定税率」、それも比較的「税率が低い」ことにあります。Paddingなしなら、3バイトが4バイトにencodeされるので、33%ということになります。これに対してencodeURIComponentの税率は、UTF-8基準で最高で3倍、UTF-16基準で最高で4.5倍にも達します。 ついに負の税率、すなわち税還付を実現しました! まずはデモを。 Inflated + Base64-Decoded (Original): chars / bytes Deflate
素数10億まで3秒 - ita’s diary
404 Blog Not Found: C - で素数を数え直したら、範囲10億で10秒切ったお むむ、以前自分が書いた奴だと、ホットスポットでやってる事はほとんど同じなのに30秒ほどだった。 for (p=2, 3, 5, 7, 11, ...) for(i=istart; i<size;i += p*2) pflag[i]=0; danさんの場合, 1bit でフラグを記憶してるのでメモリが1/8 で済む。そこでメモリアクセスの時間が効いてるんだろう。それならキャッシュに収まる位のブロックに計算を分割しその内側で素数pのループ回せばもっと速くなるかも？と思いやってみた。見事3秒で終わった! 以下コード danさんのbitmap.cに以下を追加 bitmap *bitmap_block(bitmap *parent, size_t offset, size_t size){ if (!s
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
手作り有限状態機械で字句解析
a.py #!/usr/bin/env python class Parser(object): def __init__(self): self.parse1 = self.parse_main self.items = [] self.item = '' return def feed(self, text): i = 0 while i < len(text): (self.parse1, i) = self.parse1(text, i) return def parse_main(self, text, i): c = text[i] if c == ',': self.finish_item() return (self.parse_main, i+1) elif c == '"': return (self.parse_quote, i+1) elif c == '\\':
Polynomial Semantic Indexing -- 大規模データからのスケーラブルな距離学習 - 武蔵野日記
午後はNIPS 2009 読み会。 Bing Bai, Jason Weston, David Grangier, Ronan Collobert, Kunihiko Sadamasa, Yanjun Qi and Corinna Cortes, Mehryar Mohri, "Polynomial Semantic Indexing" という論文について紹介してみた。 これはtsubosaka さんの日記にすばらしくまとまっているので、内容をあえて繰り返さず(クリアに書かれているので読む価値はあると思う)、感想を述べると、文書と文書の類似度を測る尺度としてこの polynomial semantic indexing はけっこう有用なのではないかな、と思った。@unnonounoさんと@tsubosakaさんも Twitter でつぶやいていたが、これは大規模なデータから低ランク近似して
SACHICA(類似文字列列挙アルゴリズム) - Yasuo Tabeiの日記
SACHICA(類似文字列列挙アルゴリズム)のC++による実装を公開しました。 http://sites.google.com/site/yasuotabei/sachica sachicaは、同じ長さの文字列集合を入力として、ハミング距離がある閾値以下のすべてのペアーを超高速に出力します。 アルゴリズムは、マルチソーティングという手法に基づきます。 詳しくは、ハミング距離がd以内で長さがmの文字列集合があったとします。初めに、各文字列をk (> d)の部分文字列のブロックに分割します。 今、ハミング距離がd以内の文字列のペアーを求めたいので、もし、ハミング距離がd以内の文字列のペアーが存在すれば、鳩の巣原理により、それらにはk - d個の完全一致するブロックが存在します。この原理に基づき、sachicaはcombination(k, k-d)のすべての組み合わせのブロックをラディックスソ
[プログラミング] ビット並列アルゴリズムを使った編集距離 - 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)
Diff algorithm - 枕を欹てて聴く
id:smoking186 さんの指摘を受け, First Authorの名前などを付加しました. どうもです. 記事内のcodeは最適化などを施しておらず, 冗長に, 定義どおりに書いています. ifがまとめられたりとかしますが, そのあたりはご容赦を... Rubyでlevenshtein距離を見て以来, 個人的にdiffブームが来ていた. 計算量O(ND) / O(NP)のalgorithmなどがあるのは知っていたが, 論文(英語)および, 解説のみ, またはソースコードのみなど分かれているものが多く, algorithmに疎い自分には理解するのに大変時間がかかってしまった. しかしやっとわかったので, 解説+JS実装してみる. 解説とソースコードがセットだと, 多少はわかりやすくなるかと... 自分は正直これくらい細かく言われないとすぐにはわかんない人なので(the O(ND)だけ
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意していま
バージョン管理システムのdiffのパフォーマンス測定 - 考える人、コードを書く人
最近、C++でdiffを書いているせいか、バージョン管理システムで使われているdiffのパフォーマンスが気になったので、調べてみた。バージョン管理システムにおいてdiffはかなり重要である。というのも、diffもしくはそれに相当する処理は単に差分を表示する際だけでなく、updateやmerge時の差分適用など、至るところで行われるので、diffが遅いとバージョン管理システムにおけるありとあらゆる動作が遅くなってしまうからだ。 測定に使用したバージョン管理システム 測定に使用したバージョン管理システムは以下の通り。 Subversion-1.5.2 Monotone-0.41 Git-1.6.0.1 Mercurial-1.0.2 ちなみに上記のソフトを選択した理由は単に自分が普段から検証も含めて使用しているというだけです。 準備 まず、以下のような2種類のファイルの組合せを用意する。 Ty
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
ウノウラボ Unoh Labs: diff with C++
ミートソーススパゲティを作るときは、ミートソースから作るのが信条のbokkoです。それはさておき、今日はdiffのお話です。 diff diffは指定した2つのファイルの差分を求めるコマンド、もしくはその差分そのものを指します。普段から何気なく使用しているコマンドですが、その中で使われているアルゴリズムは結構難しいです。 差分を計算するということ 差分を計算するというのは以下の3つを求めることに帰結します。 ・Levenshtein Distance(Edit Distance) ・LCS(Longest Common Subsequence) ・SES(Shortest Edit Script) 上から順に1つずつ説明していきます。 Levenshtein Distance Levenshtein Distanceは2つのシーケンスの違いを数値化したもので編集距離とも言います。これは後述
転置インデックスを実装しよう - mixi engineer blog
相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。 デモ モチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java 6の日本語文書を対象としているので、「stringbuffer」とか「コンパイル」とか「倍精度浮動小数」とかそれっぽい用語で検索してみてください。 インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら（テンプレートはこちら）です。 でも、今回はUIの話ではないのです。ものすごく地味に、全文検索
接尾辞配列 - Wikipedia
元の文字列があれば、接尾辞の開始位置を指定することですべての接尾辞を余すことなく得ることができる。この接尾辞を辞書順に並べたときの開始位置の配列が接尾辞配列となる。 "abracadabra"に対する接尾辞配列は、表のように、(11, 8, 1, 4, 6, 9, 2, 5, 7, 10, 3) となる。接尾辞 "a" の開始位置は11で、接尾辞 "abra" の開始位置は8だからである。 "abracadabra"に対して、12番目の接尾辞として空文字を考えることができる。しかし、これは常に先頭に配置されることになるので特に情報を持たないので、省略しても問題ない。 構築法[編集] 接尾辞配列を構築する最も容易な方法は、効率的な比較ソートを利用することである。この場合、回の接尾辞の比較が必要になるが、接尾辞の比較は の時間が必要となる。従って全体的な計算時間は となる。より精巧なアルゴリズ
自然言語処理における半教師あり学習のテキスト - 武蔵野日記
最近移動続きであまり研究に時間は割けないのだが、本は読めるということで本を2冊、サーベイ的な記事を3本(うち2本はチュートリアルスライドつき)を紹介する。まず Semisupervised Learning for Computational Linguistics (Chapman & Hall/CRC Computer Science & Data Analysis) 作者: Steven Abney出版社/メーカー: Chapman and Hall/CRC発売日: 2007/09/17メディア: ハードカバーこの商品を含むブログ (4件) を見る を読む。この本の著者の Steven Abney はブートストラッピングの理論的解析をした人で、 Steven Abney. Bootstrapping. 40th Annual Meeting of the Association fo
Ngram(N-gram)とは何か & 形態素解析との比較[ガラケー版]
2006/02/03 「検索エンジン&SEO > 検索エンジンの仕組み > Ngram(N-gram)とは何か & 形態素解析との比較」 [この書込みのみ表示(記事URL紹介用) / 編集 / 削除 / トラバ送信 / 共有分類に追加(タグ付け)]拍手:25個 1. 書こうと思ったきっかけ 2. Ngram(N-gram)とは 3. 向きと不向き 4. Ngramの実装 5. NGramの例(bigram=2文字切り出し時) 6. Ngramの有名な欠点 7. 形態素解析とは 8. 形態素解析の欠点 9. 形態素解析結果の実際例 10. まとめ: とはいえ鋏と包丁は使い様 11. コードのサンプル 12. ちなみにこのサイトの検索エンジンは... 13. ということで、検索エンジンを作ってリリースしてみた 1. 書こうと思ったきっかけ ライブドアのブログ検索がNgramを採用したと記事にな
確率論、統計学関連のWeb上の資料 - yasuhisa's blog
確率論と統計学は俺がまとめるから、他の分野はお前らの仕事な。 確率論 Index of /HOME/higuchi/h18kogi 確率空間 生成されたσ-加法族 確率の基本的性質 確率変数とその分布 分布の例 分布関数 期待値、分散、モーメント 期待値の性質 独立確率変数列の極限定理 大数の弱法則(Weak Law of Large Numbers) 確率1でおこること 大数の強法則 中心極限定理 特性関数 Higuchi's Page Brown運動 Brown運動のモーメントの計算 連続性 Brown運動の構成:Gauss系として Brown運動に関する確率積分 空間L^2の元の確率積分 伊藤の公式(Ito formula) 日本女子大学理学部数物科学科の今野良彦先生のところにあった資料 最尤法とその計算アルゴリズム 収束のモード 大数の法則と中心極限定理 指数分布族モデルにおける最
アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 : 404 Blog Not Found
2009年01月31日01:00 カテゴリLightweight LanguagesMath アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 これなのですが.... 同じ文字列のn回繰り返しを作る最速の方法を探求してみた - muddy brown thang ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。 なぜかもっとシンプルな奴がなかったので。 以下、比較。初期値はIEにあわせてあります。Firefox/Saf
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
