論文

競合型ニューラルネットを用いたオンライン準教師付能動学習手法
櫻井 啓介†

神谷 祐樹†† a)

長谷川 修††† b)

Online Semi-Supervised Active Learning Method Using Competitive
Neural Network
Keisuke SAKURAI† , Youki KAMIYA††a) , and Osamu HASEGAWA†††b)

あらまし 一般に，教師付学習は入力データと出力ラベルの組を用いて行われる．しかし通常，入力データに対する出力ラベルの付与は人手によって行われるため，コストがかかる．そこで，より少ない出力ラベルの付与でより良い学習結果を得るための学習法として，準教師付学習と能動学習が提案されている．本論文では，オンライン教師なし学習手法の一つである自己増殖型ニューラルネットワークに，準教師付学習と能動学習の機能を加えることにより，オンライン準教師付能動学習手法を提案する．また，計算機実験によって，提案手法が有効に働くことを示す．
キーワード

準教師付学習，能動学習，オンライン学習，自己増殖型ニューラルネットワーク (SOINN)

準教師付学習は，一部の入力データのみに出力ラベ

1. ま え が きルを付与し，それらのみから，入力データ全般の一般

一般に機械による学習は，教師付学習と教師なし学的な写像関係を推定する学習法である．準教師付学習

習に大別される．教師付学習は入力データとそれに対は，多数の入力データにラベルを付与するコストを削応する出力ラベルの組，すなわちラベル付データを用減できることから，近年注目されている．

いて，それらの間に存在する写像関係を推定する学習

また，より少ないラベルの付与で，より良い学習結である．推定した写像関係が正しければ，未知の入力

果を得るための学習法の一つに，能動学習がある．能データに対する出力ラベルを正しく予測することがで

動学習は質問学習とも呼ばれる．能動学習とは，これきる．一方，教師なし学習は入力のみ，すなわちラベまでの学習結果に基づいて，最も必要な出力ラベルを

ルなしデータを用いて，それらに包含される構造を推推定し，それを得ることによって，より効率的に学習定したり，いくつかの異なる概念に分類する学習であを行う方法である．

る．一般に，教師付学習によってより良い学習結果を

準教師付学習と能動学習は，ともに少ないラベル得るためには，多数のラベル付データが必要である．

付データを用いてより良い学習結果を得る方法であ

しかし通常，出力ラベルの付与は人手で行う必要がある．したがって，これらを組み合わせることで，更り，コストがかかるため，多数用意することは困難でに少ない出力ラベルの付与で良好な学習結果を得る

ある．

ことができると期待される．従来の準教師付能動学†

習法として，Generative Model [9]，Co-Training [2]，アップルジャパン株式会社，東京都

Transductive SVM (TSVM) [1] や GRF [12] 等が提Apple Japan, Inc., Tokyo, 163–1480 Japan†††††

東京工業大学大学院総合理工学研究科知能システム科学専攻，横浜市

案されている．また，これらの手法を拡張した準教師

Department of Computational Intelligence and System Sci-

付能動学習法も提案されている [7], [13]．これらの手

ence, Tokyo Institute of Technology, Yokohama-shi, 226–

法は，全入力データを用いて学習を行うバッチ学習で8503 Japan

ある．

東京工業大学像情報工学研究施設，横浜市
Imaging Science and Engineering Laboratory, Tokyo Institute of Technology, Yokohama-shi, 226–8503 Japana) E-mail: kamiya.y.ab@m.titech.ac.jpb) E-mail: hasegawa.o.aa@m.titech.ac.jp

電子情報通信学会論文誌 D Vol. J90–D

ここで実環境においては，システムは非常に膨大な数のデータを扱うことになる．それらのデータに対してバッチ学習を行うためには，そのすべてを蓄えておc （社）電子情報通信学会 2007
No. 11 pp. 3091–3102 

3091

電子情報通信学会論文誌 2007/11 Vol. J90–D No. 11

く必要があるため，膨大なメモリが必要である．そこ
で，学習データを入手するごとに学習機械が更新され，後の更新にはこの学習データを用いない学習法，すな
わちオンライン学習が重要になる．
そのようなオンライン学習の手法の一つに，Shenと Hasegawa によって提案された，Self-Organizing
Incremental Neural Network (SOINN) [11] がある．
SOINN は，それぞれのデータ間の距離，すなわち類似性に基づいて，データの分布をいくつかのクラスタに分ける，教師なしクラスタリングの手法の一つである．SOINN は，非定常的な入力を学習でき，複雑な形状の分布をもつクラスに対しても，クラス数などの事前知識なしに，適切なクラスタ数及び適切な位相構造を出力できる．
本論文では，こうした SOINN の機能を改良し，入力データの構造を自己組織的に近似・抽出しながら，
図 1 SOINN のフローチャート
Fig. 1 Flowchart of SOINN.

その構造中の適当な箇所に能動的にラベルを付与する，
オンライン準教師付能動学習の手法を提案する．
本論文の構成を以下に示す．2. では，提案手法のもととなる SOINN の概要について説明する．3. では，SOINN の新たなクラスタ判別方法を提案した後，教師なし学習である SOINN を準教師付学習に拡張する方法を与える．4. では，3. で提案した手法を用いて計算機実験を行い，その有効性を示す．5. では，本研究の成果をまとめるとともに，今後解決すべき課題を述べる．

2. SOINN の概要
本章では，提案手法のもととなる SOINN の概要について説明する．

