CREST加藤プロジェクト御紹介
Advanced Core Technologies for Big Data Integration
ビッグデータ統合利活用のための次世代基盤技術の創出・体系化

Foundations of Innovative Algorithms for Big Data
ビッグデータ時代に向けた革新的アルゴリズム基盤
Naoki Katoh (Kwansei Gakuin Univ.)
加藤 直樹 （関西学院大学）

Dec. 25, 2017
Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei Gakuin Univ.）

1. Objective•

Due to huge size of big data, polynomial timealgorithm paradigm becomes obsolete.

•So, we propose a new paradigm

Sublinear Time Paradigm

Run timelog n √nnn log nn2n3

Data sizeBinarysearchLinear searchSorting

Shortest path

Max flown=1000 10301000

1000

106

109

n=106 201000

106

2×107

1012(1兆)1018≒317years

n=109(Web 3030000

1093×1010≒300 Sec.

1018≒317 years

n=1012 401061012 =10000 4×1013
Sec.
≒111 hours

n=1015 50

3×107

1015=107Sec 5×1016≒110days ≒5500 days

n=1018 60(100京)

1091010 Sec
6×1019≒10 Sec. ≒317years. ≒19000yearsservers)

Foundations of Innovative Algorithms for Big Data(※)Assumption:
108 calculations need 1 second.

Naoki Katoh（Kwansei Gakuin Univ.）

Project Overview
Foundations of Algorithm Theory for BIG DATAProtein function analysis
by combinatorial rigidity
theoryFully Dynamic
Connectivity Oracles on
Dynamic GraphsO(n log n) timealgorithm for themaximum total andpartial composition
ordering problems

Quantum Computation
to Big Data Analysis

Linear Time Algorithm
for Probabilistic Image
Restoration

1. Foundations of Sublinear Time Algorithm (Katoh group)
2. Foundations of Sublinear Data Structures (Shibuya group)
3. Foundations of Sublinear Modeling (Tanaka group)
Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei Gakuin Univ.）What is sublinear?

Sublinear Time Algorithm
Running time: O(n2) ⇒ O(n) ⇒ O( log n) ⇒ constant time

Sublinear Data Structure
Data size: O(n) size ⇒ O(I) size (I: information quantity)
Index size:⇒ o(n) size

Sublinear Modeling
Model dimension: O(n) size ⇒ o(n) size

Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei Gakuin Univ.）

Project Overview

Targets of our project:
Innovation is required for developing algorithms that can cope with big data
1. Sublinear Time Algorithm: Exploring the next-generation computation model thatsupersedes statistical theory and machine learning
2. Data Structure for data compression: Developing the methodology for compressing data
to the limit of theoretical lower bound that simultaneously allows efficient random access3. Statistical-Mechanics based information processing: Establish principle andmethodology for coarse graining of information and super efficient knowledge extraction
from big data

Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei Gakuin Univ.）

Te a m A ： S u b l i n e a r - T i m e A l g o r i t h mTheory• Constant-time algorithms for big data forpractical use• Development of linear time algorithm

Applications• Protein function analysis based on
combinatorial rigidity theory• Evacuation problems

Software development• Foundations of innovative algorithm forbig data

Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei Gakuin Univ.）

Results of Sublinear time algorithm group (Team A)
Protein function analysis by combinatorial rigidity theory
Allostery analysis in Enzymes (the paper was acceptedin ”Science” )O(n log n) time algorithm for the maximum total and partial
composition ordering problems (the computational complexity has notbeen known before) (ISAAC 2016, Best paper award)

Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei Gakuin Univ.）Key difficulties in studying protein flexibility: Proteins motions occur
on many time scales

FUNCTION,Allostery

Molecular Dynamics
Simulations

RIGIDITY THEORY METHODSFoundations of Innovative Algorithms for Big Data

breakthrough technology
for protein function analysis

Naoki Katoh（Kwansei Gakuin Univ.）

Rigidity transmission allostery (RTA) algorithm in the role ofallostery in enzyme catalysis

A Story of an enzyme and how
fluoroacetate breaks one ofNature’s strongest covalent bonds…

Catalysed reaction
Sljoka et al Science, (2017)

Enzymes (catalysts) greatly accelerates chemical reactions by lowering of activation energybarrier (energy required for the reaction to start) without undergoing any permanent change

Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei Gakuin Univ.）Team D Strategy: Sublinear Data Structure Research from 3 Approaches
Information Theory-based Approach
Big Dataof Size n

