神野さんに言われました。

神野さんに言われました。

AIの勉強をしています @sesenosannko

AOJ-ICPCカテゴリー分け

AOJ-ICPCの問題で僕が解くときに使った解法(アルゴリズムなど)をまとめておきます。

僕が使った(または調べたら出てきた)というだけで、最適なのかは分からないのでご了承ください。 解けるとは思います。 空欄は特に典型的な手法を使ったつもりがないものです。 僕が知らないだけで何か名前があるかもしれません。

項目名を押すとソートできます。 「Search:」に入力するとフィルターできます。

難易度 問題 種類 補足
250 ポロック予想 DP
250 スクウェア・ルート
250 最短ルート DP bit DP
250 差分パルス符号変調 DP
250 The Secret Number DP
250 Cubist Artwork
250 Minimal Backgammon DP
250 Expected Allowance DP
250 Koto Distance 累積和
250 Manhattan
250 Squeeze the Cylinders DP 幾何
300 Cut the Cake
300 Gather the Maps!
300 Vampire 幾何
300 Line Gimmick
350 Curling 2.0 幅優先探索
350 Sleeping Time 二分探索
350 For the Peace
400 Cards 二部マッチング
450 Circle and Points 幾何

使ったもの

競技プログラミング サイト集

競技プログラミングに関するサイトのメモです。

問題のジャンル分け

主にICPCの問題のジャンル分けをしてくれているサイト。解く問題を選ぶときに参考にしている。

ACM/ICPC国内予選突破の手引き

AOJ ジャンル分けメモ - ひよっこプログラマのプログラミング

競技プログラミング練習問題集 - はまやんはまやんはまやん

AOJカテゴリー別問題集

幾何問題

geometry.txt · GitHub

カンニング

データ構造などをカンニングする。

アルゴリズム コード集

Spaghetti Source - 各種アルゴリズムの C++ による実装

Union Find木・パケット法・平方分割・セグメント木

プログラミングコンテストでのデータ構造

Dijkstra

Dijsktra's algorithm

競技プログラミングを始めた

前からほんの少しやってすぐに飽きていたんですが、今回はKPCCというサークルでみんなでやろうという感じなので少し頑張ってみたいと思います。 解いた問題とかのメモをします。

AOJ-ICPC一日一AC、毎週AtCoder参加がノルマです。

アカウント:AOJAtCoder

8月3日

8月4日

8月5日

8月6日

8月7日

僕が解法に悩んでいた問題がだいたいDPということを神野さんに教えてもらった。 DPは知っているんですが、未だに使いこなせない。 適当に簡単な問題を解いてみた。

あと、下のDPの問題を解いてみようと思ったらTLEになったので、仕方なく他の方が解いた回答を見たらほぼ同じだったのでPythonのせいで通ってないみたいですね・・・。 ここまで慣れているPythonで書いていたのですが、そろそろ限界みたいです。

8月8日

やっと今日はC++で書きました。無限に時間がかかりました。

今日得た知見としては、小さすぎる値で「2.82327e-09」とか出力されるとWA扱いになるみたいですね。iostreamで出力する場合は下のような感じでやるみたいです。少し面倒ですね。もう少しいい方法があると良いのですが。

cout << fixed << setprecision(6) << dp[T][N] << endl;

【Proton.jp】 C++:マニピュレータを用いた数値の整形

KCPPのLT会で使ったスライドです。

8月9日

解法はすぐに思いつくような問題ですが、string型の数字を比較する方法など、C++の書き方で丸一日悩んでしまいました。結局string型の数字を比較するのは以下のように関数を作ることにしました。compareの挙動も分かりづらいです。

bool former_is_bigger(string a, string b){
    if(a.size() > b.size() || (a.size() == b.size() && a.compare(b) >= 1)){
        return true;
    } else {
        return false;
    }
}

8月10日

簡単な問題ですが、C++でpair、sort、vectorを初めて使った。慣れない。

8月11日

DPで解くらしいが、制約が緩いので愚直に書いたら通ってしまった。勉強にならなかった。

8月12日

幅優先探索するだけなので1時間で解いてDijkstra法の勉強をするつもりだったが、無限にバグらせて時間がなくなった。 はじめてMLEが出た。 正直メモリをどれくらい使うのか意識していなかったが、地図ごとキューに入れるみたいな頭の悪いことをすると出てしまうみたい。

構造体やtypedefを初めて使った。 関数が配列を返せないのはとても不便。

D問題が解けなかった。 難しくはなかったが、僕の手が遅い。 あとは木の扱いに慣れてなさすぎるので、頑張りたい。

