研究室紹介，北大, 情報知識ネットワーク研究室

研究テーマ（有村）n 北大大学院情報科学研究科，教授
A

n 専門：

BA
A

l データマイニング
l 情報検索（とくに全文テキスト索引）
l 計算学習理論（機械学習）

C

B

A
A

B

n 興味があること
l 膨大なデータから，人間に役立つ情報と知識をとりだすこと
l 高速なアルゴリズム（プログラム）を設計すること

n 趣味
Daisetsuzan, H. Arimural 読書・音楽鑑賞・ハイキング・家庭菜園の手伝い
2020.10.13

42022.10.03

A

n 情報検索（「文字列」 - ）l 文字列，木，グラフ，集合族，．．．
l 検索・比較・発見・圧縮
l アルゴリズムとデータ構造

n データマイニング
l 列挙アルゴリズム： 多数の解をもれなく計算する
l 構造・パターンマイニング

n 機械学習（計算学習理論）
l 信頼されるAI（公平性・説明性）
l 離散機械学習（決定木ほあｋ）
l 効率良い学習アルゴリズム
研究室紹介，北大, 情報知識ネットワーク研究室

BAA

やりたいことC

B

A
A

B• 膨大なデータから，人間に役立つ情報と知識をとりだす• 高速なアルゴリズ
ム（プログラム）を設計する

対象• 文字列・木・グラフ• 例：テキスト・遺伝情報, etc.
• 空間データ• 例：地理・移動・音楽・???
データ
5

2022.10.03

この研究室（IKN研）
n どちらかというと基礎
l アルゴリズムが中心（道具）l 情報は「形」「道具」の学問
l 先生方は二つの専門を持っている• 道具（How）：• 対象（What)：Web, Networks, 生命科学，機械学習，検索，データ解析．．．

l 現代は，いろいろなタイプの人が一緒にはたらくのがふ
つう：基礎・応用・人間/社会n こんな人l 考えるのが好き and/or 手を動かす
研究室紹介，北大, 情報知識ネットワーク研究室

6

21世紀の情報環境
情報世界
クラウド

l 大量のデータ
l 多数のＣＰＵl 高速なネットワーク
l 膨大な計算

「集中」
7

実世界
センサー

l さまざまなデバイス
l 多様な人間活動と応用
l 多様で非均一な時空間
l 不完全で複雑なデータと情報「分散」
2020.10.13

研究室紹介，北大,情報知識ネットワーク研究室
北大情報GCOE公開講座,
2012 OCT

大量データと次世代情報技術
ワトソン君
•••
•

クラウド計算IBMリサーチ (2011/02/16)
世界中の情報を計算！
クイズ番組で⼈間に勝利！
１００万冊の本を読んで回答
⼈⼯知能と⾃然⾔語，アルゴ
次世代IT（AI）の原動
リズム，検索の技術で力ハードウェア!
データ!
アルゴリズム!

米国の人気クイズ番組「ジョパディ！」のワトソン君
クイズ王に挑戦中

From http://www06.ibm.com/ibm/jp/lead/ideasfromibm/watson/

From geek.com: Google server firm
http://www.geek.com/articles/chips/up-next-for-google2020.10.13
8enterprise-wars-2009078/

研究室紹介，北大, 情報知識ネットワーク研究室

現代の人工知能データから規則を学習する機械学習技術が中核技術になっているData

機械学習アルゴリズム

現代のAI （データ指向AI）はデータに基づく意思決定のすべての局面をあつかう

Rule or ModelDecision

伝統的なAI は規則を使った意思決定だけをあつかう

Modification of: Sara Hajian, Francesco Bonchi, Carlos Castillo, "Algorithmic Bias: From Discrimination Discovery to Fairness-Aware Data Mining", KDD 2016, Tutorial

2020.10.13

92020.9.24 北海道大学，情研究室紹介，北大, 情報知識ネットワーク研究室

次世代の発見科学技術
有村君、21世紀の知識獲得は* 最新の⼈⼯知能技術
Deep Learningで* 21世紀はDeep Learningだけで⼗分か？
決まりかね？

l 21世紀の社会で、コンピュータが人間と働くために必要な人工知能技術とは何か？
有川節夫先生（私の先生）
2020.10.13

10KSSの研究 〜その１〜

5