Enumeration-based Approach
Description forenumeration

O(I)compression(I:informationquantity)

How to enumerate?
How to represent?

Enumerated outputs of"big-data size"Newparadigmo(n) -sizeIndexing

TakedaHow to index?
How to compress?

Sakamotoo(I) indexing /computation?

Sublinear-size
representation?

Big Data with
"Well-structured Data"

Tanigawa
Sakamoto

Sadakane

Kida

Shibuya

Yamagiwa

New sublinear data structure
paradigms for Big Data
Yada

NakanoSadakane

Protein 3-D data
NGS data
POS/sensor data

ShibuyaApplication-based Approach

Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei Gakuin Univ.）

Results (Oct 2015-, Sublinear Data Structure Team)• From theory-based approach• From application-based approach• Fully dynamic connectivity oracles– Protein 3-D Structures Dataon dynamic graphs (NakamuraAnnotation (Onodera, Shibuya 2016)2017)– Management science data analysis• Space-optimal grammar(Yada 2016, 2017)
compression (Takabatake, I,• Awards
Sakamoto 2017)• From enumeration-based approach• Enumeration of floor plans withregulations (Nakano 2016, 2017)

Foundations of Innovative Algorithms for Big Data

– IPSJ Yamashita Award (2017, as a co-author)– ISAAC Best Student Paper (2017)

Naoki Katoh（Kwansei Gakuin Univ.）Fully Dynamic Connectivity Oracles on Dynamic Graphs• The first algorithm
that supports
deletion/insertionof both vertices
and edges

𝐺𝐺

Preprocessing(Disjoint TreePartitioning)

𝐶Connected
Components

Edge-only update
Amortized
Deterministic
Randomized

Worst-case
Deterministic

2

log 𝑛
𝑂 𝑛loglog 𝑛Supports vertex updates
𝑶𝟐

𝐥𝐨𝐠 𝒏𝒎 𝐥𝐨𝐠 𝟏.𝟐𝟓 𝒏 + 𝒍𝐥𝐨𝐠+𝒏𝐥𝐨𝐠 𝒏[Nakamura ’17]

[Wulff-Nilsen ’13]

𝑂 𝑛 log 5 𝑛[Kapron et al. ’13]

𝑂 𝑛V’s Subset𝑶𝑛 log log 𝑛 2log 𝑛[Kejlberg-Rasmussen et al. ’16]
Foundations of Innovative Algorithms for Big Data𝒎𝒍 𝐥𝐨𝐠 𝟐.𝟕𝟓 𝒏 [Nakamura ’17]
𝑶𝒎𝒏 𝐥𝐨𝐠 𝟎.𝟕𝟓+𝜺 𝒏[Nakamura Sadakane ’17]
Naoki Katoh（Kwansei Gakuin Univ.）Team M: S u b l i n e a r M o d e l i n g f r o m S t a t i s t i c a l Me c h a n i c sresultour strategy
for Sublinear

fast statistical algorithm• mean-field approach• sparse modeling approach• quantum annealing approachprobabilisticsystemsmalldatacoarse graining• renormalization approach• statistical distribution approach

BIG DATA

existing study
image processing, network analysis, deep learning, …

Foundations of Innovative Algorithms for Big Datageneralization

A platform of sublinear modelingforgeneral BIG DATA
Naoki Katoh（Kwansei Gakuin Univ.）

Recent Results of Sublinear Modeling Group• Developing high-performance inference algorithm by the fusion of computational
theory and statistical approximation theory
 linear time algorithm for probabilistic image restoration[M. Yasuda, J. Watanabe, S. Kataoka, and K. Tanaka, arXiv:1710.07393 (2017)]
 fast test algorithm of noise robustness of deep neural network[M. Yasuda et. al., Proc. of NOLTA20117 (2017) ]• Estimating the performance of quantum annealing method for problems in big dataanalysis

Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei GakuinLinear Time Algorithm for Probabilistic Image Restoration
degraded image （σ = 30）

graphof Gaussian MRF

torus approximation

restored image（K = 8）

MSE = 906.17
PSNR = 18.56

MSE = 57.49
PSNR = 30.53

algorithm

time approximatio
nmatrix inversion

O(n3)DFT [K. Tanaka: 2002]

O(n2) torus approx.

DFT + FFT [N. Molin:O(n ln n) torus approx.

exact

2010]

proposed method

O(n)

