Dec. 23 情報系 Winter FESTA at 一橋講堂

Outline
1. Background and Purpose
2. Project Initiatives
3. Major Results2

1. Background and Purpose
20th cent.

21st cent.

Computer
One of the Greatest Scientific Inventions

Big Data Era

Revolution
Data Volume

Revolution
Computational
Speed

Computer Science

The paradigm in 20th cent. Is obsolete!
ex) polynomial time ≠ fast
PARADIGM

Polynomial Time Algorithms

Computer Science

Urgent Task!

Sublinear Time Algorithms
3

2. Project Initiatives
Foundations of Algorithm Theory for BIG DATA

1. Foundations of Sublinear Time Algorithm (Katoh group)
2. Foundations of Sublinear Data Structures (Shibuya group)
3. Foundations of Sublinear Modeling (Tanaka group)4Research Groups
Katoh group(Sublinear Time Algorithms)

Ito

Takizawa

Yada

Sakamoto Yamagiwa Sadakane Takeda

Katoh

Makino Okamoto Yoshida

Kamiyama

Saito

Shibuya group(Sublinear Data Structures)

ShibuyaNakanoTanigawa Onodera

Kida

Tanaka group(Sublinear Modeling)
TanakaYasudaShiouraShinoharaItoGroup 1. Sublinear Time Algorithms
Base Theories

Breakthrough [Yoshida, Ito andothers]maximum matching, vertexconnectivity, sparsity matroid,
knapsack problem, etc:
constant-time randomized
approx. algorithm

Maximum Matching for
Bipartite Graphs

Practically efficient algorithm

6Group 2. Sublinear Data Structures
Base Theories

Information Theory-based Approach
Big Dataof Size n

Enumeration-based Approach
Description forenumeration

O(I)compression(I: information
quantity)

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

How to index?
How to compress?
o(I) indexing /computation?

Applications

How to enumerate?
How to represent?

Sublinear-size
representation?

New sublinear data structure
paradigms for Big Data FPGA Compression
 Management Information Data
 Protein 3-D Structure DB

Big Data with
"Well-structured Data"

ATTCAGCGTAAGGCCATTGCGATAGCCTTAAGCGCTAAAGTCGTGGCGCCTATCGATCTTGGACATTAACGCTCTGTAACTACAGGTAGCGGTATCGATC
ATCGTATTCTGATTCTTCTATCTTC
ATGGTGCTGCTGGTATACTCTACCC
TCTGGTGCATCAATAATCTCCGTGCTATCCAATAGGCTTTGCGCACTGATGroup 3. Sublinear Modeling from statistical mechanics
Statistical mechanics involves rich techniques for coarse graining of information.

low-dimensional data

BIG DATANew Paradigm of Sublinear modelingusing
Statistical Mechanics
andMachine Learning
Finding hierarchical structures of BIG DATA

(Hierarchical) Markov Random Field for Big Data
Structure inference of (hierarchical) MRFs generating Big Data
using statistical mechanical and machine learning techniques
Our recent theoretical developments:• mean-field theory for hierarchical probabilistic models (PRE, 2013; J. Phys., 2013; ICPR, 2014)• statistical machine learning theory for MRFs (Neur. Comput, 2009; ICPR, 2012)etc.

8

3. Major Results
A1. Constant-Time Algorithms for Complex Networks
A2. Modeling and Simulation of Umeda UndergroundMall toward Algorithmic Evacuation Planning

Poster

D1. Sublinear-Space Compression and Its Application
D2. Extraction of Characteristic Subgraphs from LargeScale Assembly Graphs

関連発表
Poster

M1. Information Coarse Graining using Renormalization
Group Theory with Application to Image Processing
M2. Detection of Sparse Structure in Big Data with
Application to Detection of Cheating Students

関連発表
Poster

加藤CREST関連ポスターは他にも２件、計５件あります。

Major results of Katoh group

A1. Constant-Time Algorithms for Complex Networks
A2. Modeling and Simulation of Umeda Underground Mall
toward Algorithmic Evacuation Planning

PosterA1. Constant-Time Algorithms for Complex Networks
Past Important Results

Target: Complex Networks

Dense-Graph Model:• Every hereditary property is
testable. [Alon et al. FOCS05]
Degree-Bounded Model:• Every minor-closed property is
testable. [Benjamini et al. STOC08]• For hyperfinite graphs, every
property is testable. [Newman & Sohler• Typical & important big graph data
• Includes web-graphs, social
networks, etc.
• Characteristics:• small world• high cluster• power-law degree distribution

STOC11]• → “sparse” and “degree
unbounded”

