Old but New Algorithms
藤田昭人
本稿では Earth Mover's Distance というアルゴリズムを紹介します。 このアルゴリズム、Wikipedia 日本語版にはページがないので英語版から引用しますと…
In statistics, the earth mover's distance (EMD) is a measure of the distance between two probability distributions over a region D. In mathematics, this is known as the Wasserstein metric. Informally, if the distributions are interpreted as two different ways of piling up a certain amount of dirt over the region D, the EMD is the minimum cost of turning one pile into the other; where the cost is assumed to be amount of dirt moved times the distance by which it is moved.
統計学では、Earth mover's distance (EMD)は、領域D上の2つの確率分布間の距離の尺度である。 数学では、これはワッサーシュタイン計量法として知られている。 直感的に説明すると、分布が領域D上にある量の土を積み上げる2つの異なる方法であると解釈される場合、 EMDは、一方の土をもう一方の土に変えるための最小コストであり、 コストは土の移動量に移動距離をかけたものと仮定される。
確かに "Informally, " とは書いてありますが、数学がダメダメな僕の直感にはちっとも響かない。 こういう時は "History" の項目に目を移すのが僕の常套手段です。
「モンジュの問題」
元々は「1781年に ガスパール・モンジュ （Gaspard Monge） が（数学の）輸送理論の文脈で初めて導入した」とのこと。 そこで「ガスパール・モンジュ」「 輸送理論」でググってみると 「モンジュの最適輸送問題をめぐる話題について」 というスライドがひっかかりました。そこから「モンジュの最適輸送問題」で調べまくったところ次の記事に行き当たりました。
この記事は福岡大学の桑江先生がお書きになった「研究雑談」なのですが、 何が素敵かというと「数学者が書いた文章なのに数式が全く出てこない」ってところです。
本項では、記事の中ほどにある「モンジュの問題」の説明を杖に以降の話を進めていきます。
元々は「砂山を移動させる」問題だった
桑江先生の説明では 「モンジュはラプラス、フーリエと並んで ナポレオンに仕えた数学者の一人であり、 真面目で正義感の強い人物でしたが、 それが災いしてか、 ナポレオンに最後まで信奉したために 最後には悲惨な末路を迎えた逸話が残っています」 とのことなんですが、Wikipedia でのモンジュの経歴をみると数学に秀でた軍人だったように見えます。
そのように理解すると、 当時ヨーロッパで最強の陸軍だった ナポレオンの軍団の上級将校だったとの想像から、 問題１「ある砂山をそれと同じ体積の穴に移したい。 砂粒の移動には移動距離に依存したコストがかかる時、最適な移動のさせ方は何か？」 という問いも非常にイメージしやすくなります。 陣地を構築するために大量の砂を 輸送する必要があったとか、 騎馬を進めるために行く手にある 大量の穴ぼこを全部埋める必要があるとか… と状況は腑に落ちます。
桑江先生によれば、 この問題「密に詰まった無限の各砂山から 密に詰まった無限の各穴に総コストが最小となるような １対１上への写像を決める問題」と理解できるそうで 「たいへんな難問」なんだそうです。 この説明、僕にはピンと来ないのですが、 それでも、山と積み上っている砂粒を 一粒ずつ行き先を決める関数を書いてコンピュータで 実行するとしても、いつ計算が終わるかわからない 無謀なプログラムが出来上がることぐらいは 想像が付きます。
ともあれ…
この問題が今から２００年以上前の ナポレオンの時代に提示されていたことに、 まずはビックリっと言ったところでしょう。
問題を「荷物の移動」に変更すると…
そこで、写像の問題（らしい）「モンジュの問題」を 解くために、問題の方を置き換えるそうです。 問題２「n 個の工場と n 個の店舗があり、 各工場から各店舗にそれそれ一個の製品のみを移動させ距離に応じてコストがかかるとき、 総コストを最小にする移動のさせ方はなにか？」
これで「工場の散らばり（確率分布）と 店舗の散らばり（確率分布）が与えられているときに 移動の総コストが最小となるような 工場と店舗の配置の結合分布を求めよ」と 置き換えられたそうで、 確かに工場や店舗に収まっている荷物は 砂粒よりは（物理的に）ずっと大きいので 現実的なプログラムが書けそうです。
本稿の冒頭にある「領域D上の２つの確率分布」とは こういうことかぁ…と思った次第。 つまり Earth mover's distance (EMD) とは 「モンジュ・カントロヴィッチ問題（ＭＫ問題）」 を解くアルゴリズムという訳ですね。 ちなみにカントロヴィッチはこの方です。
でもね、この問題２は「ヒッチコック型輸送問題」って言いませんでしたっけ？ このヒッチコックって誰？カントロヴィッチとはどういう関係？
「ヒッチコック型輸送問題」とは？
普通、ヒッチコックといえば映画監督の アルフレッド・ヒッチコック を思い浮かべる方が多いと思うのですが、 ここで登場するヒッチコックはこの方です。
どうやらＭＩＴの先生でいらっしゃったようですね。 彼自身がモンジュ由来の輸送問題に言及したのは、1941年の論文 "The Distribution of a Product from Several Sources to Numerous Localities（複数の供給元から複数の地域への製品の流通）" です。この論文が問題２が紹介された初めてのケースだったようです。 また「ヒッチコック型輸送問題」は "HITCHCOCK TRANPORTATION PROBLEM" という報告書でも紹介されています。
The transportation problem was first formulated by F. L. Hitchcock in 1941; he also gave a computational procedure, much akin to general simplex method, for solving the problem. Independently, during World War II, T. C. Koopmans arrived at the same problem in connection with his work as a member of the Joint Shipping Board. The Problem is thus frequently referred to as the Hitchcock-Koopmans problem.
輸送問題は1941年に F. L. Hitchcock によって最初に定式化され、問題を解くための一般的なシンプレックス法に近い計算手順を与えた。 それとは独立して、第二次世界大戦中、T. C. Koopmans は英米共同海運委員会のメンバーとしての仕事に関連して、同じ問題に到達した。 このような経緯から、この問題はヒッチコック・クープマンズ問題と呼ばれることが多い。
新たに登場したクープマンズとはこちら方です。
ザッと経歴をみてみると… 1940年にオランダからアメリカへ移民した人、 名前から察するにユダヤ系のようなので ナチス・ドイツの迫害を逃れてきたようですね。 オランダでは理論物理学者として 研究をしていたようですが、 移民を契機に統計学に転向し、 その後、経済学者として活躍した人のようです。
しかし、次から次へと新たな人物が登場するのは、 数学に関わるトピックだからでしょうか？ ちょっとキリがない気がしてきました。 ここで探索のアプローチを変えて、 最後の報告書に着目します。 というのも、この文書が保管されていたサイトが手がかりになりそうだから。
このサイトはアメリカの国防総省が管轄した過去の委託研究の報告書のアーカイバーです。主にＡＲＰＡ （国防高等研究計画局） の委託研究、例えばインターネットの技術基盤となった ＡＲＰＡＮＥＴの開発時の研究報告などが収蔵されているわけなのですが、 ＡＲＰＡが設立されたのが1958年ですので、 この報告書はそれ以前のものです。
つまり「ヒッチコック型輸送問題」とは 国防総省が関心を持つような研究だったことになります。
３人の接点
そこでカントロヴィッチ、ヒッチコック、 クープマンズの３人に何かしらの接点がないかと探したところ、Wikipediaの 線形計画法 の英語版 Linear programming のページで次の記述を見つけました。
In 1939 a linear programming formulation of a problem that is equivalent to the general linear programming problem was given by the Soviet mathematician and economist Leonid Kantorovich, who also proposed a method for solving it. It is a way he developed, during World War II, to plan expenditures and returns in order to reduce costs of the army and to increase losses imposed on the enemy. Kantorovich's work was initially neglected in the USSR. About the same time as Kantorovich, the Dutch-American economist T. C. Koopmans formulated classical economic problems as linear programs. Kantorovich and Koopmans later shared the 1975 Nobel prize in economics. In 1941, Frank Lauren Hitchcock also formulated transportation problems as linear programs and gave a solution very similar to the later simplex method. Hitchcock had died in 1957 and the Nobel prize is not awarded posthumously.
1939年、ソ連の数学者で経済学者のレオニード・カントロヴィッチが 一般的な線形計画問題に相当する問題を線形計画法で定式化し、 彼もその解法を提案した。 それは、第二次世界大戦中に、軍隊のコストを削減し、敵に課せられる損失を増やすために、 支出とリターンを計画するために彼が開発した方法である。 カントロヴィッチの研究は、当初ソ連では軽視されていた。 カントロヴィッチとほぼ同時期に、 オランダ系アメリカ人の経済学者T.C.クープマンスが、古典的な経済問題を線形プログラムとして定式化した。 カントロヴィッチとクープマンスは、後に1975年のノーベル経済学賞を共同受賞した。 1941年には、フランク・ローレン・ヒッチコックもまた、交通問題を線形プログラムとして定式化し、 後のシンプレックス法と非常によく似た解を与えました。 ヒッチコックは1957年に死去しており、ノーベル賞は死後に授与されていない。
どうやらカントロヴィッチ、ヒッチコック、 クープマンズの３人は互いに独立して、 後に線形計画法と呼ばれる研究に 先鞭をつけていたようですね。
線形計画法といえば ジョージ・ダンツィーグ （George Dantzig） の シンプレックス法 を思い出します。 ダンツィーグがこの技法を発表したのは1947年のことですが、 カントロヴィッチ、ヒッチコック、クープマンズの３人の取り組みは、 概ねその１０年近く前の第２次世界大戦が勃発した前後のことだったようです。
つまり、今日オペレーションズ・リサーチ（ＯＲ）と呼ばれる研究分野を 切り開いたのはこの３人ということになるわけですね。 なかでも、1939年に「線形計画法」を体系的に語った ”The Mathematical Method of Production Planning and Organization（生産計画と組織の数理的方法）" を発表したカントロヴィチは、 今では「線形計画法」の創始者として 広く認知されてようです。
いや、しかし、 ＯＲがロシア起源だったとは知らなかったなぁ…
オペレーションズ・リサーチの歴史
オペレーションズ・リサーチ （Operations Research） は「数学的・統計的モデル、 アルゴリズムの利用などによって、 さまざまな計画に際して 最も効率的になるよう決定する科学的技法」 と定義されています。 僕は第２次世界大戦後に アメリカで生まれた学問だと 思い込んでいたのですが、 その歴史 を辿ってみると第２次世界大戦中の 「軍事作戦のための兵站計画の立案」 を起源としていたようです。 そもそも「モンジュの問題」自体も この兵站計画の範疇に収まりますからねぇ。
第２次世界大戦後、 この技法は「線形計画法」という名前を冠し、 オペレーションズ・リサーチの技法のひとつとして 非軍事的な用途へも急速に拡大していった訳です。 でも、そこは何分にも冷戦真っ只中の時代のことですから、 技法の由来や起源については 各者が都合よく解釈した…それが、 数学、統計学、経済学の間で史観が微妙に異なり、 同じ問題に（関わったとされる）さまざまな人物の名前が 付けられることになった理由なんじゃないかと 僕は想像しています。
桑江先生も紹介しておられるように、 カントロヴィチは1975年にノーベル賞を受賞しています。 が、それはクープマンズと共同でノーベル経済学賞の受賞でした。
その受賞理由は次のとおり…
The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 1975 was awarded jointly to Leonid Vitaliyevich Kantorovich and Tjalling C. Koopmans "for their contributions to the theory of optimum allocation of resources."
1975年のアルフレッド・ノーベルを記念したスヴェリヒス・リクスバンク経済学賞は、 「資源の最適配分理論への貢献に対して」 レオニード・ヴィタリェヴィチ・カントロヴィッチとティヤリング・クープマンズに共同で授与されました。
一般にノーベル賞は「表彰されるまで待たされる」賞であることで有名ですが、 1975年は冷戦にくたびれていた米ソ両陣営が デタント に向かっていた時期でもあり、 両陣営を代表する学者が共同受賞することで米ソ融和をアピールする狙いがあったのかも？ それが彼らが３５年間も待たされた 理由かもしれません。
「Earth Mover's Distance」という新しい器
ここまで長々と説明して来た
「モンジュ・カントロヴィッチ問題」
ある意味では前世紀に決着済みのはずのこの問題には、
実はその後があります。
そもそも「砂山を運ぶためのコスト」を計算するために
考え出されたはずのこのアルゴリズムですが、
全く別の思いもよらない使い方があったのでした。
その新しい使い方を紹介しているのが論文 "The Earth Mover’s Distance as a Metric for Image Retrieval " （画像検索のための指標としてのEarth Mover’s Distance ） です。2000年に発表されたこの論文では、 なんと類似画像検索での類似度判定にEMDを使うこと提案してます。
そもそも画像検索には「２つの画像がどれくらい似ているかを判定する」アルゴリズムが必要になりますが、 この「画像が似ている」を判定するのは難しいですよね？ 画像の形に着目するのか？色に着目するのか？ はたまた「画像の一部分だけがそっくり」といった例もあるでしょう。 人間が「似ている」と感じることを判定するという意味ではＡＩ的ですし、 近年では機械学習が大きな成果を上げている研究分野でもあります。
論文の要約は次のとおりです。
We investigate the properties of a metric between two distributions, the Earth Mover’s Distance (EMD), for content-based image retrieval. The EMD is based on the minimal cost that must be paid to transform one distribution into the other, in a precise sense, and was first proposed for certain vision problems by Peleg, Werman, and Rom. For image retrieval, we combine this idea with a representation scheme for distributions that is based on vector quantization. This combination leads to an image comparison framework that often accounts for perceptual similarity better than other previously proposed methods. The EMD is based on a solution to the transportation problem from linear optimization, for which efficient algorithms are available, and also allows naturally for partial matching. It is more robust than histogram matching techniques, in that it can operate on variable-length representations of the distributions that avoid quantization and other binning problems typical of histograms. When used to compare distributions with the same overall mass, the EMD is a true metric. In this paper we focus on applications to color and texture, and we compare the retrieval performance of the EMD with that of other distances.
本研究では、コンテンツベースの画像検索における２つの分布間のメトリックであるEarth Mover's Distance (EMD)の特性を調べる。 EMDは、正確な意味で、一方の分布を他方の分布に変換するために支払わなければならない最小コストに基づいており、 Peleg, Werman, Romによって、ある種の視覚問題に対して最初に提案された。 画像検索のために、我々はこの考えを、ベクトル量子化に基づいた分布の表現スキームと組み合わせる。 この組み合わせにより、以前に提案された他の手法よりも知覚的類似度をよく考慮した画像比較のフレームワークが得られる。 EMDは、効率的なアルゴリズムが利用可能な線形最適化からの輸送問題の解に基づいており、 部分的なマッチングも自然に行うことができる。 EMDはヒストグラムマッチング手法よりもロバストであり， ヒストグラムに典型的な量子化やその他のビニングの問題を回避した分布の可変長表現で動作することができる。 同じ全体の質量を持つ分布を比較するために使用される場合、EMDは真のメトリックである。 この論文では、色とテクスチャへの応用に焦点を当て、EMDの検索性能を他の距離と比較する。
どうやら、この提案は比較する２つの画像の各々から特徴を抽出した後、 画像がどれくらい似ているかを数値として表現するためにEMDを使うようです。 さらに詳しい説明は論文を読んでもらうとして…
ちなみに、この論文では Earth Mover’s Distance という名前の由来も紹介されています。
We give the name of Earth Mover’s Distance (EMD), suggested by Stolfi (1994), to this metric in this new context. The transportation problem is to find the minimal cost that must be paid to transform one distribution into the other. The EMD is based on a solution to the transportation problem for which efficient algorithms are available, and it has many desirable properties for image retrieval, as we will see.
Stolfi (1994)によって提案された Earth Mover's Distance (EMD)という名前を、この新しいコンテキストにおけるこのメトリックに与える。 輸送問題は、ある分布を他の分布に変換するために支払わなければならない最小コストを見つけることである。 EMDは、効率的なアルゴリズムが利用可能な輸送問題の解決策に基づいており、画像検索に多くの望ましい特性を持っている。
「Stolfi (1994)によって提案された」とありますが、参考文献には ”Stolfi*1 , J. 1994. Personal communication. ” とあるので、 コンピュータ・ビジョンの専門家の間での 仲間うちでのトークで登場した呼び名なのでしょうか？
しかし、モンジュの問題を踏まえた洒落た名前ですよねぇ。
とりあえず中締めを…
本稿では、ガスパール・モンジュが提起した「モンジュの問題」から "Earth Mover’s Distance" までを （本職の数学者やコンピュータ・ビジョンの専門家に突っ込まれないよう気をつけて） 紹介して来ました。高校数学も怪しい僕にはこのあたりが限界なのですが、 同じテーマで数学者が書いた書籍も出ているようです。
それから EMD といえばコンピュータ・ビジョンの専門家にはよく知られているアルゴリズムだそうですが、 画像認識に関わる基礎技術でもあるので機械学習でも頻繁に登場するようです。
とはいえ、これ以上数式は勘弁して欲しい僕としては、 以下のＣ言語のコードでアプローチしたい思ってます。
以上