SOINN は，自己組織化マップ (SOM) [4] と競合
ヘッブ学習則 [6] を組み合わせて入力データの位相構
造を学習する手法である．入力データの代表点としてノードを生成し，それらを結合する辺を用いて位相構て，データの分布が低密度の領域を切り分けることでクラスタリングを行う．1 層目と 2 層目は同じ学習ア
ルゴリズムで動作する．図 1 に SOINN の学習アル
ゴリズムのフローチャートを示す．SOINN は，入力データ集合から入力ベクトルが与えられると，入力ベクトルに最も近いノード（第 1 勝者ノード）及び 2 番
目に近いノード（第 2 勝者ノード）を探索する．そして，類似度しきい値という規準を用いて，入力ベクト
ルがそれらのノードと同一クラスタに属するかを判定する．SOINN 1 層目では，入力データの分布は未知であるので，類似度しきい値はノードごとに適応的に変化させる．ノード i が辺によって直接的に接続しているノード（隣接ノード）をもつ場合，その類似度しきい値 Ti は，隣接ノードとの最大距離

Ti = max W i − W j j∈Ni

造を表現する．同様の手法に，Neural Gas (NG) [6]や Growing Neural Gas (GNG) [3] がある．しかし，(1)によって与えられる．ここで，Ni はノード i の隣接

NG や GNG ではノード数が恒久的に増加してしまう

ノードの集合，W i はノード i の重みベクトルを表す．

ため，永続的な追加学習には適さない．これに対しまた，ノード i が隣接ノードをもたない場合，その類

SOINN では，入力データの位相構造を適切に表現す

似度しきい値 Ti は，ノード i からそれ以外の各ノーるために必要なノード数を自律的に獲得することによ

ドとの最小距離り，永続的な学習に適している．

SOINN は 2 層ネットワーク構造により学習を行う．
1 層目の学習によって，入力データの確率密度分布を近似するようにノードを生成し，2 層目の学習によっ
3092

Ti =

min W i − W j j∈N\{i}(2)によって与えられる．ここで，N はノード全体の集合を表す．

論文／競合型ニューラルネットを用いたオンライン準教師付能動学習手法

入力データと第 1 勝者ノード及び第 2 勝者ノードとクラスタを適切に分離することができない．

の距離が類似度しきい値よりも大きい場合，それらはそこで本論文では，オンライン学習である SOINN 1

異なるクラスタに属すると判定する．このとき，入力層目の学習のみで，従来の 2 層目のクラスタ識別性能

ベクトルと同じ位置にノードを挿入し，次の入力を処と同等の結果を得られる，新たなクラスタ判別方法を理する．このときの挿入はクラス間挿入と呼ばれる．

提案する．その詳細は次章で述べる．ここで，本論文また，同一クラスタに属すると判定された場合，第 1で用いる SOINN 1 層目の学習アルゴリズムをまとめ

勝者ノード及び第 2 勝者ノードの隣接ノードの重みベて述べる．ただし前述の理由から，クラス内挿入は行

クトルを更新する．このとき第 1 勝者ノードになった

わないこととする．

ノードを i と表し，i がこれまでに第 1 勝者ノードにアルゴリズム 2.1：SOINN 1 層目の学習アルゴリズム

なった回数を Mi と表せば，第 1 勝者ノード i の重み

Step 1. 入 力 デ ー タ 集 合 Is か ら 二 つ の 入 力 s1，
s2(∈ Is ) を ラン ダムに 選択 し，そ れ ぞれの 重み ベ
クトル W s1 ，W s2 をもつノード n1 と n2 を生成する．また，ノード全体の集合を N = {n1 , n2 } に初期ベクトルの更新量 ΔW i と，i の隣接ノード j(∈ Ni )の重みベクトルの更新量 ΔW j は，

1
(W s − W i )Mi
1
ΔW j =(W s − W j )100Mi

ΔW i =(3)(4)

で与えられる．ここで，W s は入力の重みベクトルを表す．また，第 1 勝者ノードと第 2 勝者ノードの間に辺が存在しなければ，それらの間に辺を生成し，その辺の「年齢」を 0 にする．そして，第 1 勝者ノードに接続するすべての辺の年齢を +1 する．このとき，あらかじめ決められたパラメータである agemax を超えた年齢をもつ辺は削除する．更に，入力が λ 回与えら化する．

Step 2. 入力 s ∈ Is をランダムに選択する．その重みベクトルを W s と表す．
Step 3. 第 1 勝者ノード
w1 = argmin W i − W s (5)i∈N\{i}及び第 2 勝者ノード

w2 = argmin W i − W s (6)i∈N\{i,w1}

れるごとに，隣接ノード数が一つ以下のノードを低密を探索する．

度の領域に位置するとみなし削除する．その際，入力

Step 4. 入力データの重みベクトル W s と第 1 勝者
ノードの重みベクトル W w1 及び第 2 勝者ノードの重みベクトル W w2 との距離と，類似度しきい値 Tw1 ，
Tw2 との間でデータとノードの位置との誤差が大きい領域にノードを挿入する．ただし，挿入によって誤差が減少しない
場合は，挿入は取り消される．このときの挿入はクラス内挿入と呼ばれる．
ところで，前述のとおり SOINN 1 層目では類似度

W s − W w1  > Tw1(7)

しきい値が適応的に変化する．そのため，入力データ

W s − W w2  > Tw2(8)とノードの位置との誤差は大きくならず，クラス内挿
入はほとんど行われない．そこで，SOINN 1 層目ではのいずれかの条件を満たす場合，重みベクトル W s を

クラス内挿入を行う必要はない．ここで SOINN 1 層もつノード ns を生成し，Mns = 0 に初期化する．ま目は学習結果として，入力データの代表点であるノー

た，ノード集合を N = N ∪{ns } に更新し，Step 8. へ．

ドの重みベクトルとその位相構造を出力する．1 層目

上のいずれの条件も満たさない場合，Mw1 = Mw1 + 1の学習で，入力回数があらかじめ設定された回数 LTに更新する．

に達したときに出力結果として得られた重みベクトル

Step 5. 第 1 勝者ノードと第 2 勝者ノードの間に辺の接続がない場合，辺 (w1, w2) を生成し，age(w1,w2) = 0に初期化する．ここで，age(i,j) は辺 (i, j) の年齢を表す．
Step 6. 第 1 勝者ノードの重みベクトルをは，2 層目の入力として使用される．SOINN 2 層目
は 1 層目と同様のアルゴリズムで動作する．しかし，

