金子勇さんのED法を実装してMNISTを学習させてみた - Qiita
追記：続きを書きました。 はじめに 先日以下の記事が投稿され、その斬新な考え方に個人的ながら衝撃を受けました。 内容をざっくり言うと、ニューラルネットワークの学習を現在の主流であるBP法（誤差逆伝播法）ではなく、ED法（誤差拡散法）という新しい学習手法を提案しているものです。 もし記事の内容が本当ならニューラルネットワークの学習がO(1)でできてしまう事になり、まさしく革命が起きてしまいます。 （結論からいうと速度面はそこまででもなかったです（それでも早くなる可能性あり）） （ただこの新手法のポテンシャルは革命を起こす可能性は秘めているといっても過言ではありません） ED法に関してネットを探すとインターネットアーカイブに情報が少し残っていました。 このページですがED法のサンプルプログラム（C言語）が残っており、このサンプルプログラムをベースにpythonで書き起こしたものが本記事となりま
『Winny』の金子勇さんの失われたED法を求めて - Qiita
普段は「通知が迷惑かなー」と思ってブックマークしていただいている方に通知せず記事を編集しているのですが、この記事をブクマしていただいている方は続きが気になっている方だと思いますので通知させていただきます。 結論から言うと、この記事を読んだ @pocokhc (ちぃがぅ)さんという方が金子勇さんが書いたED法のサンプルプログラムを見つけてくださいました。 ちぃがぅさんの記事はこちら 自分で解明したかったという気持ちも無いことは無いですが、バズった時点で誰かが実装してくれそうな気はしていました。新卒からIT業界に入って4年目が始まったところですが、業務以外で初めて業界にコントリビュートできた気がして嬉しいです！ 追記ついでに、謝罪します。初回公開時に記事タイトル含め本文中で何か所か「Winney」と書いてしまっていた箇所がありました。失礼いたしました。誤字修正してあります。指摘してくださった何
巡回セールスマン問題を深層学習と強化学習で解く
こんにちは！shu421と言います。 数理最適化 Advent Calendar 2023 の 12 日目です。今回は巡回セールスマン問題 (Traveling Salesman Problem: TSP) を深層学習と強化学習で解く方法を紹介します。最近の動向をざっくり追うだけなので、詳細については各論文を参考にしていただけたらと思います。 目次 巡回セールスマン問題とは 深層学習と強化学習を使う理由 論文紹介 Neural Combinatorial Optimization with Reinforcement Learning Attention, Learn to Solve Routing Problems! Solving combinatorial optimization problems over graphs with BERT-Based Deep Reinforc
Haskell の Array
Haskellのカレンダー | Advent Calendar 2023 - Qiita 3日目の記事です。 Haskell の Array (配列) について書こうと思います。Haskell の Array は索引が型クラスの Ix で抽象化されているため、特に配列の次元を拡張する際に柔軟性がありとても便利です。 そんな便利な Array ですが、もともと Haskell はリスト操作が強力ということもあってか、既存の参考書をみても Array の解説はほんの少しにとどまっているか、解説がないことがほとんどです。 Array が必要になる場面の多くは「リストだと !! によるインデックスアクセスで O(n) になってしまい間に合わない」という場面が多いと思います。しかし Haskell にはインデックスアクセスが O(1) の Vector (vector: Efficient Arra
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
半開区間の魅力 〜プログラミングでのスマートな区間の扱い方〜 - Qiita
はじめに こんにちは、kenです。 今回は「プログラミングで区間を扱いたいときは半開区間が良いよ」という話をします。 もしかしたら有名な事実かもしれませんが、友達にこの話をしたら知らなかったという顔をされたので、自分の理解を深めるためにも記事にすることにしました。 数学で区間を扱う際は実数上で考えることが多いかと思いますが、この記事では区間を考える際、整数全体の集合上での区間を考えることにします。 また以下ではleft（またはl）とright（またはr）という文字式を使って説明しますが、このときleft $ \leq $ rightという関係性は常に満たされているものとします。 半開区間とは？ 半開区間の前に、開区間と閉区間についておさらいしておきます。 開区間は(left,right)のように表され、両端点を含まないleftからrightまでの区間を表します。 一方で閉区間は[left,
Haskell で、優先度付きキューを使ったダイクストラ法
Haskellのカレンダー | Advent Calendar 2022 - Qiita に参加させていただきます! 突然ですが Haskell でダイクストラ法を実装します。 ダイクストラ法は重み付きグラフで最短経路問題を解くアルゴリズムのひとつです。ダイクストラ法 - Wikipedia に詳しい解説があります。 ダイクストラ法は、重み付きグラフにおいて、その重みに負の値がない･･･つまり重みが正であることを前提にしています。この構造上の仮定によって、貪欲的手法を取ることができるのがその特徴で、結果ベルマン・フォード法などの汎用的なアルゴリズムよりも計算量的に有利になります。 ダイクストラ法では、始点から各頂点への到達コストを最初に \infty と置いて、そこから緩和操作によって徐々にそれらを最適コストまで収束させていくわけですが、このとき グラフの頂点集合からその時点で最小のコスト
Linux 6.1の注目機能「MGLRU」―メモリ管理に取り入れられたエイジングシステム | gihyo.jp
Linus Torvaldsは12月11日（米国時間）、前週の告知どおりに「Linux 6.1」の正式リリースをアナウンスした。 Linux 6.1 -Linus Torvalds Linux 6.1はメインライン開発ではじめてRustを採用したことが大きな話題となったが、そのほかにもユーザ空間におけるメモリサニタイザーツールに似た動的エラー検出の「KMSAN」やB-treeベースのデータ構造「Maple Tree」、AMDの新しいPMFドライバのサポートなど多くのアップデートが行われている。Googleの開発者がメインラインへのマージを提案してきた「MGLRU（Multi-generational LRU）」もそのひとつで、古参のカーネル開発者であるAndrew MortonもMGLRUのメインライン化をバックアップしてきた。 Linuxカーネルではメモリ管理に「LRU（Le
The Algorithms
What is an Algorithm?An algorithm is a set of rules that takes in one or more inputs, then performs inner calculations and data manipulations and returns an output or a set of outputs. In short, algorithms make life easy. From complex data manipulations and hashes, to simple arithmetic, algorithms follow a set of steps to produce a useful result. One example of an algorithm would be a simple funct
型安全で高速な連鎖行列積の計算
この記事は Haskell Advent Calendar 2021 の22日目の記事です。 次のような３つの行列の積を考えてみましょう。 ABC = \begin{pmatrix} a_{00} & a_{01} & a_{02} \\ a_{10} & a_{11} & a_{12} \\ a_{20} & a_{21} & a_{22} \\ a_{30} & a_{31} & a_{32} \\ \end{pmatrix} \begin{pmatrix} b_{00} & b_{01} \\ b_{10} & b_{11} \\ b_{20} & b_{21} \\ \end{pmatrix} \begin{pmatrix} c_{00} & c_{01} & c_{02} & c_{03} & c_{04} \\ c_{10} & c_{11} & c_{12} & c_{13}
アルゴリズム設計に欠かせない問題解決のための「還元」 with Clojure - Qiita
システムエンジニアやプログラマーは、問題解決に取り組むことが主な仕事ですが、 直面する問題解決に取り組む中で、過去に似たような問題に出会っていたことに気が付くことがよくあると思います。 この記事では、問題を別の問題に置き換えて考えることを言語化した、計算理論の世界の「還元」という概念を紹介しようと思います。 紹介の中で使うコードは、今の仕事で使っているClojureで書きました。(Clojureがわからなくても内容は理解できると思います) また、個人的な解釈を含むので、誤っている場合があります。個人的な解釈については、「～ていそうです」「～と思いました」「～な気がします」みたいな表現になっています。 1. 還元(reduce) 還元(reduce)とは、ある計算問題Aを別の計算問題Bに変換することです。 問題解決においては、 「この問題(A)って要はあの問題(B)なのでは？」 「あの問題(
SSA変換とSCCP最適化をJavaScriptで実装してみた。 - Qiita
はじめに このプロジェクトはSSA変換およびSCCP最適化(スパース条件付き定数伝播最適化)をJavaScriptで実装してみたものです。 SSA変換はコードフローグラフを破壊的な変数(レジスタ)を無くして非破壊的なレジスタとファイ関数によって構成するようにしたSSA形式に変換する処理です。 SCCP最適化は、常に固定値に評価されるプログラム内の変数と式を検出し、実行時ではなくコンパイル時にそれらの値を計算する最適化処理です。 今回は非常にやる気がなくてですね、いい加減な文章になっていることを先にお詫び申し上げておきます。[静的単一代入（SSA）形式][SSA] に依存して分析の効率を向上させ（スパース）、実行されない制御フローエッジを検出する機能により、従来の定数伝播とは一線を画しています。一定の分岐条件（条件付き）によれるかもしれないけど。みたいな英語を機械翻訳しただけのものをちゃんと
できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
Python言語による実務で使える100+の最適化問題 | opt100
指針 厳密解法に対しては、解ける問題例の規模の指針を与える。数理最適化ソルバーを使う場合には、Gurobi かmypulpを用い、それぞれの限界を調べる。動的最適化の場合には、メモリの限界について調べる。 近似解法に対しては、近似誤差の指針を与える。 複数の定式化を示し、どの定式化が実務的に良いかの指針を示す。 出来るだけベンチマーク問題例を用いる。OR-Libraryなどから問題例をダウンロードし、ディレクトリごとに保管しておく。 解説ビデオもYoutubeで公開する． 主要な問題に対してはアプリを作ってデモをする． 以下，デモビデオ： 注意 基本的には，コードも公開するが， github自体はプライベート そのうち本にするかもしれない（予約はしているが， 保証はない）． プロジェクトに参加したい人は，以下の技量が必要（github, nbdev, poetry, gurobi); ペー
グラフ描画アルゴリズムとNetworkxの裏側 - Qiita
0.グラフの描画ってどうやるの？ 二次元に描画するためには各頂点に適切に座標を与える必要がありますが、グラフは頂点と辺の情報しか持っていません。どのように頂点を配置すればよいのでしょう？？ この記事ではグラフをいい感じに配置するアルゴリズム Fruchterman-Reingold algorithm を説明します。Pythonだと networkxというライブラリで簡単に使用できます。しかし簡単すぎて悔しいので networkxの GitHub の実装を追いながら仕組みを確認していきます。 この記事の流れはこうです。 動かしてみる アルゴリズムの説明 Networkx の実装を追う 1.動かしてみる 動けば満足な方のために先に実装例を示しときます。Google colaboratory だと既にnetworkxがインストールされてるので、コピペですぐ試せます。 ランダムに配置 → ran
Bit Twiddling Hacks
By Sean Eron Anderson seander@cs.stanford.edu Individually, the code snippets here are in the public domain (unless otherwise noted) — feel free to use them however you please. The aggregate collection and descriptions are © 1997-2005 Sean Eron Anderson. The code and descriptions are distributed in the hope that they will be useful, but WITHOUT ANY WARRANTY and without even the implied warranty of
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - pubgrub-rs/pubgrub: PubGrub version solving algorithm implemented in Rust
GitHub - yorickpeterse/pattern-matching-in-rust: Pattern matching and exhaustiveness checking algorithms implemented in Rust
GitHub - keon/awesome-bits: :computer: A curated list of awesome bitwise operations and tricks
GitHub - hsk/sccp_js