8月13日

簡単な問題を解いてDijkstra法をやるつもりだったが、やる気がなくなった。

8月14日

今日こそはDijkstra法をやる。

8月15日

Dijkstra法の問題が解けなかったので、とりあえず1問解いておいた。 最近、なかなか問題が解けない。 つらい。

今日もLT会がありました

8月16日

BitDP。やり方が分からず、かなり答えを見てしまった。 しかしだいぶビット演算の扱いが分かったので良かった。

O(n2)程度が限界。

普通のDP。

今日は実装が軽い問題を3個解いた。 練習としては良かった。 しかしDPは割とできるようになったので、最短路やグラフの問題を練習したい。

普通にユークリッド距離が1のときにマンハッタン距離が2になるということが数日分からなかった(頭が悪い)

8月17日

Segment木を初めて使った。 僕は無限に時間を使って書いたんだけれど、想定解は累積和というものを使うらしく、無限に頭が良かった。

AOJ 2600: Koto Distance - 宇宙ツイッタラーXの憂鬱

DP。 特定のテストケースだけWAが出るので原因が分からずにいたが、最初と最後の壁の処理で間違えていた。

愚直に解けばO(N)で間に合う。 調べたところ方針は現地点の左右の>と<の個数を数えるということで合っているみたいだが、 書き方が雑だったのでパネル数のカウントがややこしくなってしまった。

AOJ-ICPCの問題の横にある☆マークは良問であることを表しているらしく、この問題は星が7個もついているので解いてみたが、とても簡単だった。

幾何。簡単。

ICPCで解ける問題が減ってきたので、最短経路問題やフロー問題の典型題を解いていきたい。

8月18日

二分探索。 愚直にやるとO(230)でつらい。 いろいろ試そうと思ったけど、軽く枝刈りしたら通った(良くない)。

8月19日

幾何問題。 簡単だと思ったら、二つの円の交点を求めるところでつまずいた。 普通に調べてしまったけど、割と面倒だったのでこういうのをライブラリとして用意しておくんだろうか。 これくらいは導出しろという感じなんですかね。 分からない。

Dijkstra法。 簡単だけど、自分で書いたコードと人のブログに書いてあったコードがほぼ同じだったので嬉しい。

Warshall–Floyd法の練習。 Warshall–Floyd法そのままの問題。

最大フロー問題の練習として、二部マッチング問題を解いた。 ほぼ蟻本写経になってしまったし、最大フローを空で書けるようになるのは遠そう。

8月20日

とても簡単な問題だったがなぜか通らず、スタックを毎回クリアするのを忘れていた。 これに一時間くらい気付かず、辛い気持ちになった。

随時書き足します

TOEFLの勉強でやったことのまとめ

しばらくTOEFLの勉強をしたので、何をしたのか自分が忘れないようにまとめておくことにしました。

参考までに僕の点数は以下のような感じで変化しました。

R L S W total
2016/6 25 25 19 22 91
2017/4 26 30 22 26 104

単語はおなじみの3800のやつです。僕はRANK3までしかやっていないです。

【CD3枚付】TOEFLテスト英単語3800 4訂版 (TOEFL(R)大戦略)

【CD3枚付】TOEFLテスト英単語3800 4訂版 (TOEFL(R)大戦略)

他にも本はいくつか使いました。過去問とか日本語の本を数冊やり、あとはDelta本というものをやりました。 Deltaは出題形式や傾向がTOEFLと若干違いますが、問題をたくさん解く練習にはなります。 特にリスニングは本番よりも少し速めになっているので良い練習になります。

Delta's Key to the TOEFL iBT: Advanced Skill Practice

Delta's Key to the TOEFL iBT: Advanced Skill Practice

Reading

Readingは上のスコアを見てもらうとわかるように非常に苦手です。特にこれといった対策をしなかったので、点数も上がりませんでした。 単語力が足りないからかもしれないですね。

Listening

リスニングの練習は早い音源を聴きまくることとシャドーイングでかなり向上したと思います。

声を出しながら英語を聴くのは難易度が数段上がるので、シャドーイングに慣れることでリスニングが楽になります。

一番効果があるのはシャドーイングだと思いますが、集中力が必要なのでシャドーイングに疲れたときはとりあえず英語をたくさん聴きます。 上述のDeltaの音源のほか、時間があるときにはTEDやCNN等のニュース番組などを聴くようにしていました。 ニュースは速いので良いですね。 未だに難しいです。

Speaking

スピーキングも苦手です。 スピーキングはテンプレートを決めることと、やはりここでもシャドーイングです。

