最適化計算アルゴリズムCMA-ESのライブラリlibcmaesを使ってみる
CMA-ESについて
CMA-ES (Covariance Matrix Adaptation Evolution Strategy) は連続最適化アルゴリズムの一種です。日本語では共分散行列適応進化戦略と呼ばれます。進化戦略に基づいて、目的関数
を最小化する点
を計算するために使用されます。特徴としては
などが挙げられます。
このアルゴリズムは以下の論文で提案されたそうです。
N. Hansen, and A. Ostermeier.
Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation.
Evolutionary Computation '96
https://doi.org/10.1109/ICEC.1996.542381
アルゴリズムの概要
各イテレーションで多数のサンプリング点を保持し、これらを進化計算の要領で更新していくことで最適解を発見します。進化計算の観点からは、イテレーションがgenerationに対応し、サンプリング点群がpopulationに対応しています。あるpopulationは前のgenerationのpopulationから計算される共分散行列を元に生成されます。
二次元の目的関数に対しCMA-ESを適用した様子を表した図。出典：Wikimedia Commons by Sentewolf。
libcmaesについて
CMA-ESを実装したライブラリlibcmaesがEmmanuel Benazera氏によって公開されています。ライセンスはLGPLv3です。C++11で書かれています。Python向けのバインディングもあります。
Mac OS Xでlibcmaesを動かす
下記のページに従います。
Building libcmaes on Mac OSX · beniz/libcmaes Wiki · GitHub
ます必要な依存ライブラリをbrewでインストールします。
$ brew install automake $ brew install eigen
続いて下記コマンドを実行します。
$ git clone https://github.com/beniz/libcmaes.git $ cd libcmaes $ ./autogen.sh $ ./configure --with-eigen3-include=/usr/local/include/eigen3 CXXFLAGS="-I/usr/local/include -O3" --prefix=[XXX] $ make $ make install
環境を変に汚したくなかったので、ここではconfigureのprefixに適当なパス (上記では [XXX] と表示) を与えました。与えたパスの配下に以下のフォルダが生成されます。
[XXX]/include [XXX]/lib [XXX]/bin
あとは通常のライブラリと使用方法は同じです。なおbin以下にはテストコードが含まれています。
使用例
以下のように使います。
// ヘッダファイルの読み込み #include <libcmaes/cmaes.h> // 目的関数の定義 libcmaes::FitFunc func = [](const double *x, const int N) { double val = 0.0; for (int i = 0; i < N; ++ i) { val += x[i] * x[i]; } return val; }; int main(int, char**) { // 探索空間の次元 const int dimension = 10; // 初期解の定義 const std::vector<double> x0(dimension, 10.0); // 初期の分散値 const double sigma = 0.1; // 各generationにおける個体数 const int lambda = 100; // 最適化計算の実行 libcmaes::CMAParameters<> cmaparams(x0, sigma, lambda); libcmaes::CMASolutions cmasols = libcmaes::cmaes<>(func, cmaparams); // 結果の表示 std::cout << cmasols << std::endl; // 返り値 return cmasols.run_status(); }
実行結果は以下の通りです。
best solution => f-value=1.28654e-14 / fevals=13300 / sigma=0.00235696 / iter=133 / elaps=28ms / x= 7.8921e-09 1.60128e-10 -9.10801e-09 -4.36625e-08 2.52471e-08 1.12213e-09 -2.0139e-08 -1.15845e-10 2.67003e-08 9.51658e-08
ここでは10次元の関数を最適化するのに、反復回数として133回、時間として28ms必要だったことを示しています。
なぜCMA-ESか
最近読んだ論文でCMA-ESが使われているのを見て気になったので調べました。Derivative-freeなアルゴリズムは使い易いため、今後の自身の研究でも活躍する機会があるかもしれません。
Jungdam Won and Jehee Lee.
Shadow theatre: discovering human motion from a sequence of silhouettes.
SIGGRAPH 2016.
http://mrl.snu.ac.kr/research/ProjectShadowTheatre/ShadowTheatre.htm
www.youtube.com
Gaurav Bharaj, David I. W. Levin, James Tompkin, Yun Fei, Hanspeter Pfister, Wojciech Matusik, and Changxi Zheng.
Computational Design of Metallophone Contact Sounds.
SIGGRAPH Asia 2015.
http://people.seas.harvard.edu/~gaurav/papers/cdmcs_sa_2015/
www.youtube.com
ベクトルや行列による微分の公式
ベクトルや行列に関する微分演算でよく使う式です。
小文字ボールド体はベクトル、大文字ボールド体は行列を表しています。
基本
応用（基本の式から導出可能）
その他
参考URL
- Matrix calculus - Wikipedia
- http://www.colorado.edu/engineering/CAS/courses.d/IFEM.d/IFEM.AppF.d/IFEM.AppF.pdf
- http://nlp.dse.ibaraki.ac.jp/~shinnou/zemi2012/kernel/vector-bibun.pdf
- 共分散行列を含む多次元のガウス関数の微分 - yuki-koyama's blog
- 優決定系の線形方程式の最小二乗解を与える際の式変形（導出） - yuki-koyama's blog
- matrices - Gradient of squared Frobenius norm - Mathematics Stack Exchange
注意
ベクトルで微分する際には分子レイアウト記法 (Numerator layout) と分母レイアウト記法 (Denominator layout) の2種類があり、この記事では暗黙的に後者をを仮定しています。詳しくは以下を参照。
論文読み: From Inspired Modeling to Creative Modeling (The Visual Computer 2016)
はじめに
今回紹介するのは、最近 Springer 社のジャーナル The Visual Computer に掲載された論文です。全体を大雑把に触れつつ、印象に残ったフレーズなどを引用しながらまとめたいと思います。
この論文の目的
Computational creativity と呼ばれる研究分野があります。Wikipedia によると、この分野は次の３つの目標を掲げています（意訳）：
- 人間の創造的な活動を支援する
- 人間の創造性を理解し、アルゴリズムとして定式化する
- 人間レベルの創造性を有するシステムを構築する
下の項目ほど究極的で難しい目標といえます。
この論文は、computational creativity の中でも、特に computer graphics における形状モデリング (geometric modeling) というデザインタスクに関する創造性にフォーカスをあてて議論することを目的としています。具体的には、上述の目標 1. を掘り下げた次の問い：
Can machines assist or inspire humans in a creative endeavor for the generation of geometric forms?
を主題として議論を進めていきます。
創造性とは何か？
このような問いを考察するにあたって、まず創造性の定義を確認しておくことは重要です。しかしながら、創造性を厳密に定義するのは容易ではありません。そこでこの論文では明示的な定義を避け、代わりに心理学や人工知能の分野の文献を幾つか引用した上で、以下のように簡単に説明しています：
A common view is that creativity is innately linked with unpredictability or the elements of surprise (5). Specific to computer graphics, creative inspirations to modelers are often in the form of new models that were not envisioned and contain certain elements of surprise or unexpectedness.
創造性について議論する上でのキーワードとして unpredictability という言葉が使われています。著者らは、unpredictability はランダムな振る舞い (stochastic process) をシミュレートすることで達成されうるという考えを述べています。ただし、単にランダムな振る舞いによって形状モデルを生成したり提示したりするだけでは効果的ではなく、
... the presented models remain sensible and follow the rationale of the modeling task.
という条件を達成するために、unpredictability に加えて controllability も考慮する必要があるとも述べています。簡単に言えば、controllability を欠いた完全なデタラメでは、創造的タスクの支援において役に立たないということです。この unpredictability と controllability は互いに競合する目標ですが、両者がバランスよく達成されていることが重要だと述べています。
Inspired Modeling から Creative Modeling へ
上述の内容を踏まえた上で、この論文ではまず inspired modeling と呼ばれる手法について議論します。これは必ずしも unpredictable and controllable ではないものの、何らかの inspiration をユーザに与えることで形状モデリングに関する創造的タスクの実施を支援するものです。代表的手法として、(1) exploratory modeling 及び (2) example-driven synthesis をとり挙げます。
続いて、unpredictability や controllability をより明示的な形で考慮する creative modeling と呼ばれる手法について議論します。代表的手法として (1) evolutionary algorithms と (2) co-creation をとり挙げます。
Inspired Modeling
1. Exploratory Modeling
Exploration という言葉はこの分野の論文では頻繁に用いられ、日本語ではよく「探索」と訳されます。この論文では exploratory design の特徴を
... when the user starts his journey, he does not know where he is heading.
と表現しています。ここで、journey は design task を遂行する過程を比喩的に表したものです。多少私見を交えてこれを解釈すると「明確なデザインのビジョンがない状態でデザインタスクを開始し、試行錯誤を繰り返す中でビジョンを形成していく、open-ended なデザインタスクの進め方」を exploratory design と呼んでいるのだと思います。創造的なデザインタスクを遂行することは、基本的には exploratory だとみなすことができます。
Exploratory design を支援する代表的な手法として、Marks らによる Design Galleries が挙げられています：
J. Marks, B. Andalman, P. A. Beardsley, W. Freeman, S. Gibson, J. Hodgins, T. Kang, B. Mirtich, H. Pfister, W. Ruml, K. Ryall, J. Seims, and S. Shieber.
Design galleries: a general approach to setting parameters for computer graphics and animation.
SIGGRAPH 1997.
DOI
Design galleries: a general approach to setting parameters for computer graphics and animation.
SIGGRAPH 1997.
DOI
このシステムは、デザインパラメタが張る空間の exploration を効率化するために、デザイン空間をランダムサンプリングし、幾つかのサンプリング点をユーザに対し視覚的に提示します。サンプリング点はユーザにとって unexpected であるため、creative modeling としての性質も部分的にはあると考えられますが、著者らはこれに関して
We argue that while a random result could be inspiring, we would like an inspiring tool to be smarter to offer more targeted inspirations and to allow the user a sufficient level of control.
と述べ、controllability に関する扱いが不十分であると位置付けています。
他の exploratory modeling のアプローチとして、尤もらしいデザイン要素をユーザに提示することで、ユーザがデザイン要素を選択して組み立てていくことを効率化するという方法があります。この例として、以下の論文が言及されています：
Siddhartha Chaudhuri, Evangelos Kalogerakis, Leonidas Guibas, and Vladlen Koltun.
Probabilistic reasoning for assembly-based 3D modeling.
SIGGRAPH 2011.
DOI
Probabilistic reasoning for assembly-based 3D modeling.
SIGGRAPH 2011.
DOI
この研究では probability を考慮することで提示内容の controllability を高めたと考えることができますが、一方で
... these techniques model the expected, in a probabilistic sense, rather than directly striving for the unexpected or the creative.
です。つまり unpredictability に関する扱いが不十分であるため、creative modeling としては位置付けていません。
2. Example-Driven Synthesis
ここでの synthesis とは三次元モデルを合成（生成）することを指しています。Example-driven synthesis では、事前入力として少数の事例（例えば椅子の三次元モデルを５種類、など）を与え、そこからシステムが自動的に同じカテゴリに属する三次元モデルを新しく生成します。このようなパラダイムのことを論文では「More of the same」と表現しており、具体的には次のような問題と捉えています：
... given a set of examples, how to generate more of the same, in the positive sense, more instances that clearly appear to belong to the same class as the input set of examples.
Example-driven synthesis の具体的として、以下の論文が紹介されています：
William Baxter and Ken-ich Anjyo.
Latent Doodle Space.
Eurographics 2006.
Latent Doodle Space.
Eurographics 2006.
これは OLM Digital の安生さんらによる論文で、ユーザが線画を幾つか例として与えると、システムがそれらを学習して新たな線画を生成することができたりする手法を提案しています。
創造性という観点で example-driven synthesis の手法を考えたとき、著者らは
... the generated instances were not aimed to include unexpected results or be truly creative in any sense.
という解釈を示しています。つまり、生成される結果に対して unpredictability が十分に含まれていないため、「真に創造的」ではないとしています。
Creative Modeling
1. Creativity by Evolution
創造的なアプローチの代表例として著者らが最初に取り上げるのは、進化計算 (遺伝的アルゴリズム) による方法です。遺伝的アルゴリズムは
- Mutation (突然変異)
- Cross-over (交叉)
- Selection (選択)
の３つの処理からなります。それぞれの処理において stochastic な振る舞いを用いることによって unpredictability を取り入れることができる一方で、selection の処理の際に使われる fitness function を適切にデザインすることによって controllability を保証することができます。
遺伝的アルゴリズムによる三次元モデルの生成は昔から行われてきましたが、特に最近の例として以下の論文が紹介されています：
Kai Xu, Hao Zhang, Daniel Cohen-Or, and Baoquan Chen.
Fit and diverse: set evolution for inspiring 3D shape galleries.
SIGGRAPH 2012.
Project page
Fit and diverse: set evolution for inspiring 3D shape galleries.
SIGGRAPH 2012.
Project page
この研究ではユーザ自身が fitness function として振る舞う、対話型遺伝的アルゴリズムの方式をとっています。更に、creative modeling という文脈でより効果的にするための工夫として、生成されるモデルの diversity を保つような定式化をしています。
2. Creativity from Co-Creation
創造的なアプローチとしてもう１つ取り上げるのは co-creation による方法です。Wikipedia によると co-creation は
Co-creation is a management initiative, or form of economic strategy, that brings different parties together, in order to jointly produce a mutually valued outcome.
と説明されています。それぞれのクリエータが独立に作業をし、互いに何を創作しているか分からないような状況を作ることによって、unexpectedness が発生する可能性を高めることができるというのが重要なアイデアです。
ただし、この unexpectedness は完全な randomness とは異なるとも述べています。それぞれのクリエータが全体の作業における自分の役割を認識していたり、または
... they should only be concealed partially, so that each creator sees a hint to constrain him/her own contribution.
のようにそれぞれの貢献を部分的に共有したりすることで、controllability を担保することができると考えられます。
このような co-creation による創造性のメカニズムを理解するための具体例として、exquisite corpse というゲームを紹介しています。ゲームを知らない場合は以下の動画をご覧ください：
このゲームでは与えられたテーマや境界における情報が controllability を担保する部分となっています。
さて、この co-creation において最も興味深い将来展望として、human-computer co-creation というコンセプトを紹介しています。よく似たコンセプトとして creativity support tool が human-computer interaction (HCI) の分野 (e.g., CHI, UIST, CSCW, ...) で研究されていますが、これはあくまでユーザの創造性を accelerate するだけで、コンピュータ自身が創作を行うものではありません。
各コンセプトの比較。Creativity support tool は必ずしもシステムそのものが創造的活動を行うわけではない。Generative systems はこの論文では詳しく触れていないが、システムが自動的に創作をし、ユーザにその結果を提示する。Human-computer co-creation ではユーザとシステム双方が創作を行う。
また、この human-computer co-creation というコンセプトは全く新しいわけではなく、抽象画の創作などのアプリケーションですでに事例が報告されています：
Nicholas Davis, Chih-Pin Hsiao, Yanna Popova, and Brian Magerko.
An enactive model of creativity for computational collaboration and co-creation.
Creativity in the Digital Age (Book Chapter).
DOI
An enactive model of creativity for computational collaboration and co-creation.
Creativity in the Digital Age (Book Chapter).
DOI
今後は、形状モデリングを含む様々なデザインドメインにおいて、human-computer co-creation の論文が登場していくと思われます。
最後に（＋自分の研究の宣伝）
この論文は、形状モデリングを具体的なトピックとして考えていたものの、広く「デザインにおける創造性」について議論したものとなっていました。
Computational design におけるデザインの評価軸として、近年の SIGGRAPH では functionality を扱った研究が発表されるようになってきました。例えば私は以下の研究を発表しました：
Yuki Koyama, Shinjiro Sueda, Emma Steinhardt, Takeo Igarashi, Ariel Shamir, and Wojciech Matusik.
AutoConnect: Computational design of 3D-printable connectors.
SIGGRAPH Asia 2015.
Project page
AutoConnect: Computational design of 3D-printable connectors.
SIGGRAPH Asia 2015.
Project page
また、HCI の分野でデザインの aesthetic preference を評価軸として扱う研究を発表しました：
Yuki Koyama, Daisuke Sakamoto, and Takeo Igarashi.
Crowd-powered parameter analysis for visual design exploration.
UIST 2014.
Project page
Crowd-powered parameter analysis for visual design exploration.
UIST 2014.
Project page
これら functionality, aesthetic preference を考慮することに加えて、この論文では
The new criteria that are key to design applications include aesthetics, functionality, and inevitably, creativity.
と、creativity が重要だと主張しています。これが computational design 研究の次の大きな流れになっていくのかもしれません。
また、この論文で議論してきた内容は computer graphics の分野だけでなく computational creativity、人工知能、HCI などとも深く関連があります。なぜ computer graphics の分野でこのような議論を行う必要があるのかという疑問に対して、著者らは次のような主張をしています：
We should all believe that computer graphics is far beyond image synthesis. It is capable, and should be driven, to supplement humans at a much earlier stage in the synthesis pipeline, as early as creative design and conceptualization.
最後にこの論文では、創造性はパーソナルなものである、つまり
... difference individuals exhibit and resonnate with different types of creativity thinking.
と指摘しています。その上で、個人差を考慮して創造的タスクの支援などを行っていくことの重要性を指摘しています。
Personal preference を学習することでデザインを支援する研究として、次のものを発表しました：
Yuki Koyama, Daisuke Sakamoto, and Takeo Igarashi.
SelPh: Progressive learning and support of manual photo color enhancement.
CHI 2016.
Project page
SelPh: Progressive learning and support of manual photo color enhancement.
CHI 2016.
Project page
今後は、personal preference learning と computational creativity を結びつけた研究が登場していくことになると思います。
UnityのNative Pluginを作ってC++のコードやライブラリを使う
概要
UnityといえばC#で開発するのが基本ですが、Native Pluginという機能を使えば、他の言語 (C++など) で書かれたコードを呼び出すことができます。
今回はじめてNative Pluginを作ってみたので、調べたことなどをメモしておきたいと思います。
C++のライブラリ (Eigenとlibigl) を用いてUnity上でメッシュのガウス曲率を可視化した例
背景と動機
普段はC++でコンピュータグラフィクス関連の研究をしています（プロダクトの開発は行なっていません）。私がC++を使う主な理由は
- 過去に自分で書いたコードを使いまわしたいから
- 優秀な数学演算のライブラリや高度なジオメトリ処理のライブラリを使えるから
- 高速化がしやすいから
などです。一方でUnityを使うこともあります。私がUnityを使う際の主な理由は
などです。
つまり、技術自体を作り込むにはC++が便利だけど、技術デモを作り込むにはUnityが便利なわけです。このトレードオフを解決する手段として、C++で開発した技術をUnityのNative Pluginとして呼び出すという方法を試してみることにしました。
C言語でインタフェースを作る
C#からC++で作ったNative Plugin (動的ライブラリ) の機能を呼ぶには、C言語の関数でやりとりするようです。例えばC++側では以下のようなC言語の関数を定義しておきます：
extern "C" { void* InstantiateMesh(const int* triangles, const double* vertices, int numberOfTriangles, int numberOfVertices); void DeleteMesh(void* mesh); }
なおextern "C"という宣言はC++のName Manglingを回避するために必須なのだそうです。上記の関数は、C#側で以下のように宣言することで使用可能になるようです：
[DllImport ("PluginName")] private static extern IntPtr InstantiateMesh(IntPtr triangles, IntPtr vertices, int numberOfTriangles, int numberOfVertices); [DllImport ("PluginName")] private static extern void DeleteMesh(IntPtr mesh);
intやdoubleは両言語共通で使えるようです。IntPtrとはポインタのことだそうです。
Xcodeでバンドルをビルドする (Mac OS X)
上記のサイトに従ってバンドル (.bundle) を作成し、UnityプロジェクトのAsset以下の適切な場所に配置します。
この際の注意点は、target architecturesの設定です。Unity 4のエディタは32-bitで動いているようなので、32-bit用のバンドルを作成する必要があります。その場合はi386を指定します。また、Unity 5は64-bitにも対応しているそうです。その場合はx86_64を指定します。これは意外に面倒な問題です。
ここで一番良いと思われる方法は、公式マニュアルでも言及されている通り、Mac OS Xについてはいつでもユニバーサルバイナリを作ることです。ユニバーサルバイナリとは複数のアーキテクチャで使えるバイナリです。Xcodeでもそのような選択肢が用意されています。
Xcode上でユニバーサルバイナリを指定
もう一つ注意点としては、既存のビルド済みスタティックライブラリを用いてユニバーサルバイナリをビルドするには、既存のライブラリもまたユニバーサルバイナリとしてビルドされている必要があります。例えばHomebrewで
$ brew install boost
などのコマンドでライブラリ (ここではboost) をいれている場合は、普通ユニバーサルバイナリとしてビルドしてくれていません。この問題を解決するには
$ brew reinstall boost --universal
とすることでユニバーサルバイナリとしてビルドしなおしてくれるようです。
なお
$ lipo -info (ライブラリへのパス)
などとすると既存のライブラリがどのアーキテクチャ向けにビルドされているか確認することができます。
ただしHomebrewのオプションを指定する方法は（なぜか）いつでもうまくいくわけではないようで、いくつかのライブラリについてはユニバーサルバイナリを作ってくれないようです。自分の場合はCGALというジオメトリ処理用のライブラリをHomebrewでいれようとしても、うまくユニバーサルバイナリを作ってくれませんでした。そこでHomebrewを諦めてCMakeでCGALをビルドすることにしました。CMakeでは
CMAKE_OSX_ARCHITECTURES=x86_64;i386
と指定するとユニバーサルバイナリを作ってくれます。
C#からC++へ配列を渡す
配列のやりとりは基本的にはポインタのやりとりになりますが、C#にはmanagedとかunmanagedとかいう概念があるそうで（C#に疎いので知りませんでした）、ちょっと工夫が必要です。例えばint型の配列をC#からC++に渡すには以下のようにするようです：
int[] triangles = mesh.triangles; IntPtr unmanagedTriangles = Marshal.AllocHGlobal(triangles.Length * sizeof(int)); Marshal.Copy(triangles, 0, unmanagedTriangles, triangles.Length); // ここでunmanagedTrianglesを使ってC++の関数を呼ぶ Marshal.FreeHGlobal(unmanagedTriangles);
このコードは手元では動きましたが、ググると色々な人が色々な方法を提示しているので、これが正解ではないかもしれません。
C++からC#へ配列を渡す
これもmanagedとかunmanagedとかいう概念を考慮する必要があるらしく、例えばdouble型の配列を受け取るには以下のようにすれば良いようです：
IntPtr tempPtr = IntPtr.Zero; int arrayLength = 0; SomeFunctionInNativePlugin(ref tempPtr, ref arrayLength); double[] array = new double[arrayLength]; Marshal.Copy(tempPtr, array, 0, arrayLength); // ここで何らかの手段でtempPtrが指すメモリ領域を解放する
C++のクラスをC#で使う
上記のようなラッパーを書けばC#側からC++のクラスをインスタンス化したりメソッドを呼んだりできそうです。ただしこれはかなり面倒そうです。誰かラッパーを自動生成するスクリプト書いてください。
余談：コンピュータグラフィクスの研究にどう使うか
コンピュータグラフィクスの要素技術研究に伴う開発では、もちろん研究内容によりますが、頻繁に仕様変更がおきたり、様々な実装の可能性を試行錯誤していく必要が生じます。そういった研究の初期段階では、C++とUnityを組み合わせた開発スタイルではラッパークラスなど本質的でないコードの変更が大量に発生するため、かなり効率が悪そうだと感じました。やはりC++でテスト用のレンダラを実装したりテストシーンを構築したりする方が良さそうです。技術の内容が完全に確定し、論文を書いたり人に見せるためのデモ用シーンを作ったりする段階になって初めてUnityと組み合わせるというのが現実的な選択肢だと思いました。
最後に
間違い・意見などありましたらご連絡いただけると幸いです。