These algorithms cannot be applied.

We need new algorithms!

How to Model Complex Networks
CLUE
Isolated cliques [Ito & Iwama
05,09]:<kk vertices
Highly related with “high cluster.”[Uno & Oguri 11] [Shigezumi, Uno, Watanabe
11] observed the following facts: In typical realworld networks G,
1.G includes many isolated cliques,
2.G’ that is obtained by contracting all isolated
cliques of G has a similar structure, and3.The above operation can be appliedrecursively several times.

We introduce a new graph class HSF (Hierarchically Scale-Free Multigraphs)
If G is in HSF, theni.G obeys power-law degree distribution,
ii.G includes at least one isolated clique,iii.G’ that is obtained by contracting all isolated cliques of G also has theabove property (i) and (ii) if |G|≥c, which is a given constant.

Our New Results
Theorem [Ito 15]
HSF is hyperfinite*.
For this class, every property is testable in constant-time.
*Hyperfinite: A graph can be decomposed into constant-sized components by removing at
most εn edges (n is # of vertices).

Importance of this theorem:a)The first result on universal testers on the general (=sparse & degree unbounded)graph model.
b)By using this result (algorithm), whether a big complex network has any specified
property can be tested in constant-time.
Future work:• Practical usefulness: computer experiments by using actual data.
practical side
• Which property is easy to test in practice?
• Extending the theorem, e.g., cliques → dense subgraphs.
theoretical side
• Theoretical characterization of properties that are easy to test.

A2. Modeling and Simulation of Umeda UndergroundMall toward Algorithmic Evacuation Planning• Background• Frequent occurrence in recent years offlood and tsunami.
• Disasters become bigger and wider
areas are affected.
• Congestion and limited time for
evacuation.
• Need of the support for local
governments.

Prediction of flooding
area from Yodogawa• Purpose• Development of algorithmic
evacuation planning systems with big
spatial data and efficient algorithms.

• Agenda• Model big and precise spatial data.
• Perform general multi-agent
simulations.
• Development of efficient evacuation
planning algorithms.
• Unify and validate the data andmethods.

3D Model of Umeda Underground Mall by
Taniguchi Lab. at OCU

Data acquisition, modeling andmulti-agent based evacuation simulation• Characteristics of Umeda UndergroundMall• About 1.1km length of east and west side, northand south side, respectively.
• Composed of multiple malls and five stations.
• About 50 connected buildings and 150 entrances.
• More than 1 million passengers per a day.

• Difficulty on the data acquisition• Base 3D data has been developed by Prof.
Yoshiya Taniguchi at OCU.
• However, other spatial data are stored in a lot ofprivate sectors and difficult to get them.
• We could get them from flooding measureconsociation.
• Pedestrian data were partially available and we
did a field study for getting the remaining data.
• Performed as a benchmark with general method.
• Simulator: Simtread DXF version (A&A)• About 20000 evacuees evacuate to the nearest
connected buildings at 18:00 on a weekday.
• We can roughly grasp the evacuation time andcongested places.

Evacuees• Multi-agent based evacuation simulation

25000
20000
15000
10000
5000
0

0

5

10
15
Minutes20

25

Current achievements and future plans• Achievements (ongoing)• Modeled big and precise spatial
data.
• Performed general multi-agent
simulations.
• PR of the current simulation
result.

• Flooding measure consociation of
Osaka City Umeda UndergroundMall• Osaka Prefecture Police• NHK, News Terrace Kansai• NHK, Ohayo Nippon• MBS, Chichinpuipui• Yomiuri newspaper• Sankei newspaper• Mainichi newspaper• Nikkei newspaper

MBS Chichinpuipui, Sep. 1, 2015

• Future plans• Development of efficientevacuation planning algorithms.
• Unify and validate the data andmethods.

Map evacuation exercise on March 6, 2015

Major results of Shibuya group

D1. Sublinear-Space Compression and Its Application
D2. Extraction of Characteristic Subgraphs from Large-Scale
Assembly Graphs

関連発表
PosterD1. Sublinear-Space Compression and Its Application
Sakamoto & Yamagiwa• High performance compression withcompressed space• Wide applications: index, pattern discovery,
hardware implementation, etc.

• First online self-index• online construction• supports search and partial extraction
100~1000 times
scalability

output/input(%)• Hardware implementation