exact

[M. Yasuda, J. Watanabe, S. Kataoka, and K. Tanaka, arXiv:1710.07393 (2017)]
Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei Gakuin Univ.）

Approach from Quantum Computation to Big Data Analysis
Approach
Query

ResponseDigitalcomputer

Quantumcomputer• Quantum annealing machine is a special purpose device
for combinatorial optimization problems• High power saving performance• Short computational time is expected

Community
Matrix interpolation
detection• Framework of quantum annealing is applied tocommunity detection and matrix interpolation• Estimate the performance using quantum Monte Carlo
method developed in statistical mechanics andquantum mechanics

ResultsIssues• Is quantum annealing useful for real-world problems?
• What type of problems can be solved efficiently?

How about problems in big data analysis
Foundations of Innovative Algorithms for Big Data

• Quantum effects
achieve fasterconvergence incommunity detection

Faster convergence
thanks to quantumeffects• Better solution is obtained for matrix interpolation
Naoki Katoh（Kwansei Gakuin Univ.）Future Plan of Our Project• Establish a Sublinear-time Algorithm Paradigm based on
constant-time algorithm for property testing• Develop a Sublinear Data Structure Paradigm basedon compression and succinct data structure theory and practice• Develop a Sublinear Modeling Paradigm based on coarse graining ofInformation based on statistical mechanics

Foundations of Innovative Algorithms for Big Data

Naoki Katoh（Kwansei Gakuin Univ.）

ポスター紹介量子反復条件付き最大化法による組合せ最適化問題への準量子的アプローチ
東北大学情報科学研究科 関 優也，田中 和之
組み合わせ最適化問題
指数関数的に多い選択肢の中から最適解を見つけなければならない
変数の数

510

100

200300解の候補数321024

1.3×1030

1.6×1060

2.0×1090

複雑なコスト関数の形状

局所的な最小値を抜け出すにはどのようなダイナミクスが良いか？

量子反復条件付き最大化法による組合せ最適化問題への準量子的アプローチ
東北大学情報科学研究科 関 優也，田中 和之
量子反復条件付き最大化法
従来法
熱ゆらぎを利用• シミュレーティッドアニーリング• 量子アニーリング• シミュレーティッド量子アニーリング

量子ゆらぎを利用• 反復条件付き最大化法• etc...

課題

適用先• より良い解への収束• 計算コスト• 更新クラスタのサイズによる性能差• 可解模型への適用
解への収束度合いを調べる• 画像修復やコミュニティ検出などの実用的な問題への適用ニューラルネットワークによる様々な相転移の検出
荒井 俊太 , 大関 真之, 片岡 駿, 田中 和之 (東北大 大学院情報)• １次元横磁場イジングモデルのスピン配位𝝈から横磁場Γを教師あり学習することで量子相転移を検出• 事前に相転移点を教えずに, NNの重みを見ることで相転移点が分かる→NNはスピンの画像から特徴を抽出し, 最適化の過程で横磁場で条件づけられた重みの確率分布を学習しているのでは?
+1Flatten(2)𝑊𝑘-1

横磁場を推定!
k+1𝝈 スピン配位(観測結果)

入力層 𝑳 × 𝝉

出力層 𝑵𝒄𝒍𝒂𝒔𝒔
隠れ層 𝑵𝒉• Predicted function• 秩序変数1 based on MLP
𝑊𝑚𝑒𝑎𝑛 (Γ 𝑘 ) =1𝐿𝑠𝑇
𝐿𝑠 𝟏 𝑾𝑘|𝑾𝑘 |𝑊Γ(𝑘) = 𝑎 tanh 𝑏 Γ − Γ + 𝑐

2𝑘 − 3
Γ 𝑘 =𝑁𝑐𝑙𝑎𝑠𝑠

量子相転移

強磁性

常磁性

隠れ層から出力層への重み

MLPの重みに基づく秩序変数1

Simulated Annealingを用いた
低ランク行列補完 三上譲治 関優也 大関真之 田中和之
東北大学大学院情報科学研究科

行列の穴埋めをしたい𝑀=125?
9 1013 14371115481216

低ランク行列補完：部分的に欠損しているデータ行列を，低ランク性を仮定することで補完する手法

応用先：商品のレコメンデーション，欠損画像の補完など
ランク最小化問題として定式化されるが，組み合わせ最適である
2017/12/25

WINTER FESTA2017