SOINN 2 層目では，SOINN 1 層目の学習結果が更新された場合，これまでの学習結果を消去し，学習し直す必要があり，オンライン追加学習に対応していない．
一方，SOINN 1 層目の学習だけでは，重なりがある

W w1 = W w1 + ΔW w1(9)に更新する．また，w1 のすべての隣接ノード i ∈ Nw13093

電子情報通信学会論文誌 2007/11 Vol. J90–D No. 11

クラスタリングを実現していた．しかし，SOINN 2に対して，重みベクトルをW i = W i + ΔW i

(10)に更新し，第 1 勝者ノードとの間の辺の年齢をage(w1,i) = age(w1,i) + 1(11)

層目はオンラインの追加学習ができない．SOINN 1
層目の学習結果のみから低密度の領域を切り分けることができれば，オンライン教師なし分類が実現できる．

SOINN 1 層目の学習結果であるノードとその位相関係は，入力データの確率密度分布を近似するようにに更新する．

生成されたものである．一般に，分布が高密度の領域

Step 7. 辺の年齢が agemax を超える辺を削除する．

には多くのノードが生成される．そのため，そのよう

Step 8. 入力回数が λ の倍数ならば，隣接ノード数な領域では，隣接ノード間の距離，すなわちノードをが一つ以下のノードをノイズノードとして削除する．

接続している辺の長さが小さくなる．そこで，ノード

Step 9. 学習を終了する場合は停止する．終了しない
場合は Step 2. へ．

i の密度 D(i) を，ノード i の隣接ノードとの平均距離j∈Ni W i − W j 
(12)
di =
|Ni |

次に，学習結果として得られたノードの属するクラスタを決定する方法について述べる．SOINN では競合ヘッブ学習則に従って，ノード間にパス，すなわち連続的な辺の接続が存在するとき，それらのノードが同一クラスタに属すると判断する．以下にノードの属するクラスタを決定するアルゴリズムを示す．
アルゴリズム 2.2：ノードの属するクラスタ決定

Step 1. クラスタ決定されていないノードの集合 JC
を JC = N に初期化する．
Step 2. ノード i ∈ JC をランダムに選択し，新しいク
ラスタラベル Ci を付与する．また，JC = JC \{i} に更新し，クラスタ Ci のノード集合 NCi を NCi = {i}に初期化する．

Step 3. ノード i との間 にパス が存在 するノ ードの集合を Np と表す．j ∈ Np であるすべてのノードに対して，クラスタラベル C を付与する．また，JC = JC \NCi ，NCi = NCi ∪ Np に更新する．
Step 4. JC = Φ な ら ば 終 了 ．そ う で な い な ら
Step 2. へ．
次章で，本章で紹介した SOINN を拡張したオンラ
イン準教師付能動学習手法を提案する．

を用いて，次のように定義する．

D(i) =

1(1 + di )2(13)

式 (12) で，|Ni | は Ni の要素数を表す．このように定義されたノードの密度が大きな領域ほど，入力データの確率密度が大きいと考えられる．ここで，各クラスの中心では入力データの確率密度が高く，クラスの重なる領域では入力データの確率密度が低い（図 2）と仮定すれば，ノードの密度が大きい領域がクラスの中心で，ノードの密度が小さい領域がクラスの重なり領域であると判断することができる．そこで，局所的に最大となるノード，すなわちすべての隣接ノード

j ∈ Ni について D(i) > D(j) を満たすようなノード
i を中心ノードと呼ぶことにする．
この中心ノードに基づき，SOINN 1 層目によって得られたそれぞれのクラスタを，より小さなサブクラ
スタに分割する．以下に，ノードの属するサブクラス
タを決定するアルゴリズムを示す．

3. 提 案 手 法
本章ではまず，SOINN 1 層目の学習のみで，従来の 2 層構造の SOINN のクラスタ識別性能と同等の性能を得られる，新たなクラスタ判別方法を提案する．
その後，教師なし学習である SOINN を準教師付能動学習に拡張する方法を与える．

3. 1 提案手法によるクラスタリング方法
従来の SOINN では，1 層目の学習で入力の確率密度分布を近似するようにノードとその位相関係を生成
し，2 層目の学習で低密度の領域を切り分けることで
3094

Fig. 2図 2 重なりのあるクラスの確率密度分布
Censity distribution of overlapped classes.

論文／競合型ニューラルネットを用いたオンライン準教師付能動学習手法

アルゴリズム 3.1：ノードの属するサブクラスタ決定

Step 1. 局所的に最大となるノード（中心ノード）を{ci }ni=1 と表し，それらすべてに異なるサブクラスタ

a とサブクラスタ B に属するノード b を接続する辺(a, b) を，A と B のサブクラスタ境界辺と呼ぶことにする．サブクラスタ境界辺は図 2 の A で示した，密ラベルを付与する．また，サブクラスタラベル付与済

度の「谷間」に位置する辺である．そこで，その谷間

ノードの集合 JS を JS = {ci }ni=1 に初期化する．

の密度をサブクラスタ境界辺の密度と呼ぶことにし，Step 2. サブクラスタラベルが付与されていないノードの中で，密度が最大のノード

i = argmax D(j)

(14)

j∈N\S

D(a, b) = min(D(a), D(b))(17)と定義する．一般にサブクラスタ境界辺は，それぞれのサブクラスタ間に複数存在するため，その中で密度が最大の境界辺を最大境界辺と呼ぶことにし，最大境を探索する．

界辺の密度

Step 3. ノード i に，隣接ノードの中で密度が最大の
DAB =

ノード

argmax D(j)
j∈Ni

(15)

D(a, b)(18)を用いてグループ化判定を行うことにする．ここで，EAB は A と B のサブクラスタ境界辺の集合を表す．

