披露宴の席次を Gromov-Wasserstein 最適輸送で決めた話
数理最適化 Advent Calendar 2022の9日目です。 新緑の頃、新型コロナ流行の合間をぬって、ささやかな結婚披露宴を表参道の式場にて催しました。諸々の準備の中でも席次はこだわるとキリがなく、数理最適化を使って決めました。人間関係をできるだけ保つようなゲスト集合から座席集合への写像を考えます。 ゲスト間人間関係を考慮して良い感じの配席を考えたい tl;dr 披露宴をしました 知り合い関係が複雑かつ長机でゲストの席配置が難しい 組合せ爆発は本物。高々20人の配置に1週間以上悩んだ結果、数理最適化した方が早いと結論 「知り合い同士を近くに配席する」問題は非凸な二次計画になり汎用ソルバでうまく解けない ゲストを席に"輸送"すると考えて最適輸送の一種で解くとうまくいった 本質的に非凸な問題を非凸のまま、しかし性質の良い距離構造を活用するアプローチが奏功したのではないか 再現用Colab
アルゴリズムの世界地図 - Qiita
こんにちは、square1001 です。 現在は東京大学の学部 1 年生をしています。私は中学 1 年の頃からプログラミングをやっていて、特にアルゴリズムが大好きです。AtCoder をはじめとする 競技プログラミング にも取り組んでいて、中高生のときは 情報オリンピック にも参加していました。 本記事では、アルゴリズムや競技プログラミングに興味がある方、あるいはプログラミングをやっているけどアルゴリズムをよく知らない方に アルゴリズムはどんなもので アルゴリズムを使うとどんな問題が解けて アルゴリズムが地球のように広く、多様で、奥深く、そして楽しいこと を知ってもらおうと思っています。 アルゴリズムの世界へようこそ 時代は 2020 年代に突入し、急速に IT 化 や DX が進んでいく中で、問題を効率的に解くアルゴリズム技術の重要性が、ますます高まっています。そして、アルゴリズムは、世
最適輸送の解き方
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
EMアルゴリズム徹底解説 - Qiita
ステップ2 $r_{nk}$を固定して$J$を$\mu_k$で偏微分して最小化します。 式変形をすると、 クラスタ$k$の最適なCentroidは上記のように、クラスター$k$に所属しているデータの平均であることがわかりました。 上記より最初のデモンストレーションで行っていたアルゴリズムは損失関数$J$の最適化によって導出されたものを適用していたことがわかります。 2−3. 実装 上記で示した２ステップを計算して、イテレーションを回すだけのシンプルなプログラムです。最後に更新前のmuと更新後のmuの差を取り、それがある程度小さくなったら収束したと判断し、イテレーションを止めるようにしています。 下記はアルゴリズム部分の抜粋です。プログラムの全文はコチラにあります。 for _iter in range(100): # Step 1 =============================
Knuth multiplicative hash が最小完全ハッシュ関数であることの証明 | メルカリエンジニアリング
こんにちは！サーチチームの @metal_unk です。普段はサーバーサイドエンジニアとして、メルカリの検索を改善する仕事をしています。 メルカリには Be Professional Day という「普段できないことをやろう」をテーマとする日があり、その日は業務に直接関係のないことや、普段は手をつけられないリファクタリングなどがされます。Be Professional Day の様子はこちらで紹介されています。 tech.mercari.com わたしは今回の Be Professional Day で、Knuth multiplicative hash が最小完全ハッシュであることを証明しました。このブログはその証明についての記事です。 「普段できないことをやろう」という Be Professional Day では、証明もアリです。 Knuth multiplicative hash
古くて新しい自動迷路生成アルゴリズム - やねうらおブログ(移転しました)
最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。 メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。 なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである。 この迷路を見て「ああ、俺様も迷路のことを書かねば！俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば！」と誰も求めちゃいない使命感が
統計的機械学習入門
統計的機械学習入門(under construction) 機械学習の歴史ppt pdf 歴史以前 人工知能の時代 実用化の時代 導入ppt pdf 情報の変換過程のモデル化 ベイズ統計の意義 識別モデルと生成モデル 次元の呪い 損失関数, bias, variance, noise データの性質 数学のおさらいppt pdf 線形代数学で役立つ公式 確率分布 情報理論の諸概念 (KL-divergenceなど) 線形回帰と識別ppt pdf 線形回帰 正規方程式 正規化項の導入 線形識別 パーセプトロン カーネル法ppt pdf 線形識別の一般化 カーネルの構築法 最大マージン分類器 ソフトマージンの分類器 SVMによる回帰モデル SVM実装上の工夫 クラスタリングppt pdf 距離の定義 階層型クラスタリング K-means モデル推定ppt pdf 潜在変数のあるモデル EMアル
行列分解ライブラリredsvdを公開しました - DO++
大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは
P != NP（P≠NP）予想が証明されるかも：アルファルファモザイク
■編集元：ニュース速報板より「P != NP（P≠NP）予想が証明されるかも」 1 カウンセラー(東京都) :2010/08/09(月) 18:19:40.34 ID:ZpOSgVlx● ?PLT(12000) ポイント特典 ある Anonymous Coward 曰く、 本家 /. 記事によれば、HP Labs の Vinay Deolalikar 氏が P≠NP 予想の証明に関する 100 ページに上る論文の草稿を複数名の様々な分野の研究者に送っており、 今週中にも最終稿が公開されるとのこと。 Scribd で公開されている論文は本人のあずかり知らぬところでアップロードされたものらしく、 また、Deolalikar 氏は過去にもこの分野の論文をいくつも執筆しているようです。 P≠NP 予想は 2000 年にクレイ数学研究所のミレニアム懸賞問題の一つに挙げられており、
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
7+6の計算をする時6=3+3だから7+3+3で13って求める奴ちょっと来い
1 名前：以下、名無しにかわりましてVIPがお送りします：2009/08/26(水) 04:14:54.93 ID:P4/WG89F0 お前とはいい酒が飲めそうだ ｀¨ － ､ ＿_ _,. -‐' ¨´ | ｀Tｰて＿,＿｀ `ー<^ヽ | ! ｀ヽ ヽ ヽ r / ヽ ヽ _Lj ､ /´ ＼ ＼ ＼_j／ヽ ｀ ー ヽｲ⌒r-､ヽ ヽ__j´ ｀¨´ ￣ー┴'^´ 118 名前：以下、名無しにかわりましてVIPがお送りします：2009/08/26(水) 04:47:34.61 ID:XxRcqydp0 丸暗記だろ なんでわざわざ分解するんだよ 4 名前：以下、名無しにかわりましてVIPがお送りします：2009/08/26(水) 04:16:59.21 ID:OPdj08zaO ２×７＝１４ １４－１＝１３ もしくは
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
ダイクストラ法, 貪欲アルゴリズム - naoyaのはてなダイアリー
現実逃避をしながらウェブを眺めていたら ダイクストラ法（最短経路問題） にたどり着きました。単一始点最短路問題におけるダイクストラ法の解説です。 何を思ったのか、図を眺めていたところ動かしたい衝動に駆られて、気付いたらパワポでアニメーションができていました。 http://bloghackers.net/~naoya/ppt/090319dijkstra_algorithm.ppt 実装もしてみました。隣接ノードの表現は、ここではリストを使いました。 #!/usr/bin/env perl use strict; use warnings; package Node; use base qw/Class::Accessor::Lvalue::Fast/; __PACKAGE__->mk_accessors(qw/id done cost edges_to prev/); package Q
最小完全ハッシュ関数の作り方 を JavaScript で - てっく煮ブログ
JavaScriptActionScript/Flex ネタが続いているので、たまには JavaScript ネタを。はてブ経由で知った 最小完全ハッシュ関数の作り方 が面白そうだったのだけど、「最小完全ハッシュ関数」が何か分からないまま読み進めたら、やっぱり話が分からなくなってしまった。分からないまま JavaScript に移植。 /* 順列型の最小完全ハッシュ関数 */ function ChangeNumber(arr) { var work = arr.concat(); var hash = 0; // 階乗値テーブル作成 var FACTOR = [1]; for(var i=0; i { FACTOR.unshift(FACTOR[0] * (i+1)); } for(var i=0; i { hash += work[i] * FACTOR[i]; for (j=i+1;
「解読不能は数学的に証明済み」、RSAを超える新暗号方式とは ― ＠IT
2008/04/11 すべての暗号はいずれ破られる。2000年前のシーザー暗号の時代から高度な暗号技術が一般化したデジタル通信の現代に至るまで、それが暗号通信の歴史が証明し続けた事実であると同時に、もっとも人口に膾炙したクリシェでもあった。例えば、鳴り物入りでリリースされたDVDのコンテンツ暗号技術「CSS」（Content Scramble System）が、リリースからわずか数年で10代のノルウェー人ハッカーに破られたことは記憶に新しい。 【追記】（2008年4月15日） この記事は取材に基づいて執筆したものですが、一部専門家らから「CAB方式暗号は解読不能」というのは誇大表現ではないかとの疑義が呈されています。アルゴリズムの公開や第三者による検証がない現在、この記事に登場するCAB方式が発案者・実装者の主張通り画期的な暗号方式で、本当に解読が不可能であるかどうか分かりません。現在、専
アルゴリズム百選 - ベキ乗はO(1)でOK? : 404 Blog Not Found
2007年12月04日23:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - ベキ乗はO(1)でOK? これ、Hyukiさんをはじめ多くの方が疑問に思っていらっしゃるようなので、いまのうちに答えておきましょう。blogで書く以上、書く順番は順不同で構わないのですし。 アルゴリズム百選 - フィボナッチ数列にO()を学ぶ - www.textfile.org フィボナッチ数列の一般項を求める式を使ったときってO(1)って言えるのだろうか？まずは、論より証拠、というわけで実測値をご覧下さい。Cでフィボナッチ数をO(n)アルゴリズムと公式を使ってそれぞれ100万回計算した時にかかった時間をプロットしたものです。最適化をかけていないものと-O3で最適化をかけたものと双方を計測しています。fib(73)まで計算したのは、doubleで整数で保っておける限界がそこまでだったので。ソースは本
アルゴリズム百選 - フィボナッチ数列にO()を学ぶ : 404 Blog Not Found
2007年11月28日18:00 カテゴリアルゴリズム百選Math アルゴリズム百選 - フィボナッチ数列にO()を学ぶ 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10、これほどの反響になるとは。200ブクマぐらいは予想していたが、もいくとは。 とりあえず、本の仮題を「アルゴリズム百選」として、「アマグラマーのすすめ」と同じように本blogに草稿を書いていくことにする。「メインページ」の「アルゴリズム大募集! C&R研究所 - トップページ」の方も適宜更新していくが、「その場で動かせるコードサンプル」はここでないと書けないので。 ただし、「アマグラマーのすすめ」よりは書き方は順不同になるはず。それでも序文相当のことは「チラ見」ならぬ「チラ書き」しておいた方がいいだろう。というわけで、序文に変えて紹介するのが、本Entry。 ヒントとな
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Mathematical Optimization in 60 minutes
https://jp.techcrunch.com/2012/01/20/20120118improvement-on-age-old-mathematical-principle-could-yield-improved-images-video/
システム・エンジニアの基礎知識