テンプレートはだいたい以下のチャンネルの動画を参考にしました。 これはTOEFLの公式動画なので間違いないです。

シャドーイングをする第一の理由は、僕のスピーキングが遅いからです。 詳細かつ具体的に説明しないといけないので、どうしてもある程度の長さの解答をする必要があります。 シャドーイングをすることで単純に早い発音に慣れたり、簡単な表現を素早く出力できるようにします。

シャドーイングは万能なので永遠にシャドーイングをするのが英語力向上への近道だと思います。

Writing

Writingは何故か点数が伸びずに悩んだパートです。 依然として低いですが、文字数制限にとらわれないことがポイントでした。

Writingはintegratedが150〜225ワード、independentが300ワードと問題文に文字数指定がされていますが、全く得点と関係ないようなので無視しましょう。 以前は律儀にこの文字数に従っていましたが、点数は伸びませんでした。

僕はintegratedは300ちょっと、independentは400〜500くらいで書いています。 Writingで一番大切なことはSpeakingと同じで詳細に具体的に書くことです。 integratedは言われたことを詳細に書くだけなので良いですが、independentが悩みどころだと思います。 僕はイントロ50ワード、ボディ理由2個各150ワード、結論50ワードくらいのイメージで書いています。 特に理由のところは2個にして具体例を100ワード近く広げるというところに落ち着きました。

日本人が何も考えずに書くと具体例よりも一般的な議論をしたくなる気がします。 たとえば「教科書は電子書籍であるべきという意見に賛成か反対か」という問題だとします。

僕が自然に理由を書くと「1個目の理由は持ち運びがしやすいことです。教科書は厚みがあって重いので〜。一般的な中学校・高校は授業数が〜。電子書籍であれば〜。電子書籍の重さは〜。」と誰にでも当てはまるような理由付けをしたくなります。

しかしTOEFLで好かれるのは「1個目の理由は持ち運びがしやすいことです。タブレット型端末を1個持ち運べば良いので何冊もの教科書を持ち運ぶよりも楽です。例えば、私の兄の高校では電子書籍の教材が導入されていますが〜。兄が中学の頃には〜。高校に入ってからは〜。」と自分や友人などの経験に基づいた具体例を詳しく延々と語り、兄が電子書籍が良いと言っていることを主張することらしいです。だいたいこれは嘘を書きます。僕には兄はいません。具体例を詳しく書くと自然に100ワード近く行きます。慣れると理路整然とした一般的な理由付けを考えるよりも楽です。

まとめ

シャドーイングを永遠にやりましょう。

自分の声を水瀬いのりさんの声にする他対1声質変換

僕は水瀬いのりさんになりたいのですが、まずは声から水瀬いのりさんになることにしました。

まだまだ満足とは言えない結果ですが一応音がでたのでまとめておきます。以下、変換の結果です。

元の音声(僕の声です)

変換後

合成音感がかなりありますが、言われてみれば水瀬さん・・・・と思ってもらえると嬉しいなぁ。むしろさとうささらへの変換だと思ったら良さそう・・・。強調したい点としては、僕の声は学習時には全く使っていないということです。この手法では学習に使っていない人でも誰の声でも水瀬いのりさんの声に変換することができます。

仕組みは下に書いてありますが、音声認識を応用した手法です。現状では学習データ量などの問題で音声認識の精度が低いので、ゆっくりはっきり話さないといけないし苦手な音が多いです。合成の質が低い理由もほとんどはデータ量の問題だと思います。


ちなみに、声コスプレという概念は既に提案されています。この川奈さんの記事は僕が音声分析を学び始めるきっかけになったものです。


参照した論文

2016年に発表されたパラレルデータが必要ない他対1声質変換の手法を提案した論文です。

http://www1.se.cuhk.edu.hk/~lfsun/ICME2016_Lifa_Sun.pdf

内容を簡単にスライドにまとめました。


音声処理の基礎的な話

このブログにいろいろと書いてあります。検索したら直ぐに出てくるし、有名なので紹介するまでもないですがかなり参考にさせていただいているので紹介します。


使ったもの

目標音声

ラジオ番組「水瀬いのり MELODY FLAG」第1回〜第5回、水瀬いのりさん発話部(音楽などが被っているものは除いてあります・約50分)。私的に録音したものです。原論文ではPPGからMCEPの変換の学習に100文の音声を使用したと書いてありますが音源の長さが明記されていません。


言語

自分で書いた部分は基本的にPythonです。


音声分析システム