のサブクラスタラベルと同一のラベルを付与する．また，サブクラスタラベル付与済ノード集合 JS を

JS = JS ∪ {i}max(a,b)∈EAB(16)に更新する．

このとき，D(cA ) − DAB < GC

(19)

または，

D(cB ) − DAB < GC

(20)

Step 4. JS = N な ら ば 終 了 ．そ う で な い な ら
Step 2. へ．

のいずれかを満たす場合，サブクラスタ A とサブクノードの密度はノイズなどの影響によって，細かい

ラスタ B は同一グループであると判定する．ここで，凹凸のある分布になってしまう場合がある（図 3）．そcA ，cB はサブクラスタ A とサブクラスタ B の中心
ノード，GC はサブクラスタ A とサブクラスタ B が属するクラスタ C のグループ化しきい値を表す．また，クラスタ C のグループ化しきい値 GC をαGC =|D(i) − D(j)|
(21)
|EC |

のような場合，必要以上に小さなサブクラスタに分割してしまうことになる．そこで，細かい凹凸によって分割されたサブクラスタであるかを判定し，複数のサ
ブクラスタをグループ化することで平滑化を実現する．
提案手法ではグループ化する条件に，サブクラスタの中心ノードの密度と，サブクラスタ境界の密度との差を用いる．ここで，サブクラスタ A に属するノード(i,j)∈ECと定義する．式 (21) で，EC はクラスタ C の辺の集合，|EC | は EC の要素数，α は平滑化パラメータを表す．それぞれのサブクラスタの最大境界辺について，
式 (19) と式 (20) の判定を行ってグループ化を実現す
る．以下に，サブクラスタをグループ化するアルゴリ
ズムをまとめる．
アルゴリズム 3.2：サブクラスタのグループ化

Step 1. グループ化判定していない最大境界辺の集合を JG = {(ai , bi )}ni=1 と表す．また，すべてのノードに対し，グループラベルが付与されていない状態にする．
図 3 重なりのあるクラスの確率密度分布（細かい凹凸がある場合）
Fig. 3 Clusters with overlapped area (withﬂuctuation).

Step 2. JG の中から，(amax , bmax ) = argmax D(ai , bi )(22)

(ai ,bi )∈JG

3095

電子情報通信学会論文誌 2007/11 Vol. J90–D No. 11を探索する．このとき，辺 (amax , bmax ) の両端のノーライン性を保持したままラベル付データを扱うことがド amax と bmax の両方に対してグループラベルが付できる．

与されているならば，Step 3. へ．そうでない場合，
amax と bmax が属するサブクラスタをそれぞれ A，Bと表す．このとき，式 (19) または式 (20) を満たすなに基づいてノードと位相関係を生成し，同一クラスのところで SOINN では，入力データの確率密度分布
データが同一クラスタになるようにクラスタリングしらば，サブクラスタ A と B が属するグループのすべている．更にアルゴリズム 3.1 で，クラスタ内のノーてのノードに対して，同一のグループラベルを付与

ドの分布を用いてクラスの重なり領域を検出し，クラする．

スタをより詳細なサブクラスタに分割した．したがっStep 3. (amax , bmax ) をグループ化判定済みにする．

て，同一クラスタに属するノードは同一クラスラベル

すなわち，をもつ可能性が高く，同一サブクラスタに属するノー

JG = JG \{(amax , bmax )}(23)

ドは同一クラスラベルをもつ可能性がより高いと考えられる．また，密度が小さいノードはクラスの重なりに更新する．このとき JG = Φ ならば，グループラベ

領域のノードである可能性が高く，密度が大きいノールが付けられていないノードに対して，それぞれのサドほどクラスの中心付近のノードであると考えること

ブクラスタごとに異なるグループラベルを付与して終ができる．したがって，教師付ノードでないノードの了．そうでなければ Step 2. へ．

クラスラベルは，そのノードが属するサブクラスタ内

同様な方法で，SOINN 1 層目の学習のみで低密度

で最も密度が大きい教師付ノードのクラスラベルと領域の切り分けを実現した手法に，小倉らが提案し同一であると判断することにする．また，同一サブク

た Enhanced-SOINN (ESOINN) がある [10]．しかしラスタ内に教師付ノードがない場合，同一サブクラス

ESOINN では，密度を用いて第 1 勝者ノードと第 2

タグループ内，同一クラスタ内の順で教師付ノードを

勝者ノードとの間に辺を生成するかを判定し，クラス探索し，同一のクラスラベルを付与する．これをまとタリング方法は従来と同じくパスの有無によって行う．

めた，ノードへのクラスラベル付与のアルゴリズムをそのため ESOINN では，サブクラスタ間の重なり領示す．

域を学習後に検出することができない．

アルゴリズム 3.3：教師付ノードを用いたクラスラベ

一方提案手法では，SOINN によって得られた位相関係は全く変えずに，クラスタリング方法だけを変えているため，学習後にもサブクラスタ間の重なり領域

ル付与

Step 1. 教師付ノードの集合を NL と表し，クラス
ラベル付与済ノードの集合 JL を JL = NL に初期化を検出することが可能である．この重なり領域の情報

する．

は，準教師付能動学習に拡張する際に用いる．

Step 2. ノード i ∈ N \JL を一つ選ぶ．
Step 3. ノード i と同一サブクラスタラベルをもつノードの集合を NS と表す．このとき，NS ∩ JL = Φ

3. 2 SOINN の準教師付能動学習への拡張
SOINN は教師なし学習の手法である．そのため，
SOINN は入力データにクラスラベルが付与されていても扱うことができない．そこでまず，SOINN でラ
ベル付データを扱う方法を与える．SOINN に対して，
重みベクトルが W s であるラベル付データが入力されたとき，その最近傍ノード

argmin W i − W s 
i∈N

(24)

に，入力データと同じクラスラベルを付与する．このように，ラベル付データによって直接的にクラスラベ
ルを付与されたノードのことを教師付ノードと呼ぶこ

