読者です 読者をやめる 読者になる 読者になる

2015年個人的アニメ名場面集

今年もたくさんのアニメ作品に出会えました.今年を振り返って,個人的アニメ名場面集.

四月は君の嘘 14話 椿の恋心

今年一番のアニメは?と言われたら間違いなく「四月は君の嘘」ですね.昨年末から2クールでやっていたけど,年明けてからのストーリーの猛攻が凄かった.特に,幼なじみの椿が恋心を自覚するシーンが綺麗すぎて,何回見なおしたか・・・.

君嘘はいいぞ・・・

Go!プリンセスプリキュア 39話 「レッツゴー,プリンセス」

今年のプリキュアは,自分の中ではスマプリ以来のヒット!特に,キュアフローラは,強くてかっこよくて可愛い,まさに主人公といった感じのプリキュアで大好きです.そんなフローラが変身できなくなってしまい,自分の夢を見つめなおし,再び立ち上がったときの台詞,「レッツゴー,プリンセス」,カッコよすぎ!その後の変身(特殊バンクでこれまたカッコイイ)や挿入歌「プリンセスの条件」まで含めて,まさにGoプリのハイライトでした.

ここまで全話神回で来て,残りあと僅か,最後まで突っ走ってほしいですね.

ご注文はうさぎですか?? ED

2期EDはまさに「可愛さの暴力」.あまりの可愛さに度肝を抜かれて変な声出ましたね.2期はチノちゃんが髪型豊富+可愛さ爆発してて良かった.

D論書いてるときにごちうさ2期があって本当に良かった・・・.

劇場版 ラブライブ! 僕たちはひとつの光

今年もラブライブが,何かと話題をさらってましたね〜.自分も5th,劇場版,ファンミ2回,アニサマと,昨年よりかなり多くμ'sのイベに行きました.劇中の最後に流れる「僕たちはひとつの光」.何回も聴いているうちに,μ'sの解散ライブでこれが流れる様子が想像できて,何か感動するという不思議な曲.

来年のFINALもぜひ行きたい!その前に紅白も見なければ!

響け!ユーフォニアム 8話 夜の山

今年の京アニ山田尚子)枠は,響け!ユーフォニアムけいおん・たまこまとは違って,ちょっとドロドロしてたけども,演出は凄かったですね〜.特に2人で夜の山に登るシーンは,なんとも言えない青春の狂気に満ちていた.

走るシーンの作画はけっこうスゴい.


今年も色んなアニメに救われた1年でした.来年もいいアニメにたくさん出会えますように.皆様,良いお年を.

デジモンアドベンチャー tri. 第1章 観てきた

ネタバレ注意

続きを読む

プリキュアで学ぶ劣モジュラ関数

Machine Learning Advent Calendar 2015 1日目の企画です.

機械学習人工知能系の国際会議(ICML, NIPS, AAAIなど)のチュートリアルや論文を眺めたことのある人なら,Submodular Function(劣モジュラ関数)という単語に見覚えがあるかもしれません.実際,ICML 2013,AAAI 2015や今年のIBISでも劣モジュラ関数のチュートリアル講演がなされています.今回は,劣モジュラ関数についてプリキュア解説したいと思います.

劣モジュラ関数とは

劣モジュラ関数は集合関数(ある集合の部分集合を引数に取り,実数値を返す関数)の一種です.具体的には以下の定義を満たす関数です.

$f: 2^E \to \mathbb{R}$ が劣モジュラ関数
$\iff$ 全ての$X \subseteq Y$ と $i \not\in Y$ に対して
\[
f(X \cup \{ i \}) - f(X) \geq f(Y \cup \{ i \}) - f(Y)
\]

注: $2^E$ は $E$ の全ての部分集合の集合を表す記号です.

はい,全然分からん!そこでプリキュアの出番です.

$E$ を全てのプリキュアの集合としましょう.つまり
$E =$ {キュアブラック, キュアホワイト, ... , キュアスカーレット }
です.

(↓$E$のイメージ図)

プリキュアを何人か集めてきた集合を $X$ としたとき,その中に含まれるプリキュアの色の種類を $f(X)$ として定義します.

たとえば
$X =$ {キュアマリン(青), キュアピーチ(桃), キュアピース(黄), キュアフローラ(桃)}
にすると,$X$には全部で3色のプリキュアがいるので $f(X) = 3$ です.

$X$ を含む集合として
$Y =$ {キュアマリン(青), キュアピーチ(桃), キュアピース(黄), キュアフローラ(桃), キュアミント(緑), キュアエース(赤)}
を取ると,今度は $f(Y) = 5$ です.