memory/input• FPGA (patent application)• Embedded Technology 2015 特別賞• VLDB BPOE workshop best-paper award

Background and Goal
• Rapid increase of streamdata• social media• demand for rapid printing oflarge digital data
• rapid communication ofsensing data
• rapid processing of image data

Platform of stream
computing• Progress of online
compression• not requiring whole data
• output linear workspace (notinput linear)• simple algorithm: scalable andfastBasic technology: algorithm• Grammar compression• Naïve method: parsing tree, pruning, andencoding• advantage：online friendly because of its
principle• dis-：compression ratio• Online and optimal encoding ofgrammar compression(sakamoto@presto, et al.)Basic technology: hardware• High-performance stream computing
environment (yamagiwa@presto)• Grammar comp. on FPGA
(sakamoto&yamagiwa, before crest)• advantage over previous methods• small circuit size
• 1CPU time compression• Prototype• fast communication by fixedsymbol table• speeding up by compression>transmission->decompression

After the beginning of CREST• First Online self-index• dynamic data structure• several times speeding-up(depending on memory size)• JST innovation Japan 2015
• patent application• VLDB2015 BPOE workshop
best paper award
offline• Embedded Technology 2015
特別賞

memory• first online self-index• small workspace• real-time detection of frequent pattern• Google code release• Hardware implementation

onlineinput-sizeD2. Extraction of Characteristic Subgraphsfrom Large-Scale Assembly Graphs[1] Wing-Kin Sung, Kunihiko Sadakane, Tetsuo Shibuya, Abha Belorkar and Iana Pyrogova,
An O(m log m)-time algorithm for detecting superbubbles, IEEE/ACM Transactions on
Computational Biology and Bioinformatcs, 12(4), July/August 2015.
[2] Taku Onodera, Kunihiko Sadakane and Tetsuo Shibuya, Detecting Superbubbles in Assembly Graphs,
The 13th Workshop on Bioinformatics (WABI 2013), LNCS 8126, pp. 338-348, 2013.
[3] Alexander Bowe, Taku Onodera, Kunihiko Sadakane and Tetsuo Shibuya, Succinct de Bruijn Graphs,
The 12th Workshop on Algorithms in Bioinformatics (WABI 2012), LNCS 7534, pp. 225-235, 2012.

de Bruijn graph and the SDBG (Succinct de Bruijn Graph)[Bowe, Onodera, Sadakane, Shibuya 2012]• DNA Assembly: Reconstruction of genome from NGS reads

1E+16• NP-hard problem / Input size: 300 Gbp

1E+15• de Bruijn graph: Large graph needed for DNA Assembly#bases

1E+14• SDBG: Our new data structure that stores de Bruijn graphin very small memory

1E+13
1E+12

Moore's Law（2x in 18 months）

1E+11• O(kn) → O(n), 300 bits/edge → 5 bits/edge
Single Reads

Size of the SRA database（10x in 18 months）

2013

2012

2011

2010

2009

2008

2007

1E+10

TAG

$$$

CGT
$$$T
$$T

Paired Reads

TAGT
$TAG

GTCG

AGTC

$$TA

AGT

TCGT

CGTC
GTC

TCG

$TA
AGTT

TCGA

GAGT

Assemble
GTT

GAG

CGAG

GTT$

Genome(contigs / scaffolds)

TT$

De Bruijn graph for$$$TAGTCGTCGAGTT$CGA

Knowledge Extraction from de Bruijn graphs• Subgraphs related to:• Multiploids, repeats, somatic variations, sequencing errors• O(m2) needed to detect naively

34• Intractablegcag tccta

tagatgcaagtgtagatacacag ta

3
tagatgcaagtgtagatacacag ta

28

2

6

cagtttgtattttttgttgagtgaatgt

ct

ccag t28
cggcacaaaaa

18

tatgaggaaaaacaggg

17

aggatatg

att

3

tagtttgtattttttgttgagtgaatgt

tggcacaaaaa

28

28

ttt

gagatgcaagtgtagatacacag

c

1

1

ata

28
cc atagagatgcaagtgtagatacacag

17

28

25
ctg gggaaaaaacaggg aggatatg

atat

a tgttttttgtt gagtgaatgtctccag

11

c

23

aaa agtttatgaggaaaaacaggg

agttcagttt

g ggttttttgtt

gagtgaatgtctccagt

11
ggttttttgtt

att

ata

agttcagttt

gtgttttttgtt gagtgaatgtctccag

3

3

10

1

27

25

Superbubble