ならば，

l = argmax D(j)j∈NS ∩JL(25)

であるノード l を探索し，Step 7. へ．

Step 4. ノード i と同一グループラベルをもつノードの集合を NG と表す．このとき，NG ∩ JL = Φ ならば，

l = argmax D(j)j∈NG ∩JL(26)とにする．これ以降は入力されたラベル付データを用であるノード l を探索し，Step 7. へ．

いずに，SOINN によって生成されたノードである教Step 5. ノード i と同一クラスタラベルをもつノードの集合を NC と表す．このとき，NC ∩ JL = Φ な

師付ノードのみを用いることで，SOINN のもつオン
3096

論文／競合型ニューラルネットを用いたオンライン準教師付能動学習手法

C = argmax |Na |らば，

l = argmax D(j)j∈NC ∩JL

a∈AC

(27)

であるノード l を探索し，Step 7. へ．

Step 6. NS のすべてのノードに対して，未知クラス
ラベルを付与する．また，クラスラベル付与済ノード
集合を JL = JL ∪ NS に更新し，Step 8. へ．

Step 7. NS のすべてのノードに対して，教師付ノード l のクラスラベルを付与する．また，クラスラベル
付与済ノード集合を JL = JL ∪ NS に更新する．

(28)

を探索する．そして，クラスタ C に属する最大密度のノード

q = argmax D(i)
i∈NC

(29)

を探索し，Step 5. へ．

Step2. 教師付ノードをもたないグループの集合を
AG = {Gi }mi=1 と表す．このとき，AG = Φ ならば，G = argmax |Na |(30)

Step 8. JL = N な ら ば 終 了 ．そ う で な け れ ば
Step 2. へ．
このアルゴリズムによって，SOINN で得られたノーを探索する．そして，グループ G に属する最大密度のドの一部にクラスラベルを付与するだけで，データ全ノード体を表すすべてのノードに対してクラスラベルを付与

a∈AG

q = argmax D(i)i∈NG

することができる．すなわち，SOINN を準教師付学
習に拡張したことになる．
ここで，アルゴリズム 3.3 を用いてクラスラベル付(31)を探索し，Step 5. へ．

与を行うとき，サブクラスタの中心ノードが教師付

Step 3. 教師付ノードをもたないサブクラスタの集合を AS = {Si }li=1 と表す．このとき，AS = Φ な

ノードならば，同一サブクラスタ内の他の教師付ノー

らば，ドは，その他のノードのクラスラベル付与に影響を与えない．したがって，少ないクラスラベルの付与で効率良く学習するためには，まず中心ノードのクラスラ
ベルだけを得ればよいことが分かる．また，サブクラ
スタよりサブクラスタグループ，サブクラスタグルー
プよりクラスタの方がより広範囲の分布を表現していS = argmax |Na |
a∈AS

(32)

を探索する．そして，サブクラスタ S に属する最大密度のノード

q = argmax D(i)i∈NSる．更に，その中のノード数が多いほど広範囲の分布(33)を表していると考えられる．したがって，より効率のを探索し，Step 5. へ．

良い学習のためには，ノード数の多いクラスタ，サブStep 4. 教師付ノードでないクラス境界ノードの集合
を NB と表す．このとき，NB = Φ ならば，質問せずに終了．NB = Φ ならば，q ∈ NB をランダムに一つクラスタグループ，サブクラスタの順で中心ノードのクラスラベルを能動的に要求すればよいことが分かる．
クラスの確率密度分布に重なりがある場合，アルゴ

選択．

リズム 3.3 に基づいてクラスラベルを付与すると，辺Step 5. ノード q の重みベクトル W q に対応する出で直接的に接続した隣接ノード同士で異なる推定ク

力ラベルを質問し終了．

ラスラベルをもつノードが生じる可能性がある．これ

このようにして，準教師付能動学習を実現する．たらのノードが存在する領域は，クラスの境界であるとだし，クラス境界ノードについてクラスラベルを質問考えられる．そこで，クラス間の境界を精度良く学習する場合，ノードに付与されているクラスラベルと，するために，異なるクラスラベルの隣接ノードをもつ

質問して得たラベル付データのクラスラベルとが矛盾

ノード（クラス境界ノードと呼ぶことにする）についする場合がある．アルゴリズム 3.3 に基づいて付与さてクラスラベルを要求する．これらをまとめた，クラれるクラスラベルは，他の教師付ノードのクラスラベ

スラベル質問アルゴリズムを以下に示す．

ルとクラスタリング情報から推定したものである．しアルゴリズム 3.4：クラスラベルの質問

たがってそのような場合には，ラベル付データのクラ

Step 1. 教師付ノードをもたないクラスタの集合を
AC = {Ci }ni=1 と表す．このとき，AC = Φ ならば，スラベルを優先してクラス境界ノードのクラスラベル
を上書きする．
3097

電子情報通信学会論文誌 2007/11 Vol. J90–D No. 11

追加的に生じる場合，既存の教師付ノードが新たに生

agemax = 30，α = 2.2 で実験を行った．
結果を図 5 に示す．図 5 は，ノードに付与されたじたクラスの分布と重なる領域に含まれる可能性があ

クラスラベルごとにそれぞれ異なる記号を用いて表さる．しかし，前述のとおり，サブクラスタの中心ノーれている．また，教師付ノードの記号は大きなものでドが教師付ノードならば，同一サブクラスタ内の他の表されている．この図から提案手法によって，ノイズ

教師付ノードは，その他のノードのクラスラベル付与の影響を受けずに入力分布が表現されていることが分に影響を与えない．したがって，あるクラスの教師付

かる．また，クラスラベルの要求について，一様分布

ノードが追加的に生じた別クラスに関するサブクラスである同心円及びサインカーブの分布では，クラスラタの分布の頂点にない限り，追加的なクラスラベルのベルの要求がほぼ一様に分布したサブクラスタに対し付与（アルゴリズム 3.3）に悪影響を及ぼすことはなて生じている．一方，二つのガウス分布では，クラス

