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

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

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

最適モデリング
モデル

モデル

現象・問題

最適モデル
モデル

モデル

数値解
最適解

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

マトロイド Whitney (1935)

最小基本方程式

甘利 (1962)

伊理 (1968)

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

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

最小指数混合方程式

岩田・高松 (2010)

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

岩田・高松・Tischendorf (2012)

研究計画
H26.10

H29.3

H32.3

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

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

主要研究成果① 微分代数方程式の最適モデリング
重み付き線形マトロイド・パリティ (STOC 2017, Best Paper Award)
微分代数方程式の指数減少法② 統計的モデリングの最適化
離散DC計画問題の連続緩和法(MPB 2017)

DC計画法によるスパース最適化 (MPB 2017)③ 大規模ネットワークの情報圧縮
低ランク行列基底問題 (MPA 2017)
ランダム正則グラフの直径 (SODA 2018)④ 生命現象の数理モデリング

シロイヌナズナの概日時計の階層構造 (Cell 2015)
蝙蝠の採餌行動時の飛行経路 (PNAS 2016)⑤ 社会システムの最適モデリング
優等列車停車駅の最適化による混雑緩和 (ATMOS 2017)

線形マトロイド・パリティ𝑉

𝑉: 線（2要素の組）に分割
パリティ集合: 線の和

𝐴=𝑋
最大最小定理多項式時間解法

最大独立パリティ集合
Lovász (1980)
Lovász (1980), Gabow and Stallmann (1986)
Orlin and Vande Vate (1990)

応用
RCG 回路の構造可解性
Milic (1974)
平面トラス構造の剛性
Lovász (1980)
グラフの閉曲面への埋込み Furst, Gross, McGeoch (1988)
グラフ上の内点素路
Lovász (1980), Schrijver (2003)

RCG回路の一意可解性
抵抗キャパシタη𝑅𝐶η𝜉𝜉
𝜂
𝜉=𝑅d𝜂
𝜉=𝐶d𝑡

ジャイレータ

𝑔

η1η2

𝜉1𝜉20
𝜉1=𝑔
𝜉2−𝑔 𝜂10 𝜂2

一意可解 ⟺ 各ジャイレータの両方の枝を含むか両方とも含まない全域木が存在する→ 判定問題が線形マトロイド・パリティに帰着される．
過渡解析の微分代数方程式の指数の計算には，重み付き線形マトロイド・パリティを解く必要がある．

重み付き線形マトロイド・パリティ
𝑤: 𝐿 → ℝA

𝑤 𝐵 ≔ ෍ 𝑤(ℓ)ℓ⊆𝐵B

最小重みのパリティ基
乱択擬多項式時間解法

Camerini, Galbiati, Maffioli (1992)
Cheung, Lau, Leung (2014)

応用
Steiner木問題の近似解法 Prömel and Steger (2000)
総路長最短の内点素路
Yamaguchi (2016)主結果と方法𝑂 𝑟𝑛3 回の算術演算で重み付き線形マトロイド・パリティ問題 を解く
組合せ的多項式時間アルゴリズム• 歪対称多項式行列による定式化.
• 組合せ緩和法 Murota (1990).
• 増加道アルゴリズム Gabow & Stallmann (1986).
S. Iwata and Y. Kobayashi, A weighted linear matroid parity algorithm,
Proceedings of the 49th ACM Symposium on Theory of Computing(STOC), 2017, pp. 264-276.

The Diameter of Dense Random Regular Graphs
Nobutaka Shimizu(to appear in SODA ’18)

The University of Tokyo‣ Gn,d : uniform random element from the set oflabelled d -regular graphs of n vertices.
diam(Gn,d ) := DIAMETER = ??

‣ Application to designing of network topologies.

A 3-regular graph‣ Bollobás and de la Vega (1982) :log ndiam(Gn,d ) ⇡log(d 1)for constant d3.

as n ! 1

NOT KNOWN FOR d = d(n) = !(1).

‣THIS WORK :lim diam(Gn,d ) = b↵ 1 c + 1n!1

ford/n↵Algorithms for k-submodular secretary problems

Kaito Fujii (UTokyo)

Combinatorial
Combinatorial secretary
secretary problems
problems[Kleinberg’05]

We want to hire the best combination of candidates

Interviewing from left in random orderAt each arrival, we must decide whether to hire,
and this decision cannot be revoked

The number of candidates is known in advance1/ 2

Algorithms for k-submodular secretary problems

Kaito Fujii (UTokyo)

We want to hire multiple positions at the same timee.g.) not only secretaries, but CTO Secretary

Interviewing from left in random orderCTO

We formulate this problem as

k-submodular secretary problems
We propose algorithms for several constraints

2/ 2

Index Reduction for
Differential-Algebraic Equations
with Mixed Matrices
大城 泰平（東京大学）
joint work with 岩田覚 教授（東京大学），高松瑞代 准教授（中央大学）微分代数方程式
Differential-Algebraic Equationfi (t, x(t), ẋ(t), ẍ(t), . . .) = 0(i = 1, . . . , n)指数が高い DAE は数値的に解きにくい！
数値計算の前に，低指数の DAE に変換したい
問題点
グラフアルゴリズムを用いた既存手法 [Mattsson−Söderlind ’93] では，数値キャンセルに起因する失敗が起こることがある．

本研究で与えたアルゴリズム
定数係数線形 DAE

入力

NX

Ak x(k) = f (t)k=0

ここで各 Ak は混合行列

出力

入力と同一の解を持つ低指数の DAE
🌸数値的要素（正確な定数）と混合行列

🌿組合せ的要素（非精確なパラメータ；物理量）を持つ行列

