自動微分を実装して理解する（後編） - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事はFOLIO Advent Calendar 2018、21日目の記事です。昨日はhajipionによる大規模デザインカンファレンス「デザインシップ」の着想から開会まで、超ダッシュで振り返る10ヶ月！ #Designship2018でした。 この記事は近年話題に上がることが多くなってきた自動微分を実際に実装することでより理解を深めようというものです。前回の自動微分を実装して理解する（前編）では自動微分の定義とフォワードモードの実装を見てきました。今回はリバースモードの自動微分の実装にチャレンジしてみましょう。 リバースモード 現
ダブリング - sataniC++
概要 「個次の要素を知りたい」といった状況で頻繁に用いられるテクニックです。 使える状況 「ある要素に対してその次の要素は容易に得られるが、個分次の要素を得るクエリが時間じゃ間に合わない」 というときに、ダブリングを使うことによって、全体の大きさに対して準備、クエリで求めることが出来ます。 説明 「使える状況」で述べた場面は、具体的には、 ある数の乗を求めたい 根付き木において、ある頂点vの個上の親を知りたい などです。 どちらも、次の要素（や頂点vの親）は容易に求められますね。 しかし、次の次の次の…と初めの要素から個次の要素を知るには、単純に考えると時間がかかってしまいます。 これを時間で行うことが出来るのが、ダブリングと呼ばれる手法です。 ダブリングは、次のような流れで行います。 まずは各要素における「つ次の要素」を調べておきます。 こうすることで、「「つ次の要素」のつ次の要素」、つ
動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdo
再帰関数を学ぶと、どんな世界が広がるか - Qiita
0. はじめに 再帰関数は初めて学ぶときに壁になりがちで なんとなくわかった...けれど どんな場面で使えるのだろう...いい感じの例を探したい！ という気持ちになりがちです。再帰関数は、なかなかその動きを直感的に想像することが難しいため、掴み所が無いと感じてしまいそうです。 そこで本記事では 再帰関数の動きを追いまくることで、再帰関数自体に慣れる 再帰的なアルゴリズムの実例に多数触れることで、世界を大きく広げる！ ことを目標とします。特に「再帰関数がどういうものかはわかったけど、使いどころがわからない」という方のモヤモヤ感を少しでも晴らすことができたら嬉しいです。なお本記事では、ソースコード例に用いるプログラミング言語として C++ を用いておりますが、基本的にはプログラミング言語に依存しない部分についての解説を行っています。 追記 1. 再帰関数とは 再帰の意味はとても広いです。自分自
XGBoostのお気持ちをちょっとだけ理解するためのメモ - Qiita
現在、Kaggleにてよく使われる手法の一つにGBDT(Gradient Boosting Decision Tree)があります。さらにその種類の１つXGBoostはKagglerによりその効果を検証され非常に人気の高いアルゴリズム・実装です。このブログでは、XGBoostの論文からアルゴリズムを理解するための主要な部分、 TREE BOOSTING IN A NUTSHELL 2.1 Regularized Learning Objective 2.2 Gradient Tree Boosting を丁寧に解説することを目的に書いています。 また、ここで解説した理論、アルゴリズムについてはLightGBMにおいてもほぼ同じと思いますので、合わせて参考になるかと思います。 おことわり しかしながら、最初におことわりをさせていただくのですが、markdownやtexでキレイにまとめる余裕が
高速な比較安定ソートアルゴリズム「颯式」の紹介（ベンチマークあり） - Qiita
颯式（はやてしき）は、「クイックソート種より高速」を目指した、マージソートの改良アルゴリズムです。 以下の特徴があります。 比較ソート 安定ソート 外部領域：N 最良：O(N) 平均：O(N log N) 最悪：O(N log N) 再帰：無し リポジトリ 颯式（はやてしき） MIT License 基本となるアルゴリズム 外部領域を、2Nの連続帯として見立てます。 値を外部領域に置く際、以下のルールを適用します。 （最大値 ≦ 値）であれば、昇順列の上側に置き、最大値を更新します。 （値 ＜ 最小値）であれば、降順列の下側に置き、最小値を更新します。 （最小値 ≦ 値 ＜ 最大値）であれば、新しい値（最大値であり最小値）を昇順列に置き、それまでに並べた値群をPartとします。 Part群をマージします。 具体的な流れ 外部領域を、2Nの連続帯として見立てます 4 5 1 2 7 6 3
炭焼きレストランさわやかの全店舗を巡回する近似ルートを求める - Qiita
さて、近似度の説明に戻りましょう。仮に、$X$という名前のアルゴリズムの近似度が1.5(=$X$は1.5-近似アルゴリズム)、$Y$という名前のアルゴリズムの近似度が2(=$Y$は2-近似アルゴリズム)、であるとします。先程の近似度の定義より、$X$によって出力される近似巡回ルートの合計コストは、高々、最適ルートの合計コストである42の1.5倍である61以下であるといえます。同様に、$Y$だと、高々、42の2倍である84以下であるといえます。 ここで、先程の赤色の最適ルートより無駄にコストがかかってしまう、上記の緑色の巡回ルートを考えてみると、合計コストは8+6+9+7+15+9+15=69となります。$X$は61以下の合計コストを持つ近似巡回ルートしか出力しないため、絶対に緑色の巡回ルートは出力しません。一方、$Y$は84以下の合計コストを持つ近似巡回ルートしか出力しないため、緑色の巡回
アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ - Qiita
今の場合は A さんが 31 歳の場合のストーリーでしたが、A さんが 20 歳～ 35 歳のうちのどの年齢であったとしても、似たようなストーリーで必ず 4 回の質問で当てることができます！(他の例も是非考えてみてください。) ちなみに、このような「真ん中で切ってどちらかに絞って行く」タイプのアルゴリズムには二分探索法という名前がついています。応用情報技術者試験でも頻出のテーマですので馴染みのある方も多いと思います。 1-2. つまり、アルゴリズムとは 上の年齢当てゲームという問題では、相手の年齢を当てる「方法・手順」を二分探索法に基づいて導きました。このようにアルゴリズムとは、 問題を解くための方法・手順 のことです。さて、アルゴリズムと聞くと「コンピュータ上で実装されたプログラム」のことを思い浮かべる方も多いと思いますが、必ずしもコンピュータと関係がある必要はなく、日常生活でも多々登場
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
ポケモンの外見的特徴から種族値を勾配ブースティングで予測する - Qiita
しかし、このような占有面積が小さい、かつ高い種族値合計を持つポケモンはほとんどが伝説のポケモンとなっています。 そこで、例外は存在するものの、全体としては上に挙げた画像のような傾向を持っていると仮定します。 これより、特徴を適切に捉えることで、ポケモンの外見から種族値を予測することができます。 使用するアルゴリズム -Algorithm- 今回、予測したいパラメータは以下の7種類("HP"、"攻撃"、"防御"、"特攻"、"特防"、"素早さ"、"合計")となります。 予測のおおまかな手順としては次の2ステップとなります。 勾配ブースティングを用いた個別パラメータの予測 合計値を用いた個別パラメータに対する補正 以下では、それぞれの手順についてみていきます。 勾配ブースティングを用いた個別パラメータの予測 -Prediction by Gradient Boosting- まず、はじめにそれぞ
軽い気持ちでLinkedListを使ったら休出する羽目になった話 - Qiita
ざっくり言うと リスト構造のデータに対してランダムアクセスはしちゃだめだぞ。お兄さんとの約束だ！ 発端 数年前に他部署の支援で作ったJavaのシステムに、ちょっとデカめのデータを突っ込んだらありえないほど遅いので助けてくれ、と連絡が入った。 まぁクエリとかインデックスをちょっと見れば直るっしょ・・・と鼻をほじりながら支援に向かった。 処理内容 遅い部分の処理は以下のようなものであった。 処理対象のデータをListで受け取る。 それをforループで1件ずつ前処理する。 処理結果をオブジェクトに格納し、ORマッパーでDBにINSERTする。 これだけ？ そう、これだけだ。並列処理なんて高級なことはもちろんやってない。 インフラ調査 処理中のサーバのようすを調査する。今回のインフラは典型的な3層3サーバ構成。 WEBサーバはなにもかもが余裕。 APサーバではCPUを1つ使い切っている。 14コア
実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実
わかりやすい画像のdiffを求めて - Qiita
どうも。フロントエンドエンジニアの @Quramy です。 さて、前回、1日10万枚の画像を検証するためにやったことで書いているとおり、reg-suitという画像に特化した回帰テストツールをメンテしています。 画像回帰テストという文脈において、差分の可視化方法はとても重要なファクターです。なぜなら、画像(=スナップショット)に差分が発生したからといって、それすなわち棄却、というわけではなく、その差分の内容を判断して、意図せぬ変更であれば棄却、意図した変更であればexpectedを更新する必要があります。すなわち、ワークフローに目視による差分のレビューが発生するのです。 そこで、少しだけ異なる2枚の画像について差分を効果的に可視化する、というテーマに向き合ってみました。 主にC++とOpenCVでの実装ですが、これらの知識が無くとも読めるよう、コードやAPIへの言及を少なくして、中間画像で説
ID生成大全 - Qiita
セッションIDやアクセストークン、はたまた業務上で使う一意の識別子など、いろんなところで一意のIDを生成しなきゃいけないケースが存在します。 そこで世間で使われているIDの生成方法について調べてみました。 選択基準 ID生成における要求として、以下の観点が上げられるかと思います。 生成の速度 大量にデータを短期間で処理し、それらにIDを付与する場合、ID生成そのものがボトルネックとなることがあります。 推測困難性 IDを機密情報と結びつける場合、IDを改ざんされても、機密データが見れないようにできている必要があります。 順序性 採番した順にデータをソートする必要がある場合は、IDがソートキーとして使えないといけません。 それぞれについて各生成手段を評価します。 ID生成の手段 データベースの採番テーブル 採番用のテーブルを作り、そこで番号をUPDATEしながら取得していくやりかたです。古い
機は熟した！グラフ構造に対するDeep Learning、Graph Convolutionのご紹介 - ABEJA Tech Blog
はじめまして。ABEJAでResearcherをやらせていただいている白川です。 先日、化合物の物性推定をDeep Learningをつかって従来手法より300,000倍高速に処理するという論文がでました（[1], [2]）。この論文の手法は、Graph Convolutionというグラフ上に定義されたConvolution演算がベースとなっています。物性推定に限らず、グラフ解析全般を Deep Learning で上手にこなせるようになれば、Deep Learningのアプリケーションの幅がぐっと拡がり、さらなるイノベーションが起きそうな予感がします。 ICMLやNIPSなどの機械学習系の主要国際会議でも数年前からGraph Convolutionについての論文がちらほら出現しはじめており、とくに最近その勢いが増してきている印象があります。個人的にも最近（前から？）にわかにグラフづいてい
木を綺麗に描画するアルゴリズム
cvpaper.challengeはコンピュータビジョン分野の今を映し、トレンドを創り出す挑戦です。論文サマリ・アイディア考案・議論・実装・論文投稿に取り組み、凡ゆる知識を共有しています。 http://xpaperchallenge.org/cv/ 本資料はxpaper.challengeの2020年末ワークショップとしてプレゼンした、研究効率化Tipsです。10研究室、200ページ超にわたるノウハウ詰め合わせです。
【やってみた】リーマン多様体へのグラフ描画アルゴリズムの実装【実装してみた】
第二回 Deep Learning Acceleration 勉強会（DLAccel #2） での発表資料 https://idein.connpass.com/event/139074/ 高速化技術を下記の6観点で紹介 - 畳み込みの分解 (Factorization) - 枝刈り (Pruning) - アーキテクチャ探索 (Neural Architecture Search; NAS) - 早期終了、動的計算グラフ�(Early Termination, Dynamic Computation Graph) - 蒸留 (Distillation) - 量子化 (Quantization)
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
自動微分を実装して理解する（前編） - Qiita
https://akagi.jp/works/akagi-mthesis.pdf
グラフ探索アルゴリズム - Qiita Advent Calendar 2015 - Qiita