MFCC・MCEPの抽出、MCEPからの音声生成にはSPTKという音声分析システムを使いました。提案論文ではSTRAIGHTが使われており、特に音声合成の方法は異なります。STRAIGHTの方が音声合成は高質ですが、STRAIGHTが僕のPCで動かなかったのとSPTKに慣れているため使いました。

Speech Signal Processing Toolkit (SPTK)


ニューラルネットワークライブラリ

提案論文では音素認識ではKaldi、音声生成ではCURRENNTというものが使われていますが、そもそも提案論文では設定がそれほど詳しく書いてあるわけではなく合わせる必要もないのでKerasを使います。Kerasは簡単に実装できることと、Bidirectional-LSTMが標準で実装されていることも大きいです。

Layer wrappers - Keras Documentation


コーパス

音素認識(PPGを生成する場合)では音声に対して時間ごとに発せられている音素のデータが必要になります。このようなデータは日本語でも存在しますが、私が知る限りは取得に数万円かかります。そこで、音声認識システム用ツールキットJuliusの「音素セグメンテーションキット」を活用します。日本語向けに開発をされていることが非常にありがたいです。

ちなみにJuliusは公式にはMac非対応ですが、一応使えます。

これを使えば、音声ファイルと音声をひらがなで書き起こしたファイルから、時間ごとに発せられている音素のデータを生成してくれます。スペースを入れる場合はテキストで明示する必要があること、音声ファイルの長さは30秒程度が限界ということは面倒な点です。結果で出力されるlab形式はWaveSurferという音声分析アプリのファイル形式ですので、WaveSurferで結果と音声を照らし合わせることができます。

以下は結果の一例です。有名な「あらゆる現実を」の文章です。幾つかの例を見た限りでは良い精度だと思います。

f:id:sesenosannko:20170319234404p:plain

音声ファイルと書き起こしのみのデータなら無料でも入手することができます。今回は音声資源コンソーシアムより研究用に配布されている「 重点領域研究「音声対話」 対話音声コーパス (PASD)」を使わせてもらいました。この記事の内容は所属しているサークルでの研究活動の一環なので、その名目で申請・取得したものです。およそ100分の音声を使用しましたが、空白部が多いので発話時間はおよそ50分程度でしょう。原論文で用いられているTIMITは630名の各10文(計6300文・約5.4時間)によって構成されるコーパスであることを考えても、これは明らかに不足です。コーパスには6時間程度の音声が含まれているのですが、学習に都合が悪いものや会話音声で二人の音声が被っている音源を除いたことなどが原因です。

PASD - 音声資源コンソーシアム


実装

データを除いてGitHubで公開しています。あんまり丁寧に説明とかはしていなくてすいません。

音韻モデル

提案論文ではPhonetic PosteriorGrams(PPGs)のクラスとして131個のセノンを用いています。セノンという言葉自体は日本ではあまり使われないようですがHMM音声認識で良く使われるもので、簡単に言えばトライフォンをクラスタリングしたものです。Juliusで論理トライフォンと呼ばれているものと同じだと思います。通常は数百個以上にクラスタリングされるようです。下記資料の「コンテキスト依存モデル」で基礎的な説明がされています。

https://www.gavo.t.u-tokyo.ac.jp/~mine/japanese/nlp+slp/IPSJ-MGN451003.pdf

しかし、今回の実装では音素をそのまま扱っています。この理由は、Juliusの音素セグメンテーションで認識される日本語の音素は空白を含めて36種類と多く、当初は音声生成はLSTMで行われることから効果が薄いのではないかと考えていたからです。しかし、音素認識がネックだと分かった現在ではセノンを使ったほうが精度が向上するだろうと考えているので、できれば替えたい思っています。

SI-ASR(音素認識)

提案論文ではKaldiの中間層4つ、全1024ノードのDNNモデルを使用しています。何を使っているのか明記されていないので良くわかりませんが、原論文には拘らずSI-ASRもBLSTMで作ることにします。

入力は39番目までのMFCC+エネルギー、出力は36種類の音素で試行錯誤の結果4層のBSLTM[40-128-128-128-128-36]に落ち着きました。全層に0.3のDropout層を加えています。入力サイズは40×2000フレーム(10秒分)にしていますが、適切な長さが良く分からないので適当に設定しています。単純に全ての音源を連結して10000フレームごとに切り分けています。バッチサイズは32ですが適当です。

PPGsからのMCEP生成