gggaaaaaacagggaggatatgatt

4
attg

cggaaaaaacagggaggatatgatt

28

ata

aga

25
5
ta agaEfficient Algorithms[WABI2013, GIW2014]• Average-case O(m) algorithm• Utilize the statistical property of the graph• Practically very fast

• Around 12 min./1 CPU for human-size genome• Worst-case: O(m2)• Worst-case O(m log m) algorithm• Novel techniques that transform de Bruijn graphs totractable graphs

Keys to "Sublinear Big-Data Algorithms"• Utilization of statistical behaviors of the data
• Transformation of data to tractable data

Major results of Tanaka group
関連発表
Poster

M1. Information Coarse Graining using Renormalization Group Theory
with Application to Image Processing
M2. Detection of Sparse Structure in Big Data with Application to
Detection of Cheating StudentsM1. Sublinear Modeling:from statistical-mechanical point of view
Statistical mechanics involves rich techniques for coarse graining of information.
low-dimensional data

BIG DATANew Paradigm of Sublinear modelingusing
Statistical Mechanics
andMachine Learning

Finding hierarchical structures of BIG DATA

(Hierarchical) Markov Random Field for Big Data
Structure inference of (hierarchical) MRFs generating Big Data
using statistical mechanical and machine learning techniques

Probability + Approximation + Algorithm Create a new scheme of sublinear-time algorithms for Big Data

Information Coarse Graining using Renormalization Group Theory
P ( r ) (a) ∝1

Step 11

K(r-1)

 1 (r )

exp
,
K
δ
a
a
(
)
∏( r )  2ij {i , j }∈E
2

K(r)K(r-1)

3
3

Step 21

K(r-1)

4

K(r-1)

K(r)5
5

K(r+1)

K(r-1)

K(r-1)

6

K(r)

7
7

2



K ( r −1)
 q −1+ e
(r )= 4 lnK( r −1)/ 2 
 q − 2 + 2e Ky

 q −1+ ex 
y = 4 lnx/2
 q − 2 + 2e




q=8

y=x
K

Inverse Renormalization Method

K(1)

K(2)

x

Application to Bayesian Image Segmentation••

K. Tanaka, S. Kataoka, M. Yasuda, Y. Waizumi and C.-T. Hsu: Bayesian image segmentations by Potts priorand loopy belief propagation, JPSJ, 2014.
K. Tanaka, S. Kataoka, M. Yasuda and M. Ohzeki: Inverse renormalization group transformationin Bayesian image segmentations, JPSJ, 2015.

1728 Sec
Conventional Method
481 x 321

Segmentation by
Belief Propagation
for Original Image

30 x 20
Coarse Graining
Procedures

30 x 20 Labeled
Image

The new coarse graining method is
at least 10 times faster thanthe conventional method

101 Sec
Grand Truth

M2. Detection of Sparse Structure in BIG DATA
Finding sparse structures in BIG DATA is important topic for an analysis of BIG DATAe.g.) graph mining, data decomposition etc.

Find Sparse structure using
Extended Item Response Theory and Decimation Algorithm
Extended Item Response Theory (EIRT)
can detect characters of nodes and structure among nodes
Decimation Algorithm (DA)can detect Sparse structure among nodes

The method without DA (EIRT + L1 regularization)cannot detect a clear structure from data

optimal point of DA

detection error

Decimated pairs

The new algorithm can detect
the character of each nodeandthe sparse structure
among nodes

The new algorithm
succeeded to detectsparse structure in data

Application to detection of cheating students
S. Yamanaka, M. Ohzeki, A. Decelle: Detection of Cheating by Decimation Algorithm, JPSJ, 2015.
Newton 26th Feb. 2015

newspapers:
財経新聞, Jan. 2015
人民日報, Jan. 2015
朝日新聞, Jan. 2015
TV news coverage:
NHK, おはよう日本, Mar. 2015

Application to detection of cheating students
S. Yamanaka, M. Ohzeki, A. Decelle: Detection of Cheating by Decimation Algorithm, JPSJ, 2015.

• 27th March Broad casting from NHK「おはよう日本」

4. Summary
A1. Constant-Time Algorithms for Complex Networks
A2. Modeling and Simulation of Umeda UndergroundMall toward Algorithmic Evacuation Planning
D1. Sublinear-Space Compression and Its Application
D2. Extraction of Characteristic Subgraphs from LargeScale Assembly Graphs
M1. Information Coarse Graining using Renormalization
Group Theory with Application to Image Processing
M2. Detection of Sparse Structure in Big Data with
Application to Detection of Cheating Students