信頼されるAIの基盤技術
なぜ？

えっ…

○○病

○○病

わからん

どうやって AI の導きだす回答を信頼させられるものにするか︖
Copyright © 2020 調和系⼯学研究室 - 北海道⼤学 ⼤学院情報科学研究院 情報理⼯学部⾨ 複合情報⼯学分野 – All rights reserved.

2020.10.13

研究室紹介，北大, 情報知識ネットワーク
研究室11

研究1︓予測モデルに対する反事実説明
Accepted at(Kanamori+, IJCAI2020)
IJCAI 2020

DACE: Distribution-Aware
Counterfactual Explanation byMixed-Integer Linear Optimization◯金森 憲太朗 （北海道大学）
高木 拓也（富士通研究所 / 理研AIP）

有村 博紀（北海道大学）小林 健（富士通研究所 / 理研AIP / 東京工業大学）

有村博紀，北海道大学, 2021

12

「信頼されるAI」講演会，日立製作所
2020/07/15

IKNゼミ

金森 憲太朗北海道大学1

有村博紀，北海道大学, 2021

「信頼されるAI」講演会，日立製作所

13研究室紹介，北大, 情報知識ネットワーク研究室

研究：人に優しい人工知能技術
K. Kanamori, T. Takagi, K. Kobayashi, H. Arimura, IJCAI-PRICAI 2020 (to appear)

離散最適化に基づく学
習p解釈性・説明性・公平性

機械学習の解釈性

llp反事実説明 (Kanamori+,IJCAI2020)「予測を×から○へ改善するためには，状況をどう変るべきか︖」

決定⽊を列挙!

+yes A > 2.5no
yesstarA ≦ 2.5

noquasar

yesstaryes A > 2.5no

yes A > 2.5no
B = "円"nogalaxyyesstarA ≦ 2.5

p解釈しやすい離散的ルールを学習する
pトップK・計数（数を数える）・列挙・乱択

noyesquasarstar

B = "円"nogalaxy

yes A ≦ 2.5nostarquasar

yes B = "円"nostargalaxy制約• サイズ• 葉の例数• 精度
2020.10.13

15

研究室紹介，北大, 情報知識ネットワーク研究室

研究：グラフアルゴリズム &列挙アルゴリズムによる知識発見

どんな構造が含まれているか，すべて挙げよ！
部分構造をすべてリストアップし，共通点や相違点を発⾒する

グラフ構造に抽象化

部分構造の列挙

列挙した部分構造から知識発⾒2020.10.13

16