こちらもSI-ASRと構造に大きな違いはありません。提案論文では[131-64-64-64-64-40]というBLSTMが用いられています。いろいろと試した結果、入力は音素事後確率とlogF0(平均0、分散1に標準化)、出力は0〜39番目のMCEPとして[37-64-64-64-64-40]としています。なお、変換目標のMCEPは標準化しており、僕の学習では分散が過小評価されてしまっていたので出力の分散を1に変換した上で正規化の逆操作をしています。無理やりの手法なので、ここは本質的な改善をしたいとは思っています。Dropout率は全層で0.3、バッチサイズ32です。MCEPの数を変更した点についてはSPTKの仕様上の都合で特に意味はありません。

日誌

LSTMのあたりから日誌を書いていました。ただのメモですが、詳細を知りたい方はどうぞ。


これから

もっと精度を向上したい。

水瀬声質変換の日誌

思い出したように書き始めました。実際には3月15日あたりから音声分析ライブラリ周りを実装したりしました。

3月36日

SI-ASR部分の製作を継続。BLSTMは全く学習できなかった。おそらく実装にミスがあると思う。

ひとまず一方向のLSTMで学習をしてみる。1000×576の学習データで以下の結果。実際に適用すると精度が極めて悪いが、少なくとも母音や空白の場所程度はそこそこ認識している。BLSTMは本当に全く何も学習されなくて泣いていたので、少し安心した。以下、左が教師、右が出力。良いところだけ切り出したけど、認識が全くできていないところもある。

Epoch 40/40 576/576 [==============================] - 138s - loss: 1.1735 - acc: 0.6890 - val_loss: 0.7237 - val_acc: 0.8278

BATCH_SIZE = 64
MFCC_SIZE = 40
HIDDEN_SIZE = 64
PHONEME_SIZE = 36

model = Sequential()
model.add(LSTM(HIDDEN_SIZE, input_dim=MFCC_SIZE, \
                  return_sequences=True))
model.add(Dropout(0.3))
model.add(LSTM(HIDDEN_SIZE, return_sequences=True))
model.add(Dropout(0.3))
model.add(LSTM(HIDDEN_SIZE, return_sequences=True))
model.add(Dropout(0.3))
model.add(Dense(PHONEME_SIZE))
model.add(Activation('softmax'))

es = EarlyStopping(monitor='val_loss', patience=10, verbose=0, mode='auto')
mc = ModelCheckpoint('lstm/newmodel/weights{epoch:02d}.hdf5', \
                                      monitor='val_loss', save_best_only=False, \
                                      save_weights_only=False, mode='auto')

model.compile(loss='categorical_crossentropy', optimizer='rmsprop', metrics=['accuracy'])
model.fit(x_train, y_train, epochs=EPOCHS, batch_size=BATCH_SIZE,\
               validation_data=[x_test, y_test], callbacks=[es, mc], shuffle=True)

学習が止まったわけでは無いので学習を継続したが大きな変化はなし。

f:id:sesenosannko:20170326172403p:plain

改善できる点

  • データは50分程度しか使っていないので増やす
  • ネットワークは適当に書いたので改善の余地はある
  • データ事前処理

提案論文では音素認識の精度は70%とされる。val_accは見た目上0.8を超えているが、データの空白を除いていないので空白で精度が稼がれているらしい。なんとも言えないが、この精度だと音声生成には使えそうに無いので改善したい。

データの事前処理は平均0.5標準偏差1にしている。これに関しては何もわからないが、[0, 1]に正規化している例が多くあるので試している。

import scipy.stats as sp trainmfcc = sp.stats.zscore(trainmfcc, axis=0, ddof=1)+0.5

3月27日

昨日、いろいろと論文を読んでLSTMの構成を考えていた。あとデータを増やしていた。ということで新しいものを試す。

変更点

  • データを100分に増やした
  • 1データ2000フレーム(10秒)にした
  • 中間層を128ノードにして1層増やした
  • Dropoutを最終層のみに適用した(どっかに書いてあった)
  • 一般的な標準化(平均0、分散1)にした

元のデータを検査したら長すぎる音声について音素セグメンテーションがうまくいっていないものがあったので取り除いた。

上記のネットワークの結果としてはval_accが最高で0.901を超えた。出力結果としてもそれほど悪く無いように見える。半分空白だとしても7割くらいの正答率は出ているのでは無いだろうか。そのあとにいろいろと試した結果、Dropoutは全層に0.3かけた方が少し改善してval_accは0.909になった。まぁ誤差かもしれない。

f:id:sesenosannko:20170327131552p:plain

