自動微分を実装して理解する（後編） - Qiita
この記事はFOLIO Advent Calendar 2018、21日目の記事です。昨日はhajipionによる大規模デザインカンファレンス「デザインシップ」の着想から開会まで、超ダッシュで振り返る10ヶ月！ #Designship2018でした。 この記事は近年話題に上がることが多くなってきた自動微分を実際に実装することでより理解を深めようというものです。前回の自動微分を実装して理解する（前編）では自動微分の定義とフォワードモードの実装を見てきました。今回はリバースモードの自動微分の実装にチャレンジしてみましょう。 リバースモード 現実世界（特に機械学習）の関数は一般的に出力の次元より入力の次元のほうが圧倒的に多いので、フォワードモードよりリバースモードの方が効率面で優れている場面が多々あります。しかし一般的なリバースモードの実装方法では数式を組み立てた順番を計算グラフとして保持する必要
ダブリング - sataniC++
概要 「個次の要素を知りたい」といった状況で頻繁に用いられるテクニックです。 使える状況 「ある要素に対してその次の要素は容易に得られるが、個分次の要素を得るクエリが時間じゃ間に合わない」 というときに、ダブリングを使うことによって、全体の大きさに対して準備、クエリで求めることが出来ます。 説明 「使える状況」で述べた場面は、具体的には、 ある数の乗を求めたい 根付き木において、ある頂点vの個上の親を知りたい などです。 どちらも、次の要素（や頂点vの親）は容易に求められますね。 しかし、次の次の次の…と初めの要素から個次の要素を知るには、単純に考えると時間がかかってしまいます。 これを時間で行うことが出来るのが、ダブリングと呼ばれる手法です。 ダブリングは、次のような流れで行います。 まずは各要素における「つ次の要素」を調べておきます。 こうすることで、「「つ次の要素」のつ次の要素」、つ
動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita
トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単
再帰関数を学ぶと、どんな世界が広がるか - 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
(2019/10/25 追記) 2019/10/19に33店舗目である、炭焼きレストランさわやか浜松遠鉄店がオープンしたため、記事を一部修正しました。 きっかけ 静岡県内のみ店舗を持つハンバーグレストランの炭焼きレストラン さわやか(以下、単にさわやかと表記する)へ行ったことがある人はわかると思いますが、以下のようなハンバーグ用のマットが敷かれたときがありました。 これは静岡県内にあるすべてのさわやかの店舗を大まかに地図で図示したマットですが、初めてさわやかに入店したとき、こんなに多くの店舗があるのかと驚いた記憶があります。しかし、当時何を思ったのか、「これ、すべてのさわやかの店舗を車で一巡すると、静岡県の一巡旅行ができるのでは？」と考えるようになってきました。されども、一時期車のガソリンが高くなったときもあるし、静岡県は無駄に東西に長い県なので、なるべく無駄に移動したくないよなぁ…なんて
アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 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
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についての論文がちらほら出現しはじめており、とくに最近その勢いが増してきている印象があります。個人的にも最近（前から？）にわかにグラフづいてい
【やってみた】リーマン多様体へのグラフ描画アルゴリズムの実装【実装してみた】
東京理科大学の「こうよう会」にて行った講演のスライドです（一部改変あり）。本スライドは、私自身が大学院博士課程へと進学する際、両親に賛同を得てもらうために、その説得に用いた資料をベースに作りました。データ等は最新のものになっていますが、概ね、当時のままです。もし、両親に進学を反対されていて、どうしても説得したいと考えている学生がおりましたら、本資料を参考に、ご自身の所属大学のデータを用いて説得してみてはいかがでしょうか？ Twitter→ @ONODA_in_Onodac Website→http://www.atsuto-onoda.com/ 補足説明：各方面からの疑問に対して補足いたします。 １．修士2年生は親への説得は必要か？ 親子関係は人それぞれですが、私の場合は親に納得してもらい、後顧の憂いなく博士課程で研究に没頭したかったので、説明しました。またプレゼンスライドはあくまでも「今
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
自動微分を実装して理解する（前編） - Qiita
https://akagi.jp/works/akagi-mthesis.pdf
グラフ探索アルゴリズムのカレンダー | Advent Calendar 2015 - Qiita
木を綺麗に描画するアルゴリズム