キーワード：組合せ緩和，マトロイド，組合せ行列理論

Study the Network Development Patterns of Brain by Graph Theory
DUAN Fang* and Kazuyuki Aihara
Institute of Industrial Science, the University of TokyoL2N i  j i 1 dij
N ( N  1)

C aij a jm ami
 2
 i j k m(kj 1 1)
Nii
NEi 11N  1 i  jG d i , jki ai  jGi, j

Correlation maps between the nodal level indices and the achievement scale.

(M. Kikuchi et al, 2011)

Correlation coefficient between the small-world scalars and the raw scores of K-ABC.

The well-functioning brain was better able to drive the functional network structure towards
increased efficiency in local.

Network Development Patterns of beta-band neural rhythm.

Nina Sviridova
Institute of Industrial Science, The University of Tokyo, Tokyo, Japan➢➢➢➢Results

M&M: Lorenz model and local noise sensitivity

Introduction
PPG is widely used in clinical settings and sport equipment
PPG can be recorded with green (gPPG) and NIR light, but gPPG ismovement artifacts resistant
PPG is chaotic
has short-term and doesn’t have long term prediction
noise doesn’t affect its trajectory equallyImprovement of PPG prediction can benefit health monitoring areaxሶ = −σ x − y ,ቐyሶ = ρx − y − xz,zሶ = xy − βz,
σ = 10, ρ = 28, β = 8/3

The Local Translation Error (LTE) => determinism of the signal :𝑒𝑙𝑜𝑐 =𝑣𝑗 − 𝑣
1σ𝑘𝑘+1 𝑗=0𝑣 22,

where x0 is a fixed and arbitrary chosen vector on reconstructed trajectory, xj(j=1,2,…,k) are its k nearest neighbors, yi are images of xi (i=0,1,…,k), vi = yi–xi
is translation vectors, 𝑣 is the average of 𝑣𝑗 .

M&M: gPPG➢➢➢

Data were collected from six 20-40 year old healthy humansubjects.
Finger reflectance-type recorder based on Arduino UNO
board, with sensor equipped with green-light LED.
Data recording was conducted in a sitting-relaxed position,in quiet air-conditioned room with moderate light.

y1(t+p)y(t+p)𝑘

𝑀𝑡 =1
෍ 𝐿𝑇𝐸(𝑥𝑖 (𝑡))
𝑘+1

x1(t)

x(t)

𝑖=0

𝑀𝑡 is compared with averaged
LTEs of preceding points andits neighbors – Mt-j (j=1,..,l).
The point 𝑥0∗ with the smallest
value M is chosen as a newpredictee; if j>0 then theprediction is conducted for(p+j) steps.

x(t-j)

1Results

DNP: y 𝑡 + 𝑝 = 𝑥 𝑡 + σ𝑛𝑖=1 𝜗𝑖 ,𝑛

WDNP: 𝑦 ∗ 𝑡 + 𝑝 + 𝑗 = ቀ𝑥 𝑡 +Acknowledgement. Theauthor would like toacknowledge Dr. Zhao Tiejun
from National Agriculture andFood Research Organization(Tsukuba, Japan) for providing
PPG data for this study.

1+ σ𝑛𝑖=1 𝑦𝑖∗ 𝑡 + 𝑝 + 𝑗 − 𝑥 ∗ (𝑡 − 𝑗) ቁ ,𝑛Local noise sensitivity7 in gPPG. Distributionof local determinism along a time-delay
reconstructed gPPG trajectory for typicaltime-series from a subject in 20s, thetranslation error is 0.16

The correlation coefficient between original and predicted gPPG time series for
direct prediction (blue dashed) and modified prediction (red solid line).

CONCLUSION
In this study modification ofdeterministic
nonlinearprediction based on theinformation regarding theeffects produced by noiseon the dynamics of thechaotic
signalwasproposed. The obtained
results demonstrated thatapproachtoaccountpresence of additive noisein the data and its effect on
the data dynamics canprovide an improvement in
the prediction of chaotic
Lorenz model. For thegPPG case, only a slightprediction
improvement

was achieved for thenumber of prediction steps
close to the heart cycle
time. Based on the results
for the Lorenz system it canbe noticed that for thegreater amount of noise indata, suggested prediction ismore beneficial. It is
important to notice thatwhile the Lorenz model
data were artificially noiseinduced, the raw signal wasusedforcalculations
corresponding to the gPPG
data. Therefore the further
investigation required for
improvement of the gPPG
prediction.

Envy-Free Matchings with Lower Quotas

横井 優 (国立情報学研究所, CREST 岩田プロジェクト)
選好 h2 ≻ h1 ≻ h3d1

𝐷: doctors

選好 d5 ≻ d1 ≻ d4 ≻ d3
上限制約 𝑞h1 : 2𝐷 → 𝐙+
下限制約 𝑝h1 : 2𝐷 → 𝐙+

d2

h1

d3

h2d4d5h3

上下限制約を守りながら各人の選好に考慮しながら マッチングしたい

𝐻: hospitals

目標：Envy-freeマッチングの存在判定 & 発見𝑑ℎ ≻𝑑 (現割当)𝑑′ℎ• 𝑑 ≻ℎ 𝑑 ′• (現割当)+𝑑 − 𝑑 ′ が上下限制約を満たす

𝑑 は 𝑑 ′ に対して justified-envy をもつ

結果： Envy-freeマッチングの存在判定は一般にはNP-hard,上下限がparamodularなら (i.e., 実行可能域がM♮凸なら) P.
系：上下限制約が層族上に定義されている場合は効率的に解ける

2