それなりにまともに認識された部分。「けども」と発話されている部分の一部で、左が出力で右が教師データ。子音は難しいようで、無音(sil)や似ている子音に判定される場合が非常に多い。無音と母音で正答率が稼がれているように感じられる。ただ、「do」が「無音to」と誤判定されるのは理解できる気もするので音声生成のデータとしては許容範囲なのかな。実際、話者認識も言語モデルを用いなければ使い物にならないらしいので、単純な音素認識ではある程度限界はあるのだとおもう。

水瀬いのりさんの声で試してみた。訓練データよりも明らかに早口(コーパスは比較的丁寧に話しているので)ということもあるからか、認識精度が壊滅的。音声生成に使えるとは思えないなぁ・・・

3月28日

BLSTMに再挑戦する。前回はStatefulにこだわったため実装に失敗したが、単純なものならばKerasではlayer wrapperで直ぐに作ることが出来る。そして、val_accは0.927を超えた。驚異的だ。訓練データではかなり精度が良い。しかしやはり水瀬いのりさんの声では、前回よりは改善したとはいえ難がありそう。しかしこれ以上の向上には根本的な改善(データ量など)が必要そうなので、とりあえず現状で音声生成が可能なのかを試してみる。

そういえば、KerassのBidirectionalにはバグがあるので注意しないといけない。

音声生成部についてはほぼ論文のままの構造。つまり、音素認識がまともならば可能なはず。結果は以下のようになっていた。上が出力、下が元のMCEP。

f:id:sesenosannko:20170328182925p:plain

正直、音素認識があれだけ低質だったので、一応まともな出力がされたことには驚いた。しかし、音声合成をすると全然ダメ。

これが元の音声。

以下が出力。ターゲットは水瀬いのりさん。

いのりさん以前にほとんど声になっていない。すごく頑張れば分からないでもないが、ほぼ基本周波数でもこれくらいの精度は出る気がする。ただ、音質がひどいのはsptkの問題もあると思うので他の音声分析アプリを使うことも検討したい。

3月29日

直接スペクトル包絡を出力してworldで変換するという手法も試してみたが、精度が向上しなかった。とりあえずはsptkに賭けることにする。

次に、入力にlogF0を追加してみる。logF0に適したMCEPを出力してくれるとありがたい。情報量としては大きいはず。logF0は平均と分散を水瀬いのりさんと合わせるだけなので、他の人からの変換時にももちろん入力することが出来る。logF0+PPGsで入力は37次元となる。logF0は水瀬いのりさんに平均と分散を合わせた上で、平均0標準偏差1に標準化する。

実は前回のlossが保存されていなかった。だからどれくらい改善されたのか数値ではわからない。頭が悪い。明確な改善とは言えないまでも形は良く再現されているように見られるが、平均も分散も合っていない。出力(教師データ)については良く分からなかったので標準化していないが、標準化が必要かもしれない。

f:id:sesenosannko:20170329234826p:plain

f:id:sesenosannko:20170329170333p:plain

まず、波形の再現度を確認するために平均と分散を無理やり合わせてみた。声質変換としてはあまり参考にならないが、以下のようになんとか水瀬いのりさんと判定できるような声になった。これ以上の精度は音素認識やデータ量の問題とかだと思うので、当面の目標はこれになりそう。

3月30日

出力の標準化をした。しかし、分散はやはり小さいままであった。そのため、無理やりで良くない手法ではあるが、出力結果について再度分散を1に変換した上で標準化の逆変換をすることにより分散を強制的に合わせることにした。どのような出力についても同じ変換をしている割には、波形を見るとうまくいっているように見える。

f:id:sesenosannko:20170330172950p:plain

水瀬さんの声を入力してみると、昨日の手動で合わせるものよりも良く再合成されている。これは出力の標準化によって精度が上がったと考えられる。というのも、出力(目標)を変えてしまうと誤差の値が変わってしまうので数値的には向上したのかが良く分からない。そして、子音がかなり変わってしまっているので、音素認識にも大きな問題があるということがわかってきた。後半の内容が支離滅裂。

f:id:sesenosannko:20170330171713p:plain

そして、これを使って変換した結果がこちら。上は僕の声。

合成音感や子音の精度の悪さが目立つが、言われれば水瀬いのりさんの声のようにも感じるのではないでしょうか?音声の課題では作っている人は音がそもそも出ない段階から聞いているから出力への評価が甘々になり、最終結果を他の人に聞かせると微妙な反応をされるというのはあるあるらしいので悲しいところですが。

疲れたし、学校が始まってしまうのでここで一区切りをつけることにする。

TDAの概要と入門書の紹介

こんにちは。さんこです。