ここで,$X$ と $Y$ にキュアマーチ(緑)を足して,$f$ の値がどう変化するかをみてみます(つまり $i =$ キュアマーチ).
$X \cup \{ i \} =$ {キュアマリン(青), キュアピーチ(桃), キュアピース(黄), キュアフローラ(桃), キュアマーチ(緑)}
ですから,$f$ の値は1増えます.
一方で,
$Y \cup \{ i \} =$ {キュアマリン(青), キュアピーチ(桃), キュアピース(黄), キュアフローラ(桃), キュアミント(緑), キュアエース(赤), キュアマーチ(緑)}
ですが,$Y$ には既に緑のキュアミントがいるので,$f$ の値は変化しません.

この例で分かるとおり,$X \subseteq Y$ を満たす2つの集合 $X$, $Y$ に新しい要素 $i$ を追加したとき,色の増え方は必ず ($X$ に対する増え方) $\geq$ ($Y$ に対する増え方) になります.これが上の定義が言っていることです.
つまり,劣モジュラ関数は,手持ちの集合が大きくなればなるほど増え方が鈍っていく関数*1です.

ちなみに,この関数は $X \subseteq Y$ ならば $f(X) \leq f(Y)$ という性質(単調性)も持っていますが,劣モジュラ関数が必ず単調であるとは限りません.ただし,以下で見るように,単調な劣モジュラ関数でも機械学習にたくさんの応用があります.

応用例: センサー配置問題

有名な応用としてセンサー配置問題があります.ここではセンサーの代わりにプリキュアを配置することにしましょう.賢いゆいちゃんは,街にゼツボーグが出てきたときのために,プリキュアを事前に配置して迎え撃つことにしました.過去の出現パターンから,ゼツボーグが出てくる可能性のある場所(候補点)はある程度絞り込めたとします.

プリキュアは人目についてはいけないので,配置できる場所は限られますが,ある程度の範囲ならプリキュア1人でカバーできます.さて,4人のプリキュアをどこに配置したら最も多くの候補点をカバーできるでしょうか?

f:id:tasusu:20151130014227p:plain

たとえばこんな配置が考えられます.この配置だと9箇所カバーできています.
f:id:tasusu:20151130014335p:plain

この例では $E$ をプリキュアを配置できる座標の集合, $f(X)$ を配置 $X$ によってカバーされる候補点の数とすると,実は $f$ は単調な劣モジュラ関数になります.そして,この問題は

$|X| \leq 4$ という制約のもとで $f(X)$ を最大化せよ

という問題になります.

このように単調な劣モジュラ関数 $f$ に対して

$|X| \leq k$ という制約のもとで $f(X)$ を最大化せよ

という問題は,単調劣モジュラ関数最大化と呼ばれ,貪欲法とよばれる非常に実用的なアルゴリズムが知られています.

貪欲法は,$X = \emptyset$ からスタートして,$f(X \cup \{s\}) - f(X)$ が最大となる $s$ を選んで $X$ に追加することを $k$ 回繰り返すだけの非常にシンプルなアルゴリズムです.
しかしながら性能は驚くほど高く,理論的には最悪でも最適値の 1-1/e ≒ 63% の解を出力することが保証されており,経験的には最適値の90%〜ほぼ100%に近い解を出力します.
貪欲法のおかげで,単調劣モジュラ関数最大化は「実用上解けるNP困難問題」として

  • 線形回帰モデルにおける変数選択
  • 文書要約
  • 感染型マーケティング

などに幅広く応用されています.

書籍・リンク

実は,劣モジュラ関数の研究者の中には日本人研究者が数多くいます(私もその端くれ).残念ながら,Web上の日本語情報は多くありませんが,いくつか紹介しておきます.

  • NIIの吉田さんによる「劣モジュラ関数最大化」に関するPFIセミナーの動画.


Live stream by Ustream

  • 劣モジュラ関数研究者では知らない人はいない,藤重先生の動画.

機械学習プロフェッショナルシリーズにも,もうすぐ劣モジュラ最適化の本が出ます.

劣モジュラ最適化と機械学習 (機械学習プロフェッショナルシリーズ)

劣モジュラ最適化と機械学習 (機械学習プロフェッショナルシリーズ)

英語の情報は http://submodularity.org がよくまとまっています.過去のICMLなどのチュートリアル動画へのリンクがあります.

追記

2015/12/1 09:20 誤植を直しました(a_macbeeさん,Taiki_Aさんの指摘).

*1:限界効用逓減性(げんかいこうようていげんせい)とも呼ばれます.漢字難しすぎだろJK・・・