い．本章で述べた提案手法を用いた計算機実験を次章の分布が重なる領域にクラスラベルの要求が集中して

また，クラスの確率密度分布に重なりがある分布がに示す．

4. 計算機実験
本章では，計算機実験によって，3. で述べた提案手法が有効に働くことを示す．

4. 1 人工データを用いた実験

いる．最終的に，70 個のクラスラベルで全体のノードに適切なクラスラベルが付与された．したがって本実験において，提案手法は生成された 331 個のノード全体に対して 21.1%のクラスラベル，入力データ全体に対して 70/200,000 = 0.035%のクラスラベルで，効率良く学習を行うことができた．

最初に，入力データとして人工データを用いた実

次に，オンライン学習を想定し，入力データ集合が験を行った．使用した入力データ集合を図 4 に示す．

変化する非定常的な環境での実験を行った．入力デー

データは分布に重なりのある二つのガウス分布，二つタ集合を入力 50,000 回ごとに，下側のガウス分布との同心円，及びサインカーブによって構成されている．

同心円の内側，上側のガウス分布，同心円の外側，サ二つのガウス分布については，10%のベイズ誤り確率

インカーブの順で変化させ実験を行った．提案手法のを含むように配置した．同心円及びサインカーブの形

パラメータは，λ = 250，agemax = 30，α = 2.5 とし状の分布は一様分布である．同心円の内側とガウス分た．クラスラベルの要求は入力 50,000 回ごとのノイ

布の下のものは同一クラス，他の分布はすべて異なる

ズノード削除の後に，アルゴリズム 3.4 に従って要求クラスの計 4 クラスとした．また，実世界の環境を想されるノードに対して行い，要求が生じなくなるまで定して，入力データには 10%の一様ノイズを加えた．

行った．

まず，入力をデータ集合全体からランダムに選択

図 6 は，入力 50,000 回ごとのクラスラベル付与後する，定常的な環境での実験を行った．クラスラベルの結果を表したものである．新規クラスのデータが入の要求は，SOINN の入力 200,000 回後に行われるノ
イズノードの削除の後に，アルゴリズム 3.4 に従って要求されるノードに対して行い，要求が生じなくなるまで行った．提案手法のパラメータは，λ = 750，

図 4 実験に用いた人工データ集合
Fig. 4 Artiﬁcial data used for experiment.

3098

図 5 人工データを用いた定常的な環境での実験結果．生成されたノードを，それらに付与されたクラスラベ
ルごとに異なる記号を用いて表した．また，教師付
ノードは大きな記号で表した．
Fig. 5 Experiment results of artiﬁcial data under stationary environment. Unlabeled nodes are labeled with diﬀerent marks, and teacher nodes
are labeled with large marks.

論文／競合型ニューラルネットを用いたオンライン準教師付能動学習手法

力されるごとに，新たな分布を表すノードが生成され，ていることが分かる．更にその要求は，クラスの分布

それらに対してクラスラベルが要求されていることがの重なりが生じた時点で新たに生じていることが分か分かる．また，定常的な環境での実験と同様に，クラる．最終的に，94 個のクラスラベルで全体のノードにスの分布が重なる領域にクラスラベルの要求が集中し適切なクラスラベルが付与された．したがって本実験において，提案手法は生成された 377 個のノード全体に対して 24.9%のクラスラベル，入力データ全体に対して 94/200,000 = 0.047%のクラスラベルで，効率良く学習を行うことができた．

4. 2 実データを用いた実験
次に，入力データとして実データを用いて実験を行った．

4. 2. 1 最近傍法による全数記憶方式との比較
まず，全数記憶した場合と提案手法によって得られたノードをプロトタイプとした場合の，最近傍法による識別率と教師ラベル数を比較した．データセット
は UCI Repository データベースの Pima，WDBC，

Iris，Optdigits を用いた [8]．Pima，WDBC，Iris では Leave-one-out 実験の結果を用い，Optdigits では
100 回の試行の平均を用いた．また，それぞれのデー
タセットに対する，提案手法のパラメータを表 1 に示す．クラスラベルの要求は，Pima，WDBC，Iris では入力 100,000 回，Optdigits では入力 200,000 回で行われるノイズノード削除の後に，アルゴリズム 3.4で要求されたノードに対してのみ行った．表 2 と表 3に結果を示す．表 2 より，提案手法によって全数記憶の場合とほぼ同等の識別率が得られていることが分か
表 1 各データに対して提案手法で用いたパラメータ
Table 1 Parameters for diﬀerent data sets.
λagemaxPima WDBC
1,000
400
30
150

Iris
300
150

Optdigits
10,000100

表 2 実データに対して，全数記憶の最近傍法と，提案手法によって得られたプロトタイプを用いた最近傍法との識別率の比較
Table 2 Recognition ratio comparison.
全数記憶
提案手法
図 6 人工データを用いた追加学習実験結果．生成されたノードを，クラスラベルごとに異なる記号を用いて表した．また，教師付ノードは大きな記号で表した．
上から SOINN への入力が 50,000 回，100,000 回，
150,000 回，200,000 回後に行われたクラスラベル
入力後の結果である．
Fig. 6 Incremental learning result of artiﬁcial data.
From top to down, show the results after
50,000, 100,000, 150,000, and 200,000 times
training.

Pima WDBC
68.0
91.6
69.4
92.1

Iris
96.0
96.7

Optdigits
98.0
96.5

表 3 実データを用いた実験での，全数記憶と提案手法で用いたラベル付データ数の比較．提案手法は，それぞれの試行で入力したクラスラベル数の平均値である．
Table 3 Needed teacher vectors comparison.
全数記憶
提案手法

Pima WDBC
767
568
78.9
34.2

Iris
149
14.2

Optdigits
3,823
147.4

