できる動的計画法：ロッド切り出し問題 | POSTD
私が常に頭を悩まされていたのが最適化問題です。これは、コードを理解するだけでも非常に困難な問題です。そこで、これまでに私が学んだことを基に、典型的な動的計画法の問題を取り扱ういくつかの記事を投稿することにしました。今回取り上げるロッド切り出し問題は古典的な最適化問題であり、動的計画法の一例と言えます。 ロッド切り出し問題とは？ ロッド切り出し問題は、現実世界で私たちが直面するたいていの問題に非常によく似ています。ある長さの棒があり、この棒を最大利益が得られる長さにして切り売りをしたいという状況があると仮定します。ここで問題となるのは、切り出した長さによって棒の値段が異なる点です。例えば細かく切り出した方が大まかに切り出した場合よりも、より多くの利益が得られる可能性があるため、ちょっと違った考え方をする必要があります。 先に進む前に、まずはこの問題をより正確に定義しておきましょう。 長さ n
GoogleのSHA-1のはなし
5. • その暗号技術がどのぐらい安全かを表す大雑把な指標 • nビットセキュリティは2 𝑛 回攻撃が必要 • 1回あたりの攻撃コストはあまり気にしない • 𝑂 2 𝑛 という表記 セキュリティビット 𝑛 直線 :𝑂(𝑛) 3次関数 : 𝑂(𝑛3 ) 指数関数 : 𝑂(2 𝑛) 𝑂(log 𝑛) 5 / 21 6. • 第二原像計算困難性（弱衝突耐性） • 𝑚1に対して𝐻 𝑚2 = 𝐻 𝑚1 となる𝑚2 ≠ 𝑚1が分からない • 同じじゃなくてもいいから何か一つ見つけるのが困難 • 𝑂(2 𝑛 )回トライ ; nビットセキュリティ • 衝突困難性（強衝突耐性） • 𝐻 𝑚1 = 𝐻(𝑚2)となる𝑚1 ≠ 𝑚2を見つけるのが困難 • 𝑂(2 𝑛/2 )回トライ ; 𝑛/2ビットセキュリティ • 第二原像を見つけるのは単なる衝突より2
第3回 機械学習のためのベイズ最適化入門|Tech Book Zone Manatee
応用範囲が広く幅広い視点からの説明になりがちなベイズ最適化について、本記事では機械学習のハイパーパラメータ探索に利用することに限定して解説します。 1. はじめに 最近、ベイズ最適化という手法が注目を集めています。 ベイズ最適化 (Bayesian Optimization) とは、形状がわからない関数 (ブラックボックス関数) の最大値 (または最小値) を求めるための手法です。 ベイズ最適化についての入門記事は Web 上にすでにいくつかありますが、ベイズ最適化は応用範囲が広く、入門記事は様々な応用に向けた幅広い視点からの説明になりがちです。 本記事では、機械学習ユーザに向けて、ベイズ最適化を機械学習のハイパーパラメータ探索に利用することに限定して説明します。 これにより、機械学習に対して、ベイズ最適化がどのように利用できるのかを分かりやすく解説したいと思います。 2. ハイパーパラメ
数値最適化のインタラクティブ・チュートリアル | POSTD
「数値最適化」は機械学習における中心的手法の1つです。多くの問題では、最適解を直接突き止めることは難しいものですが、ある解がどれほど適しているかを測定する損失関数を設定し、解を見つけるためにその関数のパラメータを最小化することは比較的容易です。 かつてJavaScriptを初めて学ぼうとしていた時 、結果的に数値最適化ルーチンを多数書きました。そのコードを特に使うこともなく置いていたので、それらのアルゴリズムの動作をインタラクティブな形で可視化したら面白いのではないかと考えました。 本記事の良い点は、コードが全てブラウザで実行できることです。つまり、アルゴリズムの動作をより把握するために、各アルゴリズムのハイパーパラメータをインタラクティブにセットしたり、初期位置を変更したり、どの関数が呼び出されるかを変更したりすることができるのです。 (編注：本記事ではスクリーンショットのみ公開しており
Word2Vec：発明した本人も驚く単語ベクトルの驚異的な力
Word2Vecとは Word2Vecで演算処理する Word2Vecとニューラルネットワーク Word2Vecの仕組み CBoW Skip-gram Word2Vecを応用することができる分野 レコメンド 機械翻訳 Q&A・チャットボット 感情分析 Word2Vecの弱点 Word2Vecの派生系や類似ツール GloVe WordNet Doc2Vec fastText まとめ 参考 世界中のWebサイトの数は2014年に10億件を超えたようだ。そして、Facebookのユーザー数だけでも16億人を超えている。 そして、そのいずれもコンテンツの中身の大部分はテキストから成り立っていることだろう。 ということは、莫大に増大し続けるネット上のデータのほとんどはどこかの国の言葉だってことだ。世界中の人が毎日テキストデータを生成し続けたことはこれまでの歴史上無かったんじゃないだろうか。 もしそん
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
珍しいSHA1ハッシュを追い求めて - プログラムモグモグ
「SHA1ハッシュってあるだろう？」 放課後、いつものように情報処理室に行くと、高山先輩が嬉しそうな顔でそう言った。 「ええ、SHA1、ありますね」 「SHA1って何桁か覚えているかい？」 「えっと…」 一年下の後輩、岡村が口を開いた。 「50桁くらいはありましたっけ…？」 先輩はパソコンに向かって何かを打ちはじめた。 現在、情報部の部員は三人しかいない。部長の高山先輩と、二年の自分と、後輩の岡村だ。いや、正確に言うと、先輩の学年にはもう少しいたのだが、もうほとんど部室に来ることはなくなってしまった。無理もない、この季節になると先輩たちは受験勉強で忙しくなる。 「例えば、こういうふうに… 適当なSHA1の長さを…」 echo -n | openssl sha1 | awk '{print length}' 部長だけは今も部活に来てこうやって色々なことを教えてくれている。本人曰く、普通に勉強
情報理論を視覚的に理解する (1/4) : | POSTD
世界を考察する新しい方法を手に入れたときの感覚が大好きです。特に好きなのは、いずれ具体的なコンセプトに形を変えるボンヤリとした考えがあるときです。情報理論は、その最たる例です。 情報理論は、多くの物事を説明するための正確な言葉を与えてくれます。自分はどのくらい理解できていないのか？質問Aの答えを知ることが、質問Bを答えるのにどのくらい役立つのか？ある種の信念が他の信念とどの程度似ているのか？こういうことに対し、若くて未熟なころから自分なりの考えがありましたが、情報理論に出会って正確で強固な考えとしてはっきりと固まりました。その考えは、桁外れの、例えばデータの圧縮から量子物理学や機械学習、さらにはその間に広がる数多くの分野に応用が利くものです。 残念なことに、情報理論は少々威嚇的に見えてしまうのですが、そう断定すべき根拠は全くないと思います。実際、情報理論の多くの重要な概念は完全に視覚的に説
高速なハッシュテーブルを設計する | POSTD
(訳注：2016/9/28、頂きましたフィードバックを元に記事を修正いたしました。) はじめに 本稿では、高速で汎用的なハッシュテーブルを作るために行う、設計についての多くの意思決定事項を紹介します。最終的に、私の emilib::HashSet とC++11の std::unordered_set の間のベンチマークが出来上がりました。もし、ハッシュテーブルに興味があって、自分で設計したいなら（どのプログラミング言語かに関わらず）、本稿がヒントになるかもしれません。 ハッシュテーブル は、素晴らしい発明です。 ならし計算量O(1) ( O(√N)時間 )で、挿入、削除、検索を行うことができます。ならし計算量とは、ハッシュテーブルの計算に平均でO(1)の計算量がかかることを意味しますが、時々、これよりも多くの時間がかかる場合があります。具体的には、ハッシュテーブルに空きがない場合で、挿入の
Facebook が、IBM Watson とはまったく異なる アルゴリズム & アーキテクチャ で「質問応答システム」市場 に参戦間近か？ ～ サービス名は「Memory Networks」 - Qiita
TechCrunch （2015/03/27）「Facebookの人工知能は、文章や動画の内容を理解して最適なコンテンツをユーザーに届ける」 Facebookは、人工知能の研究において目覚ましい進展を見せた。 今日のF8カンファレンスでは、CTOのMike Schroepferが、動画や文章の内容や文脈を認識する新しいシステムについて明かした。 （ 中略 ） この動画AIのプロトタイプは、487種類のスポーツを判別することができる。 しかもアイススケートとアイスホッケーのような少ししか違いのない競技も判別することができるのだ。 （ 中略 ） こちらの動画では、指輪物語の内容を数行にまとめたコンテンツをAIが理解している様子が見て取れる。AIはこのファンタジー小説の予備知識やキャラクターについては知らない。 AIはFacebookのMemory Network機能のおかげで、ストーリーの内容
HaskellDay2016_sakai
SAT/SMT solving in Haskell Masahiro Sakai ( ) Haskell Day 2016 2016-09-17 Self Introduction Masahiro Sakai Twitter: @masahiro_sakai github: https:/ /github.com/msakai/ G+: https:/ /plus.google.com/+MasahiroSakai Translated “Software Abstractions” and TaPL into Japanese with colleagues Interests: Categorical Programming, Theorem Proving / Decision Procedures, … Agenda What are SAT and SMT? Haskell
SAT/SMTソルバの仕組み
NLP コロキウム https://nlp-colloquium-jp.github.io/ で発表した際のスライドです。 論文: https://arxiv.org/abs/2205.01954 GitHub: https://github.com/joisino/wordtour 概要 単語埋め込みは現代の自然言語処理の中核技術のひとつで、文書分類や類似度測定をはじめとして、さまざまな場面で使用されていることは知っての通りです。しかし、ふつう埋め込み先は何百という高次元であり、使用する時には多くの時間やメモリを消費するうえに、高次元埋め込みを視覚的に表現できないため解釈が難しいことが問題です。そこで本研究では、【一次元】の単語埋め込みを教師なしで得る方法を提案します。とはいえ、単語のあらゆる側面を一次元で捉えるのは不可能であるので、本研究ではまず単語埋め込みが満たすべき性質を健全性と完
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
勾配降下法の最適化アルゴリズムを概観する | POSTD
(編注：2020/10/01、2016/07/29、いただいたフィードバックをもとに記事を修正いたしました。) 目次： さまざまな勾配降下法 バッチ勾配降下法 確率的勾配降下法 ミニバッチ勾配降下法 課題 勾配降下法を最適化するアルゴリズム Momentum(慣性) Nesterovの加速勾配降下法 Adagrad Adadelta RMSprop Adam アルゴリズムの可視化 どのオプティマイザを選ぶべき？ SGDの並列化と分散化 Hogwild! Downpour SGD SGDのための遅延耐性アルゴリズム TensorFlow Elastic Averaging SGD 最適化されたSGDに対する更なる戦略 シャッフル学習とカリキュラム学習 バッチ正規化 早期終了 勾配ノイズ 結論 参考文献 勾配降下法は、最適化のための最も知られたアルゴリズムの1つです。これまではニューラルネット
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Perspectives on pathfinding algorithms: Networks · ShapeScience
GitHub - tiny-dnn/tiny-dnn: header only, dependency-free deep learning framework in C++14
Non-manifold Implicit Surfaces
Line Simplification
R*-tree - Wikipedia
CoDiPack – Code Differentiation Package | Scientific Computing