ニューラルネットワークの量子化についての最近の研究の進展と、その重要性 - SmartNews Engineering Blog
こんにちは、スマートニュースの徳永です。深層学習業界はGANだとか深層強化学習だとかで盛り上がっていますが、今日は淡々と、ニューラルネットワークの量子化の話をします。 TL;DR パラメータだけを量子化するのであれば、ほぼ精度を落とさずに、パラメータのデータ容量は1/16程度にまで削減できる パラメータ、アクティベーション、勾配のすべてを量子化し、推論だけでなく学習までもビット演算だけで実現する研究が進んできている 現在は深層学習 = GPU必須というぐらいの勢いがあるけど、量子化の研究が進むと、今後はどうなるかわからないよ はじめに 情報理論における量子化とは、アナログな量を離散的な値で近似的に表現することを指しますが、本稿における量子化は厳密に言うとちょっと意味が違い、十分な（=32bitもしくは16bit）精度で表現されていた量を、ずっと少ないビット数で表現することを言います。 ニュ
すばらしいビット | POSTD
unsigned int v; //only works if v is 32 bit v--; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v++;
Union Findアルゴリズムの様々な実装とパフォーマンス計測 - $shibayu36->blog;
CourseraにAlgorithms Part1という授業があり、これが非常に評判が良いので、会社で勉強会をしている。Week1にUnion Findというアルゴリズムが出てきて、その実装パターンがいくつかあった。それぞれ計算量が違うらしいのだけど、速度がどのように変化するか試したかったので、実装してパフォーマンス計測をしてみた。それぞれの実装の詳しい説明が知りたかったら、https://www.coursera.org/learn/algorithms-part1 を見ると良い。 Union Findとは何か 二つのノードを繋いでいき(Union)、あるノードとあるノードがつながっているか(Find or Connected)を判定するアルゴリズム。 例えば、union(1,6)、union(5,6)、union(2,7)、union(3,8)、union(4,9)、union(8,9
どうぶつしょうぎ名人 - まめめも
どうぶつしょうぎ AI を作りました。絶対に勝てません。無力感を味わってください。 ref: http://mame.github.io/dobutsu-shogi-master どうぶつしょうぎとは 3 マス x 4 マスの単純化された将棋です。ライオン（王相当）、ぞう（1 マスしか進めない角行）、キリン（1 マスしか進めない飛車）、ひよこ（歩相当、にわとりに成ったら金相当）の 4 種類の駒を動かして、相手のライオンを取るか、トライ（ライオンを一番奥の行まで運ぶ、ただし直後に取られる場合はだめ）に成功すれば勝ちです。詳しくは Wikipedia の記事を見てください。 どうぶつしょうぎは後手必勝であることが知られています（研究報告）。つまり、後手が正しくプレイする限り、先手は絶対に勝てません。どうぶつしょうぎ名人は常に正しくプレイするので、先手のあなたは絶対に勝てません。 なんで作ったの
文字列マッチングのためのLCP Arrayを構築する - $shibayu36->blog;
前回のブログ記事で、文字列マッチングをするためのSuffix Arrayという構造を構築した。このSuffix Arrayという構造だけでも、テキスト長をn、パターン長をmとして、の計算量で文字列マッチングできるようになった。 suffix arrayを一番簡単なアルゴリズムで実装する - アルゴリズム学習(その6) - $shibayu36->blog; suffix array構築のメモリ効率を良くする - アルゴリズム学習(その7) - $shibayu36->blog; しかし、前処理としてSuffix ArrayからLCP Array(Longest Common Prefix Array)という構造をさらに作っておくと、という計算量で文字列マッチングが出来るようになるらしい。そこで、今回はLCP Array(Longest Common Prefix Array)の構築を実装し
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
PythonによるRapidly-Exploring Random Trees (RRT)パスプランニングサンプルプログラム - MyEnigma
目次 目次 はじめに Rapidly exploring random tree:RRTとは? RRTの利点と欠点 利点 欠点 RRTによるパスプランニングPythonサンプルプログラム シンプルなRRTパスプランニング (Goal biased sampling) パスのスムージング後処理付きRRTプランニング 車両ロボット用RRTプランニング RRTのパス収束の高速化の手法 Goal Bias Sampling Goal Zone Sampling RRTの問題点 参考資料 MyEnigma Supporters はじめに 以前、A*やダイクストラ法、Dynamic Window Approachによる パスプランニングシステムのサンプルプログラムを公開しましたが、 myenigma.hatenablog.com myenigma.hatenablog.com myenigma.hat
Behind the Scene: “すべてがFになる” ED映像
多分日本語の方が情報多めですSome of the content on this website is licensed under Creative Commons. Please feel free to refer to or quote the content which has CC-BY on the bottom right corner of the page for whatever you want, including commercial use. Behind the ScenesList of making-of articles Presentation SlidesI always publish my slides after my presentation. FITC Tokyo 2016 - Think of "Look": Designing vi
マジックカーネル – 画像のリサンプリングのメソッド | POSTD
マジックカーネルとは？ “マジックカーネル”とは、極めて高速で（一番単純なバージョンなら、必要なのは少しの整数加算とビットシフトのみです）、驚くほどの結果を出してくれる効果的な画像のリサンプリングのメソッドです（エイリアシングノイズやリンギング、細かい物体の”Width beat”の発生を防ぎます）。 私がこのマジックカーネルと出会ったのは2006年、一般的に使われているJPEGライブラリのソースコードを扱っていた時のことです。それ以来、この素晴らしい特性を深く探り、任意のリサンプリングファクタのケースにまでこのメソッドを広げました。 このWebページでは、それらの特性を要約して説明し、画像への適用も含めてマジックカーネルのC#のコード実装の全てをご紹介します。 マジックカーネルはどこから来たのか 2006年に私は、JPEGを過剰に圧縮すると発生するブロックノイズを最小限に抑えるいい方法は
高次元ベクトルデータにおいて高速な近傍検索を実現するNGTの公開
Yahoo! JAPAN研究所の岩崎です。 私は主に特定物体認識の研究開発を行っていますが、その一方で特定物体認識において必須技術である高次元ベクトルデータの近傍検索の研究開発も行っています。近傍検索の一種であるk最近傍検索とは、クエリとしてベクトルデータが与えられた時に、クエリと空間内に点在するベクトルデータとの距離に基づき近い順にk個のデータを検索する、ことです。kが5の場合の最近傍検索の例を図1に示します。図中の数字は距離の順位で、青い点が検索結果となるデータです。 空間内のすべてのデータとの距離を計算すると時間がかかるので、高速化のためにインデックスを利用します。インデックスを用いることにより数次元といった低次元のベクトルデータ空間では高速な検索が比較的容易に実現できます。しかし、インデックスを用いても100次元を超えるような高次元ベクトルデータの場合には高速に検索することが困難と
米Google、新しいデータ圧縮アルゴリズム「Brotli」を発表 | OSDN Magazine
米Googleは9月22日、新たなロスレスデータ圧縮アルゴリズム「Brotli」を発表した。Deflateと同等の速度でより高い圧縮率を実現するという。オープンソースでコードを公開し、データフォーマットの仕様はインターネット技術タスクフォース（IETF）で公開されている。 Googleは2013年にDeflate互換の圧縮アルゴリズム「Zopfli」を発表している。このZopfliはPNGオプティマイザに統合されるなど、業界から肯定的なフィードバックを得られたという。BrotliはZopfliの利用から学んだことを取り入れつつ、Webフロント側の圧縮など新しいニーズを受けて開発したと経緯を説明している。 Brotliは汎用のロスレス圧縮アルゴリズムで、LZ77派生アルゴリズムやハフマン符号、二次コンテキストモデリングなどの技術を組み合わせているという。データフォーマットはDeflate互換
Scalaで型レベル”だけ”でクイックソート | POSTD
Scalaの型システムが先進的であることは、皆さんもご存じのことかと思います。この投稿では、Scalaの型システムのみを使った クイックソート アルゴリズムの実装方法をご紹介したいと思います。なお、ここで紹介するデモの完全なコードは こちら をご覧ください。 自然数 まずは準備から。ソートアルゴリズムを実装するには、ソートする対象が必要ですよね。ここでは自然数を用います。もちろん、Scalaの型システムには利用可能な自然数はありません。そんなわけで、全ての自然数の型を作る必要があります。 型を無限に作るというのは、恐らく時間の浪費になるでしょうから、ここはもう少し賢い手を考えます。そう、数学を使いましょう。 ペアノの公理 ペアノの公理とは、自然数を形式的に定義するためのシンプルな方法のことです。 0 は特別なものとする。 0 は自然数である。 全ての自然数 n には、それに続くもう1つ別の
プログラミングコンテストで、C++を使って全ての問題を解くのに必要なアルゴリズムは何ですか？ | POSTD
これが私の提案するリストです。必要とされるアルゴリズムや概念のほとんどが挙げられています。いくつかの要素はアルゴリズムではなかったり（フェイクや状態、関心事など）、重複していたりもします。 最後に1つ、アドバイスを。 知識を蓄える前に、まずは思考能力を鍛えることを重要視しましょう。これはコンテストのみならず、あなた自身の将来にも役立ちます。思考能力を鍛えるには、アルゴリズムではなく純粋な思考を必要とする、アドホックを使いこなせるようになりましょう。 topcoderのDiv2とCodeforcesのDiv2の2つに集中することも効果的だと思います。どちらも、低いレベルから問題に取り組んでいきましょう。例えば、Div2-250をマスターしてからDiv2-500に取り組む、などです。
簡潔データ構造 LOUDS の解説（全12回、練習問題付き）
「日本語入力を支える技術」（通称「徳永本」）や「高速文字列解析の世界」（通称「岡野原本」）で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。 友達に教える時に使ったもので、練習問題付きです。 実際に紙に書いてやってみるとわかりやすいと思います。 詳解 LOUDS (1) LOUDS とは 詳解 LOUDS (2) ビット列を作ってみる 詳解 LOUDS (3) 0番ノード 詳解 LOUDS (4) ビットの意味 詳解 LOUDS (5) 木構造の復元 詳解 LOUDS (6) インデックスでノードを表す 詳解 LOUDS (7) ノード番号からインデックスを得る 詳解 LOUDS (8) インデックスからノード番号を得る 詳解 LOUDS (9) 子ノードから親ノード 詳解 LOUDS (10) 親ノードから子ノード 詳解 LOUDS (11) 木の検索 詳解
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
完備辞書（簡潔ビットベクトル）の解説 - アスペ日記
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。 LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。 また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。 この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。 今回は、このデータ構造*2について書いてみます。 完備辞書でできること ビット列に対する定数時間の rank と selectです*3。 rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。 select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。 それぞれ例を挙げます。
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
Line search - Wikipedia
In optimization, line search is a basic iterative approach to find a local minimum of an objective function . It first finds a descent direction along which the objective function will be reduced, and then computes a step size that determines how far should move along that direction. The descent direction can be computed by various methods, such as gradient descent or quasi-Newton method. The step
病みつきになる「動的計画法」、その深淵に迫る
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