3099

電子情報通信学会論文誌 2007/11 Vol. J90–D No. 11

る．また，表 3 より，提案手法に必要な教師数は，全が確認できる．一方，ランダムにクラスラベルを付与

数記憶に比べ大幅に少なくてよいことが分かる．これした方は，識別率の上がり方が緩やかで，能動学習でらのことから，提案手法は全数記憶の最近傍法に比べ，の識別率を下回っていることが確認できる．この結果非常に少ない教師数で同等の識別率が得られることがより，アルゴリズム 3.4 を用いれば，少ないラベル付分かった．

データでより効率良く学習できることが分かる．

文献 [5] では，TSVM と GRF と Logistic GRF の4. 2. 3 クラス追加学習の実験

比較実験が行われ，それらの手法で最良の場合，Pima

次に，Optdigits を用いて新規クラスの追加学習ので教師数 70 のとき識別率約 72%，WDBC で教師数実験を行った．入力データ集合を，入力 50,000 回ごと

30 のとき識別率約 95.5%という結果が得られている．

に奇数，偶数，全データの順で変化させ実験を行った．

提案手法はこれらの識別率に数%劣るが，新規クラス

提案手法のパラメータは λ = 10,000 ，agemax = 100，の追加学習やオンライン学習が可能であるという優位

α = 1.0 とした．クラスラベルの要求は 10,000 ステッ

性を有している．

プごとに行われるノイズノード削除の後に，アルゴリ

4. 2. 2 能動学習の有効性の実験

ズム 3.4 の Step 2. で質問されるノード，すなわちサ次に Optdigits を用いて，アルゴリズム 3.4 によっ

ブクラスタグループの中心ノードに対してのみ行った．

て能動的にクラスラベルを付与した場合と，ランダム

図 8 と図 9 に結果を示す．ここで，結果は 100 回にクラスラベルを付与した場合の比較を行った．Opt-の試行の平均値であり，入力 50,000 回までの識別率

digits は，3,823 個の訓練データと 1,797 個のテストデータからなる 64 次元の手書き数字データである．

より，入力データが偶数に変わった入力 50,000 回の入力データ集合としてすべての訓練データを用いて時点で，教師の数が大幅に増えていることが分かる．

は奇数のテストデータのみに対するものである．図 8

実験を行った．クラスラベルの入力を，入力 200,000

また，図 9 より，ある程度の識別率を保っていること

回で行われるノイズノード削除の後にアルゴリズムが分かる．これは，システムが入力は未知のクラスで3.4 に従って行った場合と，入力データ集合の中からラあるか判定し，必要な教師ラベル数を自律的に決定でンダムに選択して行った場合とで比較を行った．パラ

きることを示すものである．また，入力 50,000 回まメータはいずれの場合も λ = 10,000 ，agemax = 100，

α = 1.0 とした．
図 7 に結果を示す．結果は 100 回の試行の平均値である．また，縦軸が識別率，横軸が入力したラベル付
データ数，実線が能動的にクラスラベルを付与した結果，点線がランダムにクラスラベルを付与した結果を表す．図 7 より，能動学習を行った方は少ないラベル付データで，識別率が大幅に上がっていることが分かる．更にその後も，識別率が徐々に上がっていくこと

図 7 Optdigits を用いた，ラベル付データの入力を能動的に選択した場合と，ランダムに選択した場合の比較
Fig. 7 Comparison: actively queries or random
queries.

3100

図 8 Optdigits を用いた，新規クラスの追加学習実験による入力回数とラベル付データ数の関係
Fig. 8 Incremental learning: needed number ofteacher vectors.

図 9 Optdigits を用いた，新規クラスの追加学習実験による入力回数と識別率の関係
Fig. 9 Incremental learning: recognition ratio.

論文／競合型ニューラルネットを用いたオンライン準教師付能動学習手法

でに識別率が上がっていくのは，SOINN での学習が削除の後に，アルゴリズム 3.4 の Step 3. で要求され進み，入力データの分布をより良く近似できるようにるノード，すなわちサブクラスタの中心ノードに対しなったためであると考えられる．

てのみ行った．

4. 2. 4 顔画像を用いたオンライン学習実験
最後に，実環境のデータに対するオンライン学習

図 12 と図 13 に結果を示す．結果は 100 回の試行の平均で，識別率は入力されたことがあるクラスのテの実験を行った．実環境のデータとして，固定されストデータのみに対するものである．また，図 12 のたビデオカメラで撮影した 10 人分の顔画像を用いた

縦軸は入力されたラベル付データ数で横軸は入力回数，（図 10）．用いた画像は，1 秒間 30 フレームで撮影さ図 13 の縦軸は識別率で横軸は入力回数を表す．図 13

れた，20 × 26 ピクセルのグレースケール 256 階調のより，新規クラスのデータが入力されるごとに識別率

画像である．撮影中，被撮影者は顔の方向を少しずつが下がるが，学習が進むことで再び識別率が上がって変化させている（図 11）．1 人当り 3,000 フレーム分いることが確認できる．また，入力 30,000 回後のノーの連続的な画像，計 30,000 枚の画像を訓練データとしド数の平均は 353.19 であった．一方，この実験で用て用いた．また，訓練データとは別に撮影した，1 人

いたデータを全数記憶する場合，30,000 のデータを蓄

当り 700 フレームの画像をテストデータとして用いた．

えておく必要がある．したがって提案手法では，必要提案手法のパラメータは λ = 2,000，agemax = 200，

なメモリ量や最近傍法による識別の計算量を 1.2%程

α = 1.0 で実験を行った．入力データ集合は，λ のサ
イズの First-in-ﬁrst-out のバッファに画像を保存した度に抑えることができるといえる．更に，入力されたものを用いた．つまり，入力データ集合はカメラからにノードの生成は終了する．つまり提案手法では，カの新たな入力があるごとに，バッファ内で最も前に入メラからの動画像に対して実時間での学習が可能であ