Steady ProgressPoster Presentations
複雑ネットワークに対する定数時間アルゴリズム

伊藤大雄

Online self-indexed grammar compression

高畠嘉将, 田部井靖生, 坂本比呂志

Direct Access to Variable-to-Fixed Length Codes
with a Succinct Index

喜田拓也

On Demand Calibrationを用いた広域歩行者追跡和泉勇治

超事前分布を用いた確率的領域分割モデルのパラメータ推定

古市智大，片岡駿，田中和之

Poster Presentations
複雑ネットワークに対する定数時間アルゴリズム

伊藤大雄

Online self-indexed grammar compression

高畠嘉将, 田部井靖生, 坂本比呂志

Direct Access to Variable-to-Fixed Length Codes
with a Succinct Index

喜田拓也

On Demand Calibrationを用いた広域歩行者追跡和泉勇治

超事前分布を用いた確率的領域分割モデルのパラメータ推定

古市智大，片岡駿，田中和之

複雑ネットワークに対する定数時間アルゴリズム「ビッグデータ時代に向けた
革新的アルゴリズム基盤」
ABD14 --- Team A
伊藤大雄
電気通信大学 大学院 情報理工学研究科
JST CREST
2016/3/7

ABD14全体会議

2

Back Ground and Our Target on Constant-Time Algorithms
Past Important Results

Target: Complex Networks

Dense-Graph Model:• Every hereditary property is testable.

• Typical & important big graph data
• Includes web-graphs, social
networks, etc.
• Characteristics:• small world• high cluster• power-law degree distribution[Alon et al. FOCS05]

Degree-Bounded Model:• Every minor-closed property is
testable. [Benjamini et al. STOC08]• For hyperfinite graphs, every
property is testable. [Newman & Sohler
STOC11]• → “sparse” and “degree
unbounded”

These algorithms cannot be applied.

We need new algorithms!

How to Model Complex Networks
CLUE
Isolated cliques [Ito & Iwama 05,09]:<kk vertices
Highly related with “high cluster.”[Uno & Oguri 11] [Shigezumi, Uno, Watanabe 11]
observed that if a graph G is a complex network,then:
1.G includes many isolated cliques,
2.G’ that is obtained by contracting all isolated
cliques of G has a similar structure, and3.The above operation can be applied recursively
several times.

We introduce a new graph class HSF (Hierarchically Scale-Free Multigraphs)
If G is in HSF, theni.G obeys power-law degree distribution,
ii.G includes at least one isolated clique,iii.G’ that is obtained by contracting all isolated cliques of G also has theabove property (i) and (ii) if |G|≥c, which is a given constant.

Our New Results
Theorem [Ito 15]
HSF is hyperfinite*.
For this class, every property is testable in constant-time.
*Hyperfinite: A graph can be decomposed into constant-sized components by removing at most εn edges(n is # of vertices).

Importance of this theorem:a) First results on universal testers on the general (=sparse & degree un-bounded)graph model.
b) By using this result (algorithm), whether a big complex network have any specified
property can be tested in constant-time.
Future work:• Practical usefulness: computer examination by using actual data.
practical side
• Which property is easy to test in practice?
• Extending the theorem, e.g., cliques → dense subgraphs.
theoretical side
• Theoretical characterization of properties that are easy to test.

Online self-indexed grammar
compression
高畠嘉将, 田部井靖生, 坂本比呂志

Online self-indexed grammar compression
高畠嘉将 (九工大), 田部井靖生 (JST PRESTO), 坂本比呂志 (九工大)
SPIRE2015 で発表済み• 繰り返しの多いテキストのための部分文字列の出現位置・回数を検索可能な索引• 例) 個人のゲノム、バージョン管理された文書やソースコード• 文法圧縮索引 = 繰り返しの多いテキストに有効• 通常の索引は入力テキストと索引が必要だが、文法圧縮索引は繰り返しの多いテキストを高圧縮率で圧縮したデータのみで省領域に検索可能• 既存の文法圧縮索引の構築はオフライン• 入力テキストが全てないと構築不可• 新たな文字を末尾追加する場合、一度データを解凍して、作り直すので入力長に依存した計算時間及び領域が必要• 圧縮データサイズに依存した領域かつ高速に新たな文字を末尾追加可能なオンライン文法圧縮索引を提案

オフライン圧縮索引との比較実験 (english text 446MB)• 圧縮領域で構築可能• 構築時間および検索時間は低下