研究テーマ：半構造マイニング「最右拡張技法」(高速半構造データマイニングエンジン

n 「最右拡張技法」に基づく高速な木パターン発見エンジン
llll

 Discovering all frequent sub-structuresfrom a colection of labeled trees
 Extendible to most statistical functions

半構造データの特徴的部分構造の発見
その後のグラフマイニングの基礎技術に理論と実装： FREQT, StreamT, Unot
SIAM DM'02, PKDD'02, IEEEICDM'02), DS'03公開＆応用

lCanonical form for unordered
trees (Left-Biased Tree)(Lexicographically largest trees
over depth-label sequence
encoding)
AT1
B FREQT: Efficient ordered tree miningA

engine (SIAM DM'02)

Applications
Applications

Rightmost Expansion &Ordered Tree Enumeration
Trees (SIAM DM’02, IEEE
ICDM’02, DS’03))

JapaneseJapanese Text
Text Mining
Mining(Morinaga,(Morinaga, Arimura
Arimura etet^al.,al., FIT'04,FIT'04, IBIS'04,IBIS'04,
FREQT:
DEWS'02優秀論文賞（H14年
submitting2005)
submitting2005)
Chemicalmining
Chemicalmining
6月）
engineering
Softwareengineering
Unot:Software
DEWS’04優秀論文賞（H16年6etc.
etc.
frequent

B

B

B

B

A

B

B
AA月）

A

B

infrequent

A

B
A

A

B
B

B

B

A

B

B

frequent

B

B

B
B
A

A

B

B

A

T2
B

＞

C

C

(0A,1B,2A,3C,2B,1B,2C)

B

Google Scholar
引用数(2019.4)[主要文献1] 596件

B

A

C

C

(0A,1B,2B,2A,3C,1B,2C)

Difficulties in unordered tree mining

AwardedAwardedExponentially manyll"無順序木マイニングエンジン
UNOT"
MaxMotif:
Awarded DEWS2004"無順序木マイニングエンジン
UNOT"
isomorphic patterns！
IEICE
DataEngineeringWorkshp
IEICE Data Engineering Workshp
nUnique representation？
（H17.6）Japan
Japan'04,'04,bestbestpaper
paperaward
award
nEnumeration without（房延・浅井・有村・宇野・中野,（ ’０３AI学会大会優秀賞
房延・浅井・有村・宇野・中野,JuneJune2004）
2004）
StreamT:
duplicates in a uniqueway
nEfficient computationof
17（H15.6）occurrences

17研究室紹介，北大, 情報知識ネットワーク研究室

コンピュータの学習の例
テキストマイニング︓* まず⼤量のテキスト（ブログでの評判や⾃由記述アンケート）を解析し，⽂の構造を「⽊」としてとりだす.
* 次に，共通する構造を発⾒（マイニング）すると，⽂書に隠れた共通の意⾒が取り出せる．
S社の入力のいろいろな文章
S社のメタルの「メタルのパネルが，S社の携帯はかっこいい」「今度のS社の携帯はパネルがかっこいい」

パネルが今度の携帯は携帯はS社のかっこいい共通したところだけを取り出す

かっこいい

変換

「昨日見たS社の携帯は開くパネルがかっこいい」

昨日見た

S社の携帯は見つけた共通意見

開くパネルがかっこいい

この仕組みは，企業でテキストデータの解析に使われた．

携帯はパネルが発見
かっこいい「S社の携帯はかっこいい」
森永, 有村, 池田, 坂尾, 赤峯,2020.10.13
18
FIT2004; ACM KDD2005.

人工知能技術の鍵！ = 機械学習技術

NIPS 2017（機械学習研究最大の学会）
Thirty-first Conference on Neural Information Processing Systems, Dec.
4-9, Long Beach Convention Center
Attracting over 8,000 registered attendees, up 2,000 from last year
Registration

exhibitionboothsession

Postersite

H.Arimura, December 2017.

19

研究室紹介，北大, 情報知識ネットワーク研究室

研究： ベイズ学習・トピックモデル(Ohama, Iida, kida, Arimura, IJCAI 2017, NIPS2017)
Relevance-dependent IRMheR

1.00.80.60.40.2(a) Synthetic Data

0.0(b) IRM solution(c) R-IB solution

1.0
0.8
0.6
0.4
0.2

Figure 3: Synthetic example: (a) 500×500 relational data; (b)• 従来手法（IRM）は、個々の人や商品の「活動度」に影響
IRM
solution;(c)
R-IB
solution.
In(b)and(c),
theleft
andされて本来存在しない、小さなクラスに分かれている。
!
topmatrices
indicatezandz• 提案手法 (R-IB) は、個々の活動度に影響されずに、大き12 in a 1-of-K representation,
な（正しい）クラスタ構造を見つけている
respectively.
Colored areas on matrices z1 and z2! indicate
relevance parameters for corresponding objects. For intuitive(a) Synthetic Data

0.0(b) IRM solution(c) R-IB solution

Figure 3: Synthetic example: (a) 500×500 relational data; (b)IRM solution; (c) R-IB solution. In (b) and (c), the left and
top matrices indicate z1 and z2! in a 1-of-K representation,respectively. Colored areas on matrices z1 and z2! indicate
relevance parameters for corresponding objects. For intuitive
understanding, a relevance parameter θ ∈ [0, +∞] is transformed into a probability as 1 − exp(− log(2) × θ), so thatthe probability is 0.5 when θ = 1.

description of the R-IB model, incorporating the R-BD to theobservation model of the IRM,!is as follows:2020.10.13 " 20
Ri,j | z, θ, λ ∼ Bernoulli 1 − e−θ1,i θ2,j λz1,i ,z2,j ,cC
ihave been
estimate iR∗ .
As z1,icentrate oCRP, giv
is assigne

P (z1,i =n∝γ

where thstatistic i
Converse
puted whFrom (yesnoyes

研究室紹介，北大, 情報知識ネットワーク研究室
star quasar star

研究：機械学習の研究* 決定⽊(decision tree)と⽊アンサンブル (勾配ブースティング，ランダムフォレスト) による⾃動分類▼決定⽊：対象を，その属性の値に従って分類する．基本は「すごろく」と同じ．条件式の値（YES/NO）にしたがって，根から葉までたどる．ゴールが分類クラス．
▼⽊アンサンブル：多数の決定⽊の予測を，多数決して全体の予測を決める．データサイエンス競技の常勝アルゴリズムの⼀つ+

属性値の条件式

A > 2.5yes

A ≦ 2.5

A > 2.5

noyes

B = "円"A > 2.5yesno

A ≦ 2.5

B = "円"A ≦ 2.5

noB = "円"

yesno

yesno

yesno

yesno

yesno

yesnostarquasarstargalaxystar

quasarstar

galaxystar

quasarstar

galaxy分類クラス名分類クラス名2020.10.13

21

22

研究テーマ：ビッグデータの検索
n 世界初の線形LCP配列計算アルゴリズム (CPM2001)
n 研究分野ベスト１０引用論文として表彰： 2010年に分野トップ会議(CPM) での「接尾辞木データ構造４０周年記念」集会で表彰

n CACM紙の「接尾辞木データ構造４０周年記念」特集で言及された： 「数十年以上の未解決問題を肯定的に解決し，接尾辞Google Scholar
引用数(2019.4)[主要文献2] 535件

配列と接尾辞木の相互変換のMissing Linkをつないだ」．

    Text
Data structures for efficiently storing
all of O(n2) substrings in O(n) space

Suffix tree(1976, McCreight)

ab1234a b c a$789(1990, Manber etal.)–Compactly
representrepresents
all the substrings
all theinO(n)space.
substrings with a 1-dimensional
1ca6b b c a $n Suffix
Suffix tree
array

integer array.

b5n

2

3

4

5

6

78

JSTさきがけ &特定領域「情報学」

b9

Problems
4 1 8 5 2 6 3 7 9

a– Nota spacea b efficient.
b b c c $$b cb– Dynamicb $ b reconstruction
c c a a isbac$b notc easy.c a a b $cbbaac– Nota suitablea bfor $ b8bbb$
7$b $ ca implementationb$ b on thecc
secondarystorage.
caa4$ bca5 a6$$ca$$a$
123$
Hiroki Arimura, Kyushu Univeristy
The Future of AI Workshop
ca

Efficient text mining algorithm using suffix
arrays. Direct use of d-dim Orthogonal
Range Tree Structure

9aa■b
Mean Height O(log N)

O(N log2 N) space / preprocess and O(log2 N) time per query■ improvement: O(N2 log2 N) < O(N3)The Future of AI Workshop

Hiroki Arimura,Kyushu Univeristy
2021.01.18、北大、有村博紀

研究室紹介，北大, 情報知識ネットワーク研究室研究：文字列アルゴリズムとデータ構造* ⼤規模テキスト・系列データを効率よく圧縮・検索・解析するためのアルゴリズムとデータ構造を研究する* ⽂字列・正規表現・⽊構造・NoSQLの検索アルゴリズム* 接尾辞⽊と接尾辞配列，BWT，テキストグラフ(DAWG)（⼆分探索⽊や，ハッシュ表，領域検索，RMQなどのテキストへの拡張）
LSTrie$a9

接尾辞⽊データ構造

d1bdba$6

テキストグラフ(DAWG
a bdcbcbcdbca cdd$
aa$$
52$

8

LCDAWG + SLP

X2

X1bcdd

X9$

a $

a$$
7

X4cc a

3X3dc

4

X5$

bc X8dX6dX7bc X11X10abcX14dd$
adX12$$aX13

X1 = aX2 = b
X3 = c
X4 = d
X5 = $ 
X6 = dX 7 = X 3X 6
X 8 = X 2X 7
X9 = $
X10 = aX11 = X2X7
X12 = $ ⽂法圧縮X13 = X10X12
X14 = X11X13
X15 = X8X14
X16 = X1X15
2020.10.13

23

Arimura+, 26 Oct. 2023, SPIRE2023

Optimally Computing CompressedIndexing Arrays Based on theCompact Directed Acyclic Word Graph
Hiroki Arimura1
Shunsuke Inenaga2
Yasuaki Kobayashi1
Yuto Nakashima2
Mizuki Sue1

1) Graduate School of IST,

Hokkaido University, Japan2) Department of Informatics,Kyushu University, JapanFor details and proofs, visits the arXIv site of this talk:• Manuscript at https://arxiv.org/abs/2308.02269 ;• Slide pdf at “Code section” or Github https://ikndeva.github.io )This work is partly supported by MEXT Grant-in-Aid for Basic Research A, 2000-2004, Japan

Backgrounds: Previous work

Arimura+, 26 Oct. 2023, SPIRE2023

n Consider the relationship between their sizes
l has been studied so far.

RL-BWTr𝑟≤𝑒

CDAWG𝑟 ≤ 𝑧 log2 𝑛Kempa &Kociumaka,STOC2021
25Bellazougui &Cunial
CPM2015e

LZ-parsez𝑧≤𝑒Bellazougui &Cunial
CPM2015

And many others (see survey by Navarro (CSUR, part i, ’21)

Arimura+, 26 Oct. 2023, SPIRE2023

Backgrounds: Previous work
n The time and space complexities of conversions
l have not been studied very much

RL-BWTO(z polylog(n))
timeKempa &Kociumaka,
CACM 2022

26r

LZ-parsezTime?
Time?

CDAWG

e

定理
[ 定理1 ]

Arimura+, 26 Oct. 2023, SPIRE2023

Research Goal:
提案アルゴリズムは,テキスト T[0,n), CDAWG CDAWG(T ) に対して,[ 定理1 ]We devise efficientthat solves theRLBWT(T )algorithms連長圧縮BWTを O(e) 語作業領域と時間で計算する.
提案アルゴリズムは, テキスト T[0,n), CDAWG CDAWG(T ) に対して,conversion
problem from the CDAWG for a text T
RLBWT(T ) を O(e)連長圧縮BWT語作業領域と時間で計算する.
intovarious compressedindexes
for T in linear time
2 3 4combined
5and index
space 0in1 theinput/output sizes$5Tindex c a0c1 a2o34

CDAWG
CDAWG

the conversion problemc a c a o $index
T Compressed

CDAWG

aA$

ca acao$27

2022/12/6
2022/12/6

1212oc$aB
RL-BWT
RL-BWT変換Conversion$ o$
cao$o$

変換

RL-BWT Compressed index

o1 c2 $1 a2

cao$
o$Time & Space complexity

Original text

コンピュテーション研究会
コンピュテーション研究会

LZ-parse

IrrPLCP

Irr-LPF北海道大学 須江瑞樹
北海道大学 須江瑞樹

8585

Arimura+, 26 Oct. 2023, SPIRE2023

Our approachn We use two orders of paths p Order for defining 2ndaryp Order for traversal

ForwardDFS

RL-BWTe

Ordered DFS from thesource in thelexicographic order2ndary edge=~same-letterrun

Bellazougui& Cunial
CPM201528

ReverseDFS
Ordered DFS
from the sink inthe text orderedgesp One for traversal of CDAWG

p Order for 2ndary

edges

GeneralizedLongest Previous
Factor Array
Navarro, Ochoa,[This work]n We generalize PLCP & LPF into

GLPF by the framework of (NOP’20)& Prezza (Trans.
Inf. Theory, ’20).

Lexparser

LZparserlength of thelongest upper
path =~irreducible
GLPF-value

Arimura+, 26 Oct. 2023, SPIRE2023

Sec5. Computing PLCP in O(e) time&space
CDAWG Gn Observation A1: O(e) secondary outgoingsourceedge of CDAWG(T) under the lengthlongest
order determines the irreducible value
pathPLCP[p] = l by the length l of the longest
Canonical
PLCP[p]path from the source to the= lsuffix
corresponding branching nodesecondaryoutgoingedge inlex-orderlex-firstpath

ReverseDFSsink29

n Observation A2: O(e) secondary outgoingedges can be enumerated in the text
order of its “canonical suffix” by thereverse DFS from the sink.

We can extend the above result from PLCP to PLPF
by employing the definition of 2ndary outgoing edges in length-orderおまちしています
情報知識ネットワーク研究室有村・{arim}@ist.hokudai.ac.jp
ex. 7678, 7679
33

研究室紹介，北大, 情報知識ネットワーク研究室 2020.10.13