タグ

関連タグで絞り込む (0)

  • 関連タグはありません

タグの絞り込みを解除

Algorithmとalgorithmとmathに関するmanabouのブックマーク (65)

  • ブラックホール撮影にも使える「スパースモデリング」とは?【機械学習】 - ざるご博士になりたいブログ

    この記事は移転しました。約2秒後に新記事へ移動します。移動しない場合はココをクリックしてください。 どうもざるご(@zalgo3)です. 世界初のブラックホール撮影の成功例が出たようです. ブラックホールの撮影に成功 世界初 一般相対性理論を証明 - 毎日新聞 今回のブラックホール撮影は,スパースモデリングという機械学習技術を取り入れたことによる貢献が大きいようです. 天文学に計算機科学の知識が取り入れられて,大きな成果が出たというのは,驚くべきことだと思います. 今回はそんな大成功を巻き起こした「スパースモデリング」について解説していきます. スパースモデリングとは スパースモデリングとは,誤解を恐れずにざっくりいうと解けない連立一次方程式を無理やり解くための仕組みです. 次のような連立一次方程式を考えます. この方程式は,が逆行列を持つときに解くことができて, となります.では,が逆行

    ブラックホール撮影にも使える「スパースモデリング」とは?【機械学習】 - ざるご博士になりたいブログ
  • プログラミングできる人とできない人との間の深い溝 - masatoi’s blog

    どうしてプログラマに・・・プログラムが書けないのか?を読んでいて出てきたので出展の一つを訳してみた。Separating Programming Sheep from Non-Programming Goatsの和訳。 プログラミングというものには向き不向きが強く出るということはわりと知られていると思うが、このエントリではプログラミングができるかできないかは比較的簡単なテストによって、プログラミングの訓練を始める前の段階で分かると主張している。どうしてプログラマに・・・プログラムが書けないのか?では、そもそもこの事前テストをパスしていないような人達までプログラマとして応募してくると言っており、その判定法として有名なFizzBuzz問題を挙げている。 追記(2019/2/28) 注意: なおこの論文はしばらく前に著者の一人によって撤回されたようです Camels and humps: a r

    プログラミングできる人とできない人との間の深い溝 - masatoi’s blog
  • 計算量オーダーの求め方を総整理! 〜 どこから log が出て来るか 〜 - Qiita

    NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ~ 文系理系問わず楽しめる精選 6 問 ~ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると

    計算量オーダーの求め方を総整理! 〜 どこから log が出て来るか 〜 - Qiita
  • 双対性

    最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。

    双対性
  • 線形回帰を1つ1つ改造して変分オートエンコーダ(VAE)を作る - 作って遊ぶ機械学習。

    こんばんは. 今日は統計や機械学習において最も基となる手法である線形回帰から出発し,1つ1つモデルや学習方法に変更を加えていき,最終的に深層学習の分野で非常に良く使われている生成モデルである変分オートエンコーダ(variational auto-encoder,VAE)*1*2を導いていきたいと思います. 2014年に発表されたVAEは,勾配近似を得るためのreparametrization trickや,効率的に潜在変数を近似推論する認識モデル(recognition model, inference model)の導入,確率的勾配法(stochastic gradient descent,SGD)の2重適用など,様々なアイデアが散りばめられている確率的生成モデルです.背景としては,当時ニューラルネットワークを用いて画像を生成するといったアプローチが(CNNを使った識別などと比べて)そ

    線形回帰を1つ1つ改造して変分オートエンコーダ(VAE)を作る - 作って遊ぶ機械学習。
  • エレガントな解法、エレファントな解法 〜モンテカルロ法を添えて〜|山本一成🚗TURING

    問 コインを100回投げて、表か裏が10回連続で出る確率は? 皆さんこの問題解けますでしょうか?私は正直解ける気がしません。そもそも何%くらいなのかすら、うまく推測できません。今日は、しかし皆さんには全然別の方法論を共有できればと思います。 その方法論とはずばり実際に投げてみましょう。「コインを100回投げて、表か裏が10回連続で出るかどうか」を100回あるいは1000回くらい試行してみたらそれなりに正しい確率が出ると思いませんか?実際にでます。 でもいくらなんでも現実にするのはつらいですよね。そこでせっかくなのでコンピュータに投げさせましょう。といっても実際に投げるのではなく、コンピュータの中で乱数(ランダム)を発生させて、それで投げていることにしましょう。プログラムで書くとこんな感じです。 コインを100回投げて、表か裏が10回連続で出るかどうか調べるプログラム。試行回数が増えるほどに

    エレガントな解法、エレファントな解法 〜モンテカルロ法を添えて〜|山本一成🚗TURING
  • x + 0.25 - 0.25 = xが成り立たないxとは何か|Rui Ueyama

    スタンフォードのコンピュータサイエンスの授業で、ときどきこれは良問と思う問題がテストで出ることがある。僕の印象に残っているのは「xをfloatとするとき、x + 0.25 - 0.25 = xが成り立たないxを求めよ」というものだ。浮動小数点数を理解していないと、両辺が同じにならないケースがあるほうが不自然に思えるだろうから、この問題は浮動小数点数の奇妙さを結構うまく突いていると思う。この問題を元に浮動小数点数についてちょっと説明してみよう。 まずコンピュータ上での数について少し考えてみよう。コンピュータにおける数と、数学の整数や実数は、よく考えてみると全然違う。コンピュータは有限の記憶領域しか持っていないので、無数にある数を表すことが根的にできない。つまりコンピュータ上の数は「物の数になるべく似せた別の何か」だ。現実的には、例えば32ビットの数なら2^32パターンしか表せないので、そ

    x + 0.25 - 0.25 = xが成り立たないxとは何か|Rui Ueyama
  • 画像処理の数式を見て石になった時のための、金の針 - Qiita

    $k$は定数で、だいたい0.04~0.06くらいです。Rの値によって以下のように分類できます。 Rが大きい: corner Rが小さい: flat R < 0: edge 図にすると、以下のようになります。 CSE/EE486 Computer Vision I, Lecture 06, Corner Detection, p22 これで手早くcornerを検出できるようになりました。ここで、corner検出についてまとめておきます。 cornerは複数のedgeが集まる箇所と定義できる 変化量をまとめた行列の固有ベクトルからedgeの向き、固有値の大きさから変化量の大きさ(edgeらしさ)がわかる 2つの固有値の値を基に、edge、corner、flatを判定できる 固有値の計算は手間であるため、判定式を利用し計算を簡略化する なお、Harrisはedgeの向きである固有ベクトルを考慮す

    画像処理の数式を見て石になった時のための、金の針 - Qiita
  • イプシロン-デルタ論法はなぜ難しいのか? どうしたら分かるのか? 分かる必要があるのか? - 檜山正幸のキマイラ飼育記 (はてなBlog)

    先週末に、N君が「イプシロン-デルタ論法って、なんすかアレ? 全然分からないっす!」と言ってました。そのときはそれ以上話す時間もなかったし、次回会うときはこの話題を忘れてしまうかも知れないので、書き記しておきます。 僕は、伝統的なイプシロン-デルタ論法そのものには懐疑的です*1。ゴタゴタした不等式をいじり回すのは早々に切り上げて、開集合を導入したほうがいいと思います。そんな思いから、出来るだけ不等式を使わずに集合族に注目するスタイルでイプシロン-デルタ論法を紹介します。 内容: イプシロン-デルタ論法 時間や運動のイメージを捨て去る ユークリッド距離と開球体 扱う関数達と実例 平面から平面への写像 一点の周辺を記述する開球体の族 写像による開球体の像 デュエルゲームとしての連続性 論理式で書き下そう 再びイプシロン-デルタ論法 続編: 距離空間と位相空間と連続写像 イプシロン-デルタ論法

    イプシロン-デルタ論法はなぜ難しいのか? どうしたら分かるのか? 分かる必要があるのか? - 檜山正幸のキマイラ飼育記 (はてなBlog)
  • quadpack

  • 自動微分の基礎| GRC/ARCA Viewpoint | PwCあらた有限責任監査法人

    自動微分(Automatic Differentiationあるいは Algorithmic Differentiationともいわれ、ADと略される場合が多い)とは、コンピュータープログラムで表現された関数を効率的かつ正確に計算する技術です。 もともとは流体力学、原子核工学、気象科学などで使用されていた手法ですが、近年機械学習や金融への応用が注目されています。そこでここでは、自動微分の基礎について紹介します。 1. 数値微分 関数の微分係数を求めたい場合、数式がわかっていれば、数学的にはその関数式を微分すれば求まります。しかし、コンピュータープログラムで使用される関数は、何段階にも入れ子になっていたり、ループや条件分岐を含むコードにより表現されているため、数学的に微分することは必ずしも簡単ではありません。 しかし、そもそも微分の定義を考えると、

    自動微分の基礎| GRC/ARCA Viewpoint | PwCあらた有限責任監査法人
  • Linear algebra cheat sheet for deep learning

    During Jeremy Howard’s excellent deep learning course I realized I was a little rusty on the prerequisites and my fuzziness was impacting my ability to understand concepts like backpropagation. I decided to put together a few wiki pages on these topics to improve my understanding. Here is a very basic intro to some of the more common linear algebra operations used in deep learning. NEW: check out

    Linear algebra cheat sheet for deep learning
  • 機械学習エンジニアが知るべき10のアルゴリズム

    前回の投稿から大分時間が空いてしまいましたが、現在マーケティング部では、データサイエンスに関する知識を深めるために海外のデータサイエンス記事を翻訳するという取り組みを行っています。主に、KDnuggetsというサイトで紹介されている記事で人気のあるものを中心に選び、原著者より翻訳の許諾をいただけた記事を公開しております。不定期ですが、データサイエンスに関心のある皆様により良い情報を日語でお届けできるように取り組んで参ります。 初回に取り上げたい記事はJames Le氏の「The 10 Algorithms Machine Learning Engineers Need to Know」です。機械学習の手法が網羅的に紹介されており、実用例も示されています。初めて機械学習に取り組む方のご参考になれば幸いです。 SOURCE https://gab41.lab41.org/the-10-alg

    機械学習エンジニアが知るべき10のアルゴリズム
  • 円周率の16進数表現100億桁目を求めてみた! ― 円周率の世界記録をどのように検証するか ― - プログラムモグモグ

    あなたは円周率を何桁言えますか。3.14159…という、あの数字です。 円周率の小数部分は無限に続き、循環することもありません。 古来より、数学者は円周率の値を様々な幾何学的な近似や公式を用いて計算してきました。 その桁数は計算機の発明により飛躍的に伸び、収束の速い公式の発見や効率の良いアルゴリズムの発明などによって加速してきました *1。 5年前、私がまだ学生だった頃、円周率1億桁の計算に挑んだことがありました。 私にとって高精度計算の初めての挑戦で、様々な試行錯誤で苦労したのをよく覚えています。 itchyny.hatenablog.com 2017年現在、円周率計算の世界記録は22兆桁です。 円周率計算の歴史をご覧いただくとよく分かると思いますが、近年の円周率計算の世界記録からは次のような特徴が読み取れます。 2002年に1兆を超え、最新の記録 (2016年) は22兆桁 (10進数

    円周率の16進数表現100億桁目を求めてみた! ― 円周率の世界記録をどのように検証するか ― - プログラムモグモグ
  • 中置記法の数式文字列から計算結果を求める操車場アルゴリズム - $shibayu36->blog;

    最近 Algorithms, Part I | Coursera の社内勉強会を開いている。そこで「Stacks and Queues」という章をみんなで学習し、議論したところ、中置記法の数式文字列から計算結果を求める操車場アルゴリズム(Shunting-yard algorithm)というものがあるということを知った。 操車場アルゴリズムというのは、中置記法の数式文字列から計算結果を求めるというようなことができるアルゴリズム。オペレータスタックと値スタックの二つがあるだけでトークンを一つずつ読みつつその都度計算するだけで計算結果を求めることができる。パースして構文木を作るというフローを取ることなく計算ができるというのが面白い。このアルゴリズムの説明は Wikipediaの操車場アルゴリズム - Wikipedia の説明が非常に分かりやすい。 このアルゴリズムを使うことで、例えば以下のよ

    中置記法の数式文字列から計算結果を求める操車場アルゴリズム - $shibayu36->blog;
  • 数値最適化のインタラクティブ・チュートリアル | POSTD

    「数値最適化」は機械学習における中心的手法の1つです。多くの問題では、最適解を直接突き止めることは難しいものですが、ある解がどれほど適しているかを測定する損失関数を設定し、解を見つけるためにその関数のパラメータを最小化することは比較的容易です。 かつてJavaScriptを初めて学ぼうとしていた時 、結果的に数値最適化ルーチンを多数書きました。そのコードを特に使うこともなく置いていたので、それらのアルゴリズムの動作をインタラクティブな形で可視化したら面白いのではないかと考えました。 記事の良い点は、コードが全てブラウザで実行できることです。つまり、アルゴリズムの動作をより把握するために、各アルゴリズムのハイパーパラメータをインタラクティブにセットしたり、初期位置を変更したり、どの関数が呼び出されるかを変更したりすることができるのです。 (編注:記事ではスクリーンショットのみ公開しており

    数値最適化のインタラクティブ・チュートリアル | POSTD
  • 確率的プログラミング | POSTD

    この数年で、プログラミング言語(PL)や機械学習のコミュニティは 確率的プログラミング(PP) を用いて、それぞれに共通する研究の関心事を明らかにしてきました。その概念は、抽象化のような強力なPLのコンセプトを”エクスポート”し、現状では複雑で困難な作業である統計的モデリングに再利用することができるかもしれない、というところにあります。 (講義ノートの 最新版 を閲覧したい方は、リンクをクリックしてください。ソースは GitHub に投稿してあります。誤りを発見した場合は、Pull Requestを送信してください。) 1. 何、そしてなぜ 1.1. 確率的プログラミングは○○○ではない 直観に反して、確率的プログラミングとは確率的に振る舞うソフトウェアを書くことでは ありません。 例えば、暗号のキー・ジェネレータやOSカーネルでの ASLR の実装、または回路設計のための 焼きなまし法

    確率的プログラミング | POSTD
  • グラフ代数 | POSTD

    数学や計算幾科学の分野において、 グラフ理論 は私のお気に入りのテーマです。この記事では、私が長年研究している グラフ代数 についてご紹介します。代数学は私にとって、グラフを扱う上で欠かせないツールになっています。皆さんにも、その便利さが伝われば幸いです。 私がグラフ代数の研究を始めたきっかけは、CONCUR 09という学会向けに提出した論文です。その論文は不採録でしたが、私はその後も特定用途向けのいくつかの論文を発表し、代数学の知識を深めていきました。その全容が記載された論文は、 ACM TECS でご確認いただけます(査読前の原稿は こちら です)。では早速、最もシンプルなグラフ代数の概要と、Haskellでの実装方法を紹介します。 グラフの作成 ここでは、固定領域に存在する頂点を持つ一式のグラフをGと表記します。例として、正整数の頂点を持つグラフについて考えてみましょう。グラフg ∈

    グラフ代数 | POSTD
  • 複素数演算による幾何ライブラリの実装 - ヘクトのメモ

    この記事はMCC Advent Calendar 2016 15日目の記事です.ICPC向けの複素数演算による幾何ライブラリの実装について話します. MCC Advent Calendar 2016 - Adventar 遅れてすいません... 背景 ICPCでは幾何の問題が出てきます. ただし,ICPCでは電子的な事前準備の禁止と標準ライブラリしか使えない制約があります. このため,標準ライブラリ縛りで幾何に必要な関数を一から実装する必要があります. しかし,事前準備なしで幾何に必要な関数を実装するのは大変なことであり,多くのチームは紙媒体でライブラリを用意していると思います. 幾何に必要な関数を一から実装するとコード量も膨大になりがちです. そこで,複素数演算を活用することで実装量を減らすことができます. (ただし,2D限定です.あと,事実だけを淡々と書いていきます.) ベクトル 2次

    複素数演算による幾何ライブラリの実装 - ヘクトのメモ
  • 力づく法・分割統治法・動的計画法 - アルゴリズム学習(その5) - $shibayu36->blog;

    アルゴリズムの設計手法として、力ずく法・分割統治法・動的計画法というような考え方があった。新しいアルゴリズムを学ぶ時、どの設計手法でやっているのだろうかと意識しておくと、頭に入りやすい気がした。そこで、自分の頭を整理するためにメモを書いておく。自分用メモなので、情報の正確さについては保証がない。 力づく法 全探索する方法 アルゴリズムの考え方としては単純なことが多いが、かなり遅いものになることが多い 例えば、Nクイーンなら、N個の置き方を全通り作って、それぞれが条件をみたすか確認し、条件を満たしたら返すようなもの。Nの二乗のなかから、N個の組み合わせを作って試すので、計算が膨大になる 例えば文字列マッチなら、1文字ずつずらしながら、マッチさせたいパターンとテキストの文字を比較していくようなもの 分割統治法 Wikipediaによると、そのままでは解決できない大きな問題を小さな問題に分割し、

    力づく法・分割統治法・動的計画法 - アルゴリズム学習(その5) - $shibayu36->blog;