構築領域（ＭＢ）
入力長• オンライン化のために遅いデータ構造を用いたため構築時間（sec）

検索時間（msec）

Direct Access to Variable-to-Fixed
Length Codes with a Succinct Index
喜田拓也

Direct Access to Variable-to-Fixed Length Codes with a Succinct Index
発表者： 喜田 拓也（北海道大学） 加藤CREST劣線形データ構造チームメンバー（チームリーダー：渋谷 哲朗）

・気象衛星データ
・航空写真データ

リモートセンシングデータ
Remote sensing data

GPS

Internet SNS・GPSログ・ライフログ・市民からの情報提供
・市民への道路情報の提供

ビッグデータ

GPSログ・ライフログデータ
GPS logs, Life logs

UGCデータUser Generated Content data

20120101000000,3,5.0,1,120,644132,00008,168933376,555574333,09853,168933408, ・・・
20120101000000,3,5.0,1,110,644132,00008,168933376,555574333,09853,168933408, ・・・
20120101000000,3,5.0,1,120,644132,00009,168989212,555755788,00036,168990785, ・・・・・・

Repair-VF： データ検索やデータ解析時に再利用しやすいデータ圧縮方式
高速なデータ展開

Repair-VF

圧縮したまま検索可能

優れた圧縮性能

Fully Indexable Dictionary (FID;完備辞書)
高速な部分文字列抽出を実現！

実験結果： 部分文字列抽出の速度比較
抽出位置 𝑝𝑜𝑠 を変化させたときの抽出時間（CPU時間）をプロット
FOLCA

既存手法（FOLCA）と比較して，１０倍以上高速に部分文字列を取り出すことができる
FIDを含めても圧縮率は同等
methodRVF+RRR
RVF+DA
RVF+SDAdna

proteins

englishRVF w/o index

28.43

46.27

30.53

RVF+DA

47.83

63.78

47.62

RVF+SDA

60.86

62.39

45.54

RVF+RRR

41.05

54.17

38.60

FOLCA

40.69

50.34

47.25

(% of the compressed size / the original size)On Demand Calibrationを用いた広域歩行者追跡
和泉勇治

On Demand Calibrationを用いた広域歩行者追跡
加藤CREST 劣線形モデリンググループ
東北大学大学院情報科学研究科 和泉勇治
• 避難シミュレーションにおける歩行者の初期位置の取得• 歩行者の初期位置と歩行の向きを取得• 歩行者検知＋追跡• より広域に歩行者を追跡し，高精度なシミュレーションの実現• 複数のカメラ画像に跨る歩行者追跡• カメラ画像間の共通領域が無い撮影状況での歩行者追跡• Non-Overlapping Fields of View

参照：合田祥子 「大都市地下街の津波避難計画に関する研究」

On Demand Calibrationを用いた広域歩行者追跡
加藤CREST 劣線形モデリンググループ
東北大学大学院情報科学研究科 和泉勇治•

カメラ毎の撮影状況が異なる–

共通色物体を利用した色の補正,•

W : Calibration Matrix: RGB values of Sampling Point

IoT/M2Mからのアプローチ–

自律的な情報交換••

追跡精度
53.03% → 71.12%•

トラヒック量––提案方式： 480kBps
中央方式： 14400kBps

超事前分布を用いた確率的領域分割モデルのパラメータ推定
古市智大，片岡駿，田中和之

超事前分布を用いた確率的領域分割モデルの東北大学大学院情報科学研究科
パラメータの推定
古市 智大，片岡 駿，田中 和之• 確率的領域分割[1]Pr A|αPottsPrior

Pr A|FPr F|A
分割画像 A• くりこみによる高速化[2]観測画像 F

2713[sec]
481×32164×41

α ＝3.171600[sec]
α ＝3.213• 問題点• くりこみにより平滑化パラメータの画像ごとの差異がなくなってしまう⇨平滑化パラメータの分布をモデルに導入
超事前分布
αf i x ＝3.229
64×41

α ＝2.489

α ＝3.213

α ＝3.461
超事前分布

α ＝18.931[1]K. Tanaka, S. Kataoka, M. Yasuda, Y. Waizumi and C.‐T. Hsu: Bayesian image segmentations by Potts prior and loopy belief
propagation, JPSJ, 2014.
[2] K. Tanaka, S. Kataoka, M. Yasuda and M. Ohzeki: Inverse renormalization group transformation in Bayesian image
segmentations, JPSJ, 2015.