力されたデータを破棄し，新たに入力されたデータをる．このように，カメラで撮影したような，実環境の保持するという方法で更新される．また，クラスラベ

多数高次元データに対しても，識別率を大幅に下げる

ルの要求は入力 2,000 回ごとに行われるノイズノード

ことなくオンラインで学習できていることが分かる．

図 10 実験に用いた 10 人分の顔画像
Fig. 10 An example of facial images of each subject.

図 11 実験に用いた顔画像．顔の方向が少しずつ変化する
Fig. 11

An example of face sequences.

画像に対して，カメラから次の画像が入力されるまで

図 12 顔画像データを用いた実験による入力回数とラベ
ル付データ数の関係
Fig. 12 Face recognition: needed number of teacher
vectors.

図 13 顔画像データを用いた実験による入力回数と識別率の関係
Fig. 13 Face recognition: recognition ratio.

3101

電子情報通信学会論文誌 2007/11 Vol. J90–D No. 11
on Machine Learning, pp.435–442, 2002.

5. む す び[8]

本論文では SOINN を拡張し，オンライン準教師付
能動学習手法を提案した．提案手法は，ノード数やク

C. Merz and M. Murphy, UCI Repository of machinelearning database, University of California Department of Information, Irvine, CA, 1996.

[9]

K. Nigam, A.K. McCallum, S. Thrum, and T.

ラス数などの事前知識を必要としない．また，必要な

Mitchell, “Text classiﬁcation from labeled and un-

教師数を自律的に獲得することで永続的な学習を行う

labeled documents using EM,” Mach. Learn., vol.39,

ことができる．更に，入力データの中に分布するノイ

pp.103–134, 2000.
[10]

ズを除去することが可能であるという特長をもつ．

小倉和貴，申 富饒，長谷川修，“オンライン教師なし分
類のための追加学習手法，” 信学論（D），vol.J90-D, no.6,
pp.1610–1622, June 2007.

計算機実験によって，提案手法の有用性を示した．
人工データを用いた実験では，データ中に存在する[11]10%程度のノイズを除去し，入力データの分布とそのlearning,” Neural Netw., vol.19, no.1, pp.90–106,

クラスラベルを適切に表現できることを示した．次に，実データを用いて，提案手法は全数記憶の最近傍法と

2006.
[12]

monic functions,” Proc. ICML-03, 20th International

きることを示した．また，必要なラベル付データやそしても事前知識なしで追加的に学習できることを示した．更に，実環境のデータに対してもオンラインで学

X. Zhu, Z. Ghahramani, and J. Laﬀerty, “Semisupervised learning using Gaussian ﬁelds and har-

同程度の識別率で，ラベル付データ数を大幅に削減での数を自らで決定することができ，新たなデータに対F. Shen and O. Hasegawa, “An incremental networkfor on-line unsupervised classiﬁcation and topology

Conference on Machine Learning, pp.912–919, 2003.
[13]

X. Zhu, J. Laﬀerty, and Z. Ghahramani, “Combining active learning and semi-supervised learning using Gaussian ﬁelds and harmonic functions,” ICML
2003 Workshop on The Continuum from Labeled to

習できることを示した．しかし，従来のバッチ学習のUnlabeled Data in Machine Learning and Data Min-

手法に比べ，提案手法は識別率で数%劣る．それらのing, pp.58–65, 2003.

（平成 19 年 2 月 20 日受付，6 月 28 日再受付）

手法の識別率に近づけることが今後の課題である．
謝辞 本研究の実施にあたり NEDO 産業技術研究
助成事業から支援を頂きました．記して感謝致します．
文
[1]

[2]

献

櫻井

啓介

2005 東工大・工・情報工学卒．2007 同

K. Bennett and A. Demiriz, “Semi-supervised support vector machines,” Advances in Neural Informa-

大大学院総合理工学研究科知能システム科学専攻修士課程了．現在，アップルジャパ

tion Processing Systems, vol.11, pp.368–374, 1999.

ン（株）に勤務．

A. Blum and T. Mitchell, “Combining labeled andunlabeled data with co-training,” Proc. Conference
on Computational Learning Theory, pp.92–100, 1998.

[3]

B. Fritzke, “A growing neural gas network learns
topologies,” Advances in Neural Information ProcessT. Kohonen, “Self-organized formation of topologically correct feature maps,” Biol. Cybern., vol.43,
no.1, pp.59–69, 1982.

[5]

B.

Krishnapuram,

D.

Williams,

祐樹 （学生員）

2003 東工大・工・電気電子卒．2005 同

ing System, vol.7, pp.625–632, 1995.
[4]

神谷

Y.

Xue,

A.

大大学院総合理工学研究科知能システム科学専攻修士課程了．現在，同大学院総合理
工学研究科知能システム科学専攻博士後期課程在籍中．

Hartemink, L. Carin, and M. Figueiredo, “On semisupervised classiﬁcation,” Advances in Neural Information Processing Systems, vol.17, pp.721–728,
2004.
[6]

修 （正員）

T.M. Martinetz, S.G. Berkovich, and K.J. Schulten,

1993 東京大学大学院電子工学専攻博士““Neural-Gas” network for vector quantization and

課程了．博士（工学）．同年電子技術総合研究所，1999 から 1 年間米国カーネギー

its application to time-series prediction,” IEEE
Trans. Neural Netw., vol.4, no.4, pp.558–569, July
1993.
[7]

長谷川

メロン大学客員研究員，2001 産業技術総合研究所主任研究員，2002 東京工業大学

I. Muslea, S. Minston, and C. Knoblock, “Active +像情報工学研究施設助教授，2003〜2006

semi-supervised learning = robust multi-view learn-

JST さきがけ研究 21 研究者（兼任），情報処理学会，日本認ing,” Proc. ICML-02, 19th International Conference

知科学会，人工知能学会，IEEE-CS 等各会員．

3102