CREST 「数理モデリング」領域

大規模複雑システムの最適モデリング手法の構築

岩田 覚（東京大学情報理工学系研究科）

数理工学の基本的な枠組
数値計算
最適化

モデル化

現象・問題

モデル

数値解
最適解

最適モデリングモデル

モデル
現象・問題最適モデル
モデル

モデル

数値解
最適解

回路解析における最適モデリング
混合解析 Kron (1939)

マトロイド Whitney (1935)

最小基本方程式
甘利 (1962)

伊理 (1968)

マトロイド理論の工学的応用

修正節点解析 SPICE (1973)
微分代数方程式モデルによる過渡解析
最小指数混合方程式

岩田・高松 (2010)

修正節点解析に対する混合解析の優位性
高松・岩田 (2010)

岩田・高松・Tischendorf (2012)微分代数方程式の最適モデリング
指数： 常微分方程式からの離れ具合→ 指数が高い程，数値計算が困難
電気回路網： 指数２以下
機械力学系： 指数３
化学反応系： より高い指数高い指数（≧２）の微分代数方程式の解法
隠れた制約式の導出

Pantelides (1988), Pryce (2001)

指数減少法の適用

Matsson, Sonderlind (1997)

統計的モデリング
統計的モデルの良さを測る尺度
情報量規準 AIC

赤池 (1973)

AIC = −2(最大対数尤度) + 2(自由パラメタ数)

AIC最小化によるモデル選択

組合せ爆発

多重線形回帰，グラフィカル・モデリング

離散ＤＣ計画

前原・室田 (2014)

離散凸関数（劣モジュラ集合関数）の差を最小化する近似アルゴリズム

大規模ネットワーク
ソーシャル・ネットワーク
感染症伝搬ネットワーク

評判の伝搬
流行の予測・予防時空間ネットワーク

物流・避難計画

巨大なネットワーク構造が入手可能
解析には莫大な計算資源本質の抽出・粗視化が必要
劣モジュラ関数の近似手法・学習理論

Goemans, Harvey, 岩田, Mirrokni (2009)
Balcan, Harvey (2011)

高階テンソルの分解手法

Tucker (1966), Kolda, Bader (2009)

研究計画
H26.10

H29.3

H32.3

最適化モデリング手法の開発① 微分代数方程式

社会システムへの応用
・電力システム・交通システム② 統計的モデリング③ 大規模ネットワーク生命現象の最適モデリング④ 生命現象の数理モデリング

遺伝子・タンパク質ネットワーク，代謝ネットワーク，神経回路網，感染症伝搬ネットワーク

優モジュラ関数に対するリスト彩色定理
岩田 覚 横井 優 （東京大学）
優モジュラ彩色[Schrijver 85]の枠組みへ

2部グラフのリスト辺彩色定理[Galvin 95]

本研究拡張

リスト優モジュラ彩色定理

1

2部グラフの辺彩色隣接する辺が同色になってはいけない

彩色数： 彩色に必要な色の数
辺彩色数= 32部グラフのリスト辺彩色定理[Galvin 95]

各辺が彩色数以上の色をリストにもつとき，リスト中の色で辺彩色可能
安定マッチング[Gale-Shapley 62] を用いた構成的証明2

優モジュラ彩色 [Schrijver 85]
3色２つの交叉優モジュラ関数が各部分集合に割当色数の下限を課す
成果：リスト優モジュラ彩色定理

4色3色

彩色数= 4

各要素が彩色数以上の色をリストにもつとき，リスト中の色で優モジュラ彩色可能
有向グラフのカーネルを用いた構成的証明（単色パス定理 [Sands, Sauer & Woodrow 82] を活用）

3

Regret Ratio Minimization in
Multi-objective Submodular Function Maximization
Tasuku Soma (Univ of Tokyo)

w. Yuichi Yoshida

Submodular Maximizationf : 2E → R+ submodular, C ⊆ 2Emaximize f (X )subject to X ∈ C

Useful in Machine Learning, Social Science, etc.
Motivation
What if we have multiple submodular functions?
1/2

IssueExponentially many Pareto optimalsolutions!
Our Approach
Choose k Pareto optimal solutions to minimize“regret”.
Our Result
1 Algorithms for minimizing regret ratio, given approxalgorithms for single-obj problems.
2 Lower bound for regret ratio.
2/2

岩田CREST

加速近接勾配法の改善と2値判別モデルの統一的解法への応用
伊藤直紀(東大) ・ 武田朗子 (統数研) ・ TOH Kim-Chuan (NUS)

JMLR採択済l 汎用的な最適化手法である加速近接勾配法 + 高速化の工夫
収束レート
Backtracking (Beck & Teboulle, ʻ09)

O(1/k 2 )Modiﬁed Backtracking (Scheinberg et al., ʻ14) O(1/k 2 )Restarting (OʼDonoghue & Candes, ʼ13)

unknown

Maintaining top-speed (Monteiro et al., ʻ15)

unknown

本研究組み合わせ + 安定化
O (log k/k)2l 統一的2値判別モデルを提案 ← 提案手法を適用•SVM・ロジスティック回帰・フィッシャーの線形判別器 などを含むモデル•

様々なモデルを既存手法より高速に解くことができた•

モデル選択をする上で有用A critical point of an intestinal dynamical
network and its association with aging in mice
DUAN Fang1, Shinji Fukuda2, and Kazuyuki Aihara1
1Institute of Industrial Science, the University of Tokyo
2Institute for Advanced Biosciences, Keio University

A Dynamical Network Biomarker (DNB) is abiomarker consisting of multiple genes/proteins with possible
interactions, that are selected based on their dynamics.
(L. Chen et al., Sci. Rep., 2012)
Low CI DNB
Attractors

High CI DNB
Critical Point

Low CI DNB

Schematic illustration

Attractors

Proposed for genetic and biochemical studies for clinical usage
Detect THE PRE-DISEASE (tipping point) state
Heal before ill!

Core issue: How to find the leading network?

We proposed DNB Landscape method and Local DNB Index
to avoid the opening question of leading network and mapping thelandscape of DNB. The 3 components of CI of node n were calculated
under reference network as follow:
𝑺𝑺𝒏 : Average standard deviations of node and first-order neighbors.

𝑹𝒊𝒊𝒏 : Average absolute PCCs between node and first-order neighbors.

𝑹𝒐𝒐𝒐𝒏 : Average absolute PCCs between node and random selected nodes

outside the network.

SDn Rinn
CI n =Routn

Nodes for calculate SD and Rin

Three type of nodes selection method for calculate Rout56 week

Common Reference Network

64 week

Critical point of aging at 60 week
60 week

20 week

16 week

Average Reference Network

24 week

Critical point of growing at 20 week

Found the critical points of the aging process of mice by biochemical data ofblood and feces in mice. We linked the aging process and intestinal microbial flora.