アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ - Qiita
今の場合は A さんが 31 歳の場合のストーリーでしたが、A さんが 20 歳～ 35 歳のうちのどの年齢であったとしても、似たようなストーリーで必ず 4 回の質問で当てることができます！(他の例も是非考えてみてください。) ちなみに、このような「真ん中で切ってどちらかに絞って行く」タイプのアルゴリズムには二分探索法という名前がついています。応用情報技術者試験でも頻出のテーマですので馴染みのある方も多いと思います。 1-2. つまり、アルゴリズムとは 上の年齢当てゲームという問題では、相手の年齢を当てる「方法・手順」を二分探索法に基づいて導きました。このようにアルゴリズムとは、 問題を解くための方法・手順 のことです。さて、アルゴリズムと聞くと「コンピュータ上で実装されたプログラム」のことを思い浮かべる方も多いと思いますが、必ずしもコンピュータと関係がある必要はなく、日常生活でも多々登場
ディープラーニングの限界 | POSTD
(注：2017/04/08、いただいたフィードバックを元に翻訳を修正いたしました。 @liaoyuanw ) この記事は、私の著書 『Deep Learning with Python（Pythonを使ったディープラーニング）』 （Manning Publications刊)の第9章2部を編集したものです。現状のディープラーニングの限界とその将来に関する2つのシリーズ記事の一部です。 既にディープラーニングに深く親しんでいる人を対象にしています（例：著書の1章から8章を読んだ人）。読者に相当の予備知識があるものと想定して書かれたものです。 ディープラーニング： 幾何学的観察 ディープラーニングに関して何より驚かされるのは、そのシンプルさです。10年前は、機械認識の問題において、勾配降下法で訓練したシンプルなパラメトリックモデルを使い、これほど見事な結果に到達するなど誰も想像しませんでした。
EMアルゴリズム徹底解説 - Qiita
ステップ2 $r_{nk}$を固定して$J$を$\mu_k$で偏微分して最小化します。 式変形をすると、 クラスタ$k$の最適なCentroidは上記のように、クラスター$k$に所属しているデータの平均であることがわかりました。 上記より最初のデモンストレーションで行っていたアルゴリズムは損失関数$J$の最適化によって導出されたものを適用していたことがわかります。 2−3. 実装 上記で示した２ステップを計算して、イテレーションを回すだけのシンプルなプログラムです。最後に更新前のmuと更新後のmuの差を取り、それがある程度小さくなったら収束したと判断し、イテレーションを止めるようにしています。 下記はアルゴリズム部分の抜粋です。プログラムの全文はコチラにあります。 for _iter in range(100): # Step 1 =============================
ランキング設計はどうあるべきか？ その3｜深津 貴之 (fladdict)
ここまでランキングのあるべき方向性と、実行可能なアプローチについて考察してきた。そして、いよいよプロトタイピングと実験の時間だ。残念ながら自分はサーバーサイドのコードが書けないので、ここからは開発チームに託すことになる。 妄想や実証不能なものをオーダーするのは非効率だと思う。ある程度はクラスをモデリングしておくと、エンジニアとディスカッションしやすい（ように思える）。 とりあえずnoteでのランキングは、様々な試行錯誤や実験が予想される。そのため、以下のような要素が必須となる。 ・工数最小 ・あらゆるランキングを表現できる ・拡張しやすい 今回はDecoratorパターンとCommandパターンを混ぜたような実装で、柔軟性のあるランキング計算システムのコンセプトを描いてみた。下手なコードでも、設計がある方がエンジニアさんに説明しやすい。 設計イメージとしては、まずランキングの各処理を同じイ
Alpha Zeroの衝撃と技術的失業｜山本一成🚗TURING
2016年、Google DeepMind社から恐ろしい論文が出された、AlphaGoその名を冠した囲碁プログラムが既存の囲碁ソフトに勝率99％を叩き出したのだ。AlphaGoは強化学習とDeep Learningを組み合わせた囲碁プログラムで、その年に最強の囲碁棋士の一人である李世ドルさんに4勝1負で勝利した。その後も進歩を続けて今のAlphaGoの強さは人類が体感できるレベルを超えるほど強くなったと予想される。 2017年も終わりのころ、Google DeepMind社からまた途方もない論文が発表された。囲碁とほぼ同じ手法で最強レベルのチェスや将棋プログラムを超えたということだった。実際のところ正確に超えたのかどうかちょっとだけ疑問もあるのだが、まず前提として彼らの新手法が途方もない成果をあげたこと素直に祝福したい。彼らは自分たちのプログラムをAlpha Zeroと名付けた。 コンピュ
Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
はじめてのAdversarial Example
今回はadversarial exampleについて解説していきます。Adversarial exampleというのは、下図のように摂動を与えることによりモデルに間違った答えを出力させてしまうもののことです。 この例では、もともとモデルがパンダと正しく分類することができていた画像に摂動を与えることで、テナガザルと誤分類させています。しかし、人間には元の画像との違いはほとんど分からず、パンダのままに見えます。 Adversarial exampleは機械学習モデルを実用化していく上で大きな問題となります。例えば、交通標識をadversarial exampleにしてしまえば、自動運転車をだませてしまう可能性があります。 注目を集めてきている研究分野ですが、まだちゃんと調べたことがないという人も多いかと思います。今回もなるべく丁寧に解説していきたいと思います。 目次 基礎 攻撃 防御 論文紹介
Knuth multiplicative hash が最小完全ハッシュ関数であることの証明 | メルカリエンジニアリング
こんにちは！サーチチームの @metal_unk です。普段はサーバーサイドエンジニアとして、メルカリの検索を改善する仕事をしています。 メルカリには Be Professional Day という「普段できないことをやろう」をテーマとする日があり、その日は業務に直接関係のないことや、普段は手をつけられないリファクタリングなどがされます。Be Professional Day の様子はこちらで紹介されています。 tech.mercari.com わたしは今回の Be Professional Day で、Knuth multiplicative hash が最小完全ハッシュであることを証明しました。このブログはその証明についての記事です。 「普段できないことをやろう」という Be Professional Day では、証明もアリです。 Knuth multiplicative hash
Amazonの推薦システムの20年
IEEE Internet Computingの2017年5・6月号に "Two Decades of Recommender Systems at Amazon.com" という記事が掲載された。 2003年に同誌に掲載されたレポート "Amazon.com Recommendations: Item-to-Item Collaborative Filtering" が Test of Time、つまり『時代が証明したで賞』を受賞したことをうけての特別記事らしい 1。 「この商品を買った人はこんな商品も買っています」という推薦で有名なAmazonが1998年にその土台となるアルゴリズムの特許を出願してから20年、彼らが 推薦アルゴリズムをどのような視点で改良してきたのか 今、どのような未来を想像するのか その一端を知ることができる記事だった。 アイテムベース協調フィルタリング 20年前も
Big Sky :: レーベンシュタイン距離を使ったあいまい grep コマンド「lsdgrep」作ってみた
元ネタはずいぶんと昔の記事なのだけど。 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー ■ 編集距離 (Levenshtein Distance) 昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベン... http://d.hatena.ne.jp/naoya/20090329/1238307757 思い付きはまったく関係ない所から。 mp3 が数千ファイル入ってるフォルダで何かの手違いで同じ曲が入ってしまう事が結構あって重複取り去る作業してた。ID3が違ってるとMD5も違うのでレーベンシュタインの文字列距離を使ってファイル名が似てるの調べたら422ファイル消せる事が分かった。 — Vim芸人 (@mattn_jp) February 25, 2017 これを
Formalization and Proof of Distributed Systems (ja)
分散システムの形式化と証明について ＠情報システム特別講義D 2016年度筑波大学
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
DBエンジニアのミックさんが語る、RDBで階層構造データを扱う「入れ子集合モデル」の将来性
これまで階層構造データはリレーショナルデータベースでうまく扱えませんでしたが、その解決策としてジョー・セルコが提案したのが「入れ子集合モデル」です。この手法を紹介した『プログラマのためのSQLグラフ原論』の刊行にあたり、翻訳されたDBエンジニアのミックさんに入れ子集合モデルの将来性についてうかがいました。 なぜRDBで木と階層構造を扱う手法が1冊の書籍に？ ――『プログラマのためのSQLグラフ原論 リレーショナルデータベースで木と階層構造を扱うために』についてミックさんにうかがいます。最初に、本書がどういう本なのか教えていただけますか？ ミック：内容としては、リレーショナルデータベース（RDB）でグラフ構造の一つである木と階層構造を扱うための方法論「入れ子集合モデル」をメインに解説しています。RDBには大きな問題があり、入れ子集合モデルがそれを解決しうる手法だと見込まれています。その問題と
ディープラーニング（TensorFlow）を使用した株価予想 ～その2～ - Qiita
前回の続き。 ディープラーニングのフレームワークであるTensorFlowを使用して株価を予想するぞ～、というお話です。ちなみに前回は完全に失敗でした。 前回のコメントで、tawagoさんから「Googleが同じようなことしている」という情報をいただいたので、そちらをコピ・・・インスパイアしてみました。 ##前回との相違点 前回は、「数日分の日経平均を使用して、次の日の日経平均が上がるか、下がるか、変わらないか（3択）を予想する」ものでした。 Googleのデモでは、「数日分の世界中の株価指数（ダウ、日経平均、FTSE100、DAXなど）を使用して、次の日のS&Pが上がるか下がるか（2択）を予想する」という内容でした。 ということで、下記が前回からの主な変更点となります。 「上がるか」「下がるか」の2択 日経平均だけでなく、他国の株価指数も使用 隠れ層x2、ユニット数は50,25 予想する
大規模グラフ解析のための乱択スケッチ技法
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
非負値行列因子分解（NMF）によるレコメンドのちょっとした例 - About connecting the dots.
最近線形代数についていろいろ読みなおしたりしてるのですが（線形代数チートシートを前の記事でまとめてあります），その一環でレコメンドアルゴリズムについていくつか試してみたので，それを解説します．順序としては，基本の協調フィルタリング（ユーザベースド，アイテムベースド）→特異値分解（SVD）→非負値行列因子分解（NMF）になります． 基本的な考え方 ここで取り扱うのは，すべて以下のようなユーザ×商品のマトリックスをベースとしたレコメンドになります*1．ここでは映画レンタルサービスを例にして考えます．6人のユーザが，4つの映画*2のうちレンタル視聴したものについては，1-5点の5段階評価を行いました．0になっているものは「みていない」ということになります． まずはざっと評価の状況をみると，「千と千尋の神隠し」が最もよく視聴されていて，6人中4人がみています．次にみられているのは「となりのトトロ」
ICALP 2014 に論文採択されました - うどん記
M.Kusumoto, and Y.Yoshida . "Testing Forest-Isomorphism in the Adjacency List Model." ICALP 2014, to appear. 修論の成果で投稿した論文が国際会議のICALP2014に採択されました． ICALP(International Colloquium on Automata, Languages and Programming) は理論計算機科学(理論系アルゴリズム，計算量理論，言語・オートマトン，プログラミング言語理論など) を扱う国際会議です．運営はEATCSというヨーロッパの理論計算機科学の団体によって行われ，会議は毎年ヨーロッパの色々なところを転々としながら開催されるようです．今年はデンマークのコペンハーゲンで開催されます． ICALPは理論系アルゴリズム界隈の会議の中でも上位レベ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
500 Data Structures and Algorithms interview questions and their solutions
なめらかなシステムのアイデアと設計概要 / namerakad-idea-design
Raft