情報幾何と同様に、TDA(位相的データ解析)の概要と僕が読んだ入門書を紹介します。書籍は下の方に紹介してあります。

情報幾何の記事はこちら


TDA(位相的データ解析)とは

TDAとはトポロジーを用いてデータを分析する手法です。トポロジーの中でも持続性トポロジーと呼ばれるものが主な道具となります。

厳密に定義したり、多次元一般化したり、実際に計算をするとなるとまさに代数を用いることになるので難しいですが、考え方は簡単です。様々なサイトでTDAの概要の説明が行われているのでここでは省きます。例えば、以下の記事にTDAの簡単な概要が書いてあります。


TDAは何がすごいのか

TDAトポロジーをデータ分析に応用するというだけで面白そうではありますが、どれほど有効なのかは一見すると良くわかりません。具体例を紹介しつつ見ていきましょう。

まず、 TDAには適用対象に注目して以下の二種類に分けられます。それぞれ異なる性質を持っているので別々に見ていきます。

  1. 各データ自体の幾何構造に注目するTDA
  2. データ全体の幾何構造に注目するTDA


各データ自体の幾何構造に注目するTDA

各データ自体の幾何構造に注目する場合、データ自体が幾何的な構造を持っているものが対象になります。例えば、タンパク質などの高分子化合物や画像認識への適用があります。

タンパク質への適用がわかりやすいので紹介します。タンパク質の各原子の位置とファンデルワールス半径のデータが与えられているとします。ここで、各原子をファンデルワールス半径の x倍の球として扱うと自然に持続性ホモロジーが導入されます。各原子と中心を共有する球をだんだん拡大していくと分子全体としての位相的性質が変化していくことが分かります。以下の図のようなイメージです。

簡単に言えば、半径がファンデルワールス半径のa倍からb倍のときまでは穴が10個で、b倍からc倍のときまでは穴が7個でした、といったようなことが分かります。この位相的性質の変化を特徴量として用います。

『タンパク質構造とトポロジー』によればタンパク質内部の空洞の大きさや個数はタンパク質の性質と大きく関わるらしく、トポロジーを用いることには理論的に妥当性がありそうです。実際に生物の種ごとのホモグロビンの違いを捉えるなどの例ではうまくいっています。

このTDAの使い方も面白いですが、適用例が限られるのが難点でしょう。TDAが注目されているのは個々のデータ自体の幾何構造に対する適用ではなく、主に次の節の手法だと思います。


データ全体の幾何構造に注目するTDA

データ全体の幾何構造に注目するTDAはビックデータへの応用が目的とされています。多次元でサンプル数が非常に多いデータの位相的性質に注目することで、データの分析や視覚化に適用されています。

しかし、タンパク質の例のようにデータを中心とする球を考えるのはビックデータに適用するには計算量が多すぎるだろうということは容易に想像できます。この欠点の克服のためにwikipedia(英語)にあるように様々な工夫がなされてきたようです。ここでは、Ayasdiで用いられているMAPPER(提案論文)と呼ばれる手法を紹介します。

AyasdiとはTDAの研究やTDAを用いたデータ解析を専門に行っている会社です。この節は以下の資料の内容をまとめたものです。


MAPPERによるグラフの作り方

MAPPERの概要です。混乱を招きそうですが、MAPPERは持続性ホモロジーを用いた手法ではありません*1。MAPPERでは元のデータと同じ位相構造を持つグラフを構築する手法です。データの位相構造に注目している点には変わらないので、これもTDAと呼ばれるようです。

それでは、MAPPERにおいてデータからグラフを作る方法を説明します。下図のようにデータを何らかの軸に対して切り分け、切り分けた区分ごとにデータをクラスタリングして各クラスタをノードとします。実は各区分はぴったり切り分けられているわけではなく、のりしろがあります(端っこのデータは隣接するどちらの区分にも含まれている)。そこで、のりしろを介してデータを共有しているノードがあれば繋ぎ合わせます。のりしろが大きければ1つのノードがいくつかのノードと繋がれることもあります。

切り分ける軸、区分の大きさ、のりしろの大きさは結果を左右する大きなポイントとなります。また、データ間の近さを表す計量にはユークリッド距離の他にも様々なものが使われます。これらがMAPPERにおけるパラメータと言えるでしょう。また、区分ごとのクラスタリングには単連結法などの既存のクラスタリング手法が用いられ、区分の大きさに応じてクラスタリングの打ち切り基準が決められます。


MAPPERで得られたグラフの応用