Simulated Annealingを用いた低ランク行列補完
組み合わせ最適を解く手法：Simulated AnnealingSAを用いてベクトルのスパース近似をする手法が提案された[1]𝒚 = 𝐴𝒙 + 𝝃
この手法を特異値して得られた特異値ベクトルに適応させることで，低ランク行列補完に応用する手法を考案した
結論：既存手法より補完できる領域が大きくなった• [1] T. Obuchi and Y. Kabashima: J. Phys.: Conf. Ser. 699 (2016) 012017
2017/12/25

WINTER FESTA2017

自己紹介: 九州工業大学大学院 修士1年 坂本研究室 大野達也
論文(IWOCA 2017で発表済み)
A Faster Implementation of Online Run-Length Burrows Wheeler Transform
共同研究者: 高畠嘉将 井智弘 坂本比呂志
巨大なデータ(Wikipediaのdumpなど)を圧縮したい
圧縮方法: Online BWT + 連長圧縮
連長圧縮: aaabbbb → a3b4
先行研究
• 省メモリで圧縮可能だが実装は遅い [Policriti et. al. 2016]• 時間計算量 O(n lg r lg σ) 空間計算量 O(r lg n)
提案手法
• 高速化
• 時間計算量 O(n lg r) 空間計算量 O(r lg n)n: 入力文字数
r: 圧縮サイズ
σ: 文字種類数

実験結果: 最悪: 最良

PP: 先行研究
ours: 提案手法
datasetdata size[MB] computation time [sec] working space [MB]ours

PPourPP

einstein.en.txt

445.963

182

9,293

4.836

2.296

world_leaders44.792

17857

9.335

2.891

kernel246.011

146

5,333

41.75812.510Esherichia_Coli

107.469154

2,047 316.184

36.655para

409.380547

7,364 329.901

52.005influenza

147.63791

2,501

12.386

1/50 ~ 1/13倍

72.7302~9倍

定数時間性質検査アルゴリズムの実用化を目指して
ー複雑ネットワークの超有限性の検証ー
本田裕太郎*1 伊藤大雄*2 加藤直樹*3 笹嶋宗彦*3 宇野裕之*1*1大阪府立大学*2電気通信大学*3 CREST 加藤PJ・関西学院大学• 研究目的：実世界をモデル化した複雑ネットワークに対する定数時間アルゴリズムの開発：SNS, 電力網,…
• 動機：– HSF(Hierarchically Scale-Free Multigraphs) : 複雑ネットワークをモデル化したグラフクラス，超有限性を備える[Ito, ESA16]– 超有限性を備えるグラフにおいては任意の性質が定数時間検査可能である[Newman & Sohlar, STOC11]– 複雑ネットワークが超有限性を備えていれば複雑ネットワークに対しても定数時間アルゴリズムは効果的なのではないか？
確率2/3以上で受理

P

ε-far

確率2/3以上で拒否
例：グラフの連結性を定数時間アルゴリズムで検査するイメージ本発表：複雑ネットワークの超有限性についての実験
ρ超有限グラフ

連結成分の接続辺数 < εnG: 入力グラフ
n: 頂点数連結成分の頂点数 < ρ(ε)• 実験方法：既知のアルゴリズムを一部修正したものを複雑ネットワークに適用し，ρ(ε)を理論値と比較する• 実験結果：– 格子グラフ(次数制限かつマイナーフリーグラフ)：理論通りの値– 平均次数が低く，平面に近い複雑ネットワーク：HSFの理論値より良い値，超有限性を備える可能性がある– 少数の高次数頂点を含み，平均次数が高い複雑ネットワーク：これまでの実験では，超有限とは言えないReconfigurationof Maximum
Weightb-Matchings
in a Graph≪ 分野 ≫
グラフ・アルゴリズム
無向グラフのb-マッチング

岡本 吉央 (電通大)
である
共同研究者

伊藤 健洋 (東北大)垣村 尚徳 (慶応大)神山 直之 (九大)小林 佑輔 (筑波大)じゃないReconfigurationof Maximum
Weightb-Matchings
in a Graph≪ 分野 ≫
グラフ・アルゴリズム
最大重み b-マッチングの遷移（辺のつけかえによる）

岡本 吉央 (電通大)
共同研究者伊藤 健洋 (東北大)垣村 尚徳 (慶応大)神山 直之 (九大)小林 佑輔 (筑波大)できる？ できない？ どうやって判定？

道具：線形計画問題の双対性