IBIS 2023 企画セッション『最適輸送』 https://ibisml.org/ibis2023/os/#os3 で発表した内容です。 講演概要: 最適輸送が機械学習コミュニティーで人気を博している要因として、最適輸送には微分可能な変種が存在することが挙げられる。微分可能な最適輸送は様々な機械学習モデルに構成要素として簡単に組み入れることができる点が便利である。本講演では、最適輸送の微分可能な変種とその求め方であるシンクホーンアルゴリズムを紹介する。また、この考え方を応用し、ソーティングなどの操作や他の最適化問題を微分可能にする方法を紹介するとともに、これらの微分可能な操作が機械学習においてどのように役立つかを議論する。 シンクホーンアルゴリズムのソースコード：https://colab.research.google.com/drive/1RrQhsS52B-Q8ZvBeo57vK

レイトレ合宿９(*)のセミナー発表スライドです。 * https://sites.google.com/view/rtcamp9/home - 2023/09/08 “除算法2”追記。（@Reputelessさんありがとうございました）

リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit

はじめに 年末に Twitter でこのツイートを見かけました。 もともとアルゴリズムの勉強に興味があり、一年ほど前に数ヶ月だけ AtCoder をやっていましたが、途中で挫折してしまった自分にとって、NeetCodeの勉強ロードマップは非常に魅力的に感じました。（転職意欲があったわけではないです） NeetCode のロードマップ そこで、このロードマップに従って LeetCode の問題を 150 問解くことを決意し、結果的におよそ1ヶ月半で全ての問題を解き切ることができました。 この過程で、様々なことを学ぶことができました。中には自分が予想していなかった学びも多くありましたので、同じくアルゴリズムに興味のあるエンジニアの方に役立てていただけるよう、記録として残しておきます。 ハードスキル 📗 データ構造への理解 頻出するデータ構造について、それぞれの長所/短所を理解し、主要な処理の

巡回セールスマン問題 巡回セールスマン問題(以下TSP)についてご存知でしょうか。 完全グラフと全ての辺の移動コストが与えられた上で、全ての点を１回ずつ通り、始点に戻る巡回路の中で総移動コストが最小となる巡回路を求める組合せ最適化の問題です。 今回の記事の趣旨とは異なるため、ソルバーの詳細及びTSPを解くアルゴリズムの紹介は他の文献に譲ります。(個人的には辺の移動コストが定数でないTSP (dynamic TSP)にも興味があるので追ってまとめたいと思います。実応用としては、渋滞が発生して移動時間が変わる等の状況を考慮することに相当します。) TSPの応用としてはその名についているように人が全ての与えられた場所の集合を回る、郵便物などの配送*やテーマパークで回る順番を考える問題が多いかと思いますが、それらの実空間で何かの対象物が移動する以外の面白いなと思った応用例について３つ紹介して行きた

アプリケーションなどOSより上に作られる高水準のプログラムではハードウェアの速度と容量を考慮しない数学的キャッシュアルゴリズムが使われ主にこれを本稿の対象とする。キー探索用マップと明示的キャッシュサイズ(対となる値が保持されているキーのサイズ)は計算量に含まれない。 LRU 最も単純かつ高性能な基礎的キャッシュアルゴリズム。そのため性能比較のベースラインとして常に使用される。逆に言えば実用最低水準の性能である。スキャン耐性皆無でスキャン一発でキャッシュとヒット率がリセットされゼロからやり直しになるため非常に脆く不確実な性能となりベンチマークにおける性能が表面上さほど悪くなく見えても実際の性能はこのような外乱により大きく低下しやすい。このためLRUより高度な主要アルゴリズムはすべて大なり小なりスキャン耐性を備えている。ちなみにプログラミング言語最大のパッケージマネージャであるJavaScri

At Spotify we take user feedback seriously. We noticed some users complaining about our shuffling algorithm playing a few songs from the same artist right after each other. The users were asking “Why isn’t your shuffling random?”. We responded “Hey! Our shuffling is random!” So who was right? As it turns out, both we and the users were right but it’s a bit more complicated than that. It also tells