作られたグラフによってデータの幾何的構造を得ることができました。データから得られる幾何構造が既存の機械学習手法に比べて優れているの以下のような点です。

  • 機械学習では人が決めるモデルに結果に大きく影響されるが、TDAでは事前に人が決めることにが少ない
  • 機械学習では結果は得られても過程は失われるが、TDAはデータ全体の構造が保持される
  • ビックデータと相性が良い(次元削減など)
  • 視覚化が容易

この性質を生かして、グラフそのままデータの分類や分析に適用もできます。特にビックデータの視覚化は多くの適用が期待されます。次元削減という点では、PCAなどでは射影によってデータの性質が失われることは多いですが、MAPPERではデータの幾何的性質を保持すると主張されています。

また、MAPPERで得られたグラフを用いて既存の機械学習システムを分析したり改良したりする手法が提案されています。面白い適用例を2つ紹介します。

  • 分類器の実証

従来の機械学習システムで分類器を作る場合は、モデルの構築のミスや学習の予期せぬ挙動などで期待した通りの分類器ができるとは限りません。また、そのような問題が起こっていても人間が気づきにくい場合も多くあります。この問題を解決するためにMAPPERによるデータの可視化を活用します。

まず、機械学習システムに入力するデータをMAPPERでグラフ化します。そして、このグラフに対して機械学習システムの分類を適用して、分類ごとに色分けなどをします。すると、グラフ上の各ノードに対してどのように分類されたかが分かります。グラフのノードは似たデータの集まりであると期待されるため、単純に考えれば単一ノード内のデータは同じように分類されたり、グラフ上で遠いノードは異なる分類であると予想されます。分類器がこれと大きく異なるような分類をした場合は検証が必要となります。このようにデータの視覚化を用いることで機械学習システムの動作を確認することができます。

ただし、もちろん必ず分類器の誤りを検知できるわけでもありませんし、MAPPERのグラフに対して違和感があっても必ず誤っているわけではないでしょう。Ayasdiではこの手法はあくまでデータの中で注目すべき点を指摘するだけと説明しています。とはいえ、既存の機械学習システムの動作を人間が視覚的に捉えられるのは大きな利点と言えそうです。

  • 分類器の向上(モデル作成)

あるデータを分類したいときに、普通はデータ全体に対して一つの分類器を考えます。しかし、複雑な分類を行うのは当然難しいので、データの一部に対する分類器を作るのが一般的に簡単だと考えられます。つまり、同じ手法であればデータに対して複数の分類器を作った方が精度が向上すると考えられます。ここで問題となるのがデータの分割法ですが、MAPPERのグラフの各ノードごとに分類器を作るという手法が提案されています。

この2つの他にも様々な手法が提案されています。このように、MAPPERももたらす合理的なクラスタリング・次元削減・視覚化がビックデータの解析に新たな手法を生み出すことが期待されているようです。


書籍紹介

集合・位相の基礎や多様体論は前提とされていますが、下記の書籍の内容に限定すれば事前知識がなくても理解できると思います。この範囲で僕が読んだものは情報幾何の記事で紹介したものです。

トポロジー

トポロジー:柔らかい幾何学

トポロジー:柔らかい幾何学

トポロジー:柔らかい幾何学

位相幾何学の基礎的な話からホモロジー論を感覚的な理解に重点を置いて説明している書籍。特に4章以降の内容は「タンパク質構造とトポロジー」と多くの内容が被りますが、こちらの方が紙面を多く割いていることもあり具体例も多く分かりやすいと思います。

持続性ホモロジー

タンパク質構造とトポロジー

タンパク質構造とトポロジー ―パーシステントホモロジー群入門― (シリーズ・現象を解明する数学)

タンパク質構造とトポロジー ―パーシステントホモロジー群入門― (シリーズ・現象を解明する数学)

現状では日本語でほぼ唯一のTDA入門書だと思います。良著だと思いますが、120ページ程度で基礎的な部分から説明されているのでそれぞれの内容が懇切丁寧に説明されているわけではありません。また、ここで説明されているのは各データ自体の幾何構造に注目するTDAです。データ全体の幾何構造に注目したTDAは上で紹介したAyasdiの記事などを参照するのが良いと思います。

最後の Z_2[x]加群のあたりが重要なところですがあまり理解できていないので、 そのうち群論の基礎から学び直したいと思います。

*1:提案論文等を読む限り正しいですが、wikipediaには持続性ホモロジーを用いた手法と書いてあります。見かけ上は違いますが、実際には持続性ホモロジーを扱っているということなのでしょうか。ご存知の方がいらっしゃればご指摘いただけると助かります。