機械学習パイプラインのデバッガについての論文:Debugging Machine Learning Pipelines

タイトルの通り、機械学習パイプラインのデバッグを行うツールを開発した論文「Debugging Machine Learning Pipelines」を読んだ。
International Workshop on Data Management for End-to-End Machine Learning というワークショップで発表されている。

概要

機械学習システムの失敗原因はコードのバグや入力データ、パラメータ設定など様々な原因が考えられる。特にパイプラインが複数になったりすると原因箇所の特定が非常に難しい。

そこで、ML Systemにおけるfailureの原因を推測して簡潔な説明を提供する仕組みを開発。

機械学習パイプラインの例

具体的には、前回までの実行時の情報と結果や、まだテストされていないパラメータ値を提案することで原因を突き止めやすくする。このツールによって、データ、データ型、ライブラリバージョン、パラメータ値などの側面でパイプラインをチェックできる。

実際のアルゴリズムとしては、いくつかのパイプライン実行からエラーっぽい実行結果を抽出して、未テストのパラメータ群をある時間制約の中で実行して原因を突き止める。最終的に、複数の原因が見つかったら、最小限の原因をブール式の形で提示する。

処理の説明

色々と定義が書かれているが、簡潔に言うと、以下の通り。

  • MLパイプラインのプロパティを設定してCVの値が一定以上なら成功とする。
  • 成功した時のパラメータ、失敗した時のパラメータからどのパラメータのときに失敗するのかの候補を最小限のブール式で提示する。

具体的には決定木のように条件文を構築して、上手くいった場合のプロパティと失敗した場合のプロパティから最小の原因となるブール式を求めている。
作成された決定木は重複部分が多く出てきて可読性が悪いため、Quine-McCluskeyのアルゴリズムというものを使って、まとめられる部分をまとめてブール式にする。

決定木形式での原因特定

既存の研究との違いは、このML Debuggerは上手くいかないケースを探すことにある。既存研究は上手くいくプロパティの設定を探すが、著者らは最小の原因を探すためには上手くいくケースはあまり役に立たないためであると論じている。

実験結果

FineOneという原因の少なくとも一つを当てるタスクではF値1.0と他のフレームワークよりも良い結果が出ている。試行回数を制限するケースではF値は1.0よりも下がるが、依然として他のフレームワークよりも良い結果が出ている。全ての原因を見つけるFindAllというタスクでも同様の傾向が出ている。

実験結果の一つ。他のフレームワークよりも良い結果が出ている

他のフレームワークとの比較を考察すると、最小の原因群を出すのが苦手だったり、否定や不等式が扱えないなどの欠点があることが分かった。

所感

他のフレームワークはベイズ最適化のような手法を使ってパラメータを探索するものもあるというが、本手法は特にベイズ最適化などを用いることなく、失敗したところの近傍を調査するという手法で良い結果が出ているのは面白い。

データサイズが大規模になると、このようにイテレーションを回して原因を追及するということが、本質的に難しくなりそうなのでそのような場合を想定した研究を探してみたい。

著者らは今後の方向性として、何らかの実行環境に組み込んでユーザに使ってもらうことを考えているというので、近い将来このようなフレームワークを使って機械学習パイプラインをデバッグする時が来るのだろうか。

Embeddingの違いによる後段タスクへの影響推定:Understanding the Downstream Instability of Word Embeddings

MLSys 2020の論文より。Embeddingが異なった場合、後段のNLPタスクに対してどれだけの影響があるかを、後段モデルの訓練を行わないで推定しようという論文の「Understanding the Downstream Instability of Word Embeddings」を読んだ。

概要

トレーニングデータが少し変わっただけでモデルの性能が不安定になったりする現象がある。この論文では、自然言語処理モデルにおいてEmbedding層のサイズとトレーニングデータの変更による性能低下に関係性があることを調査した。
そのような関係性を、理論的に説明するために、eigenspace instability measureという指標を導入して後段の予測がどの程度変わるかを予測することができることを示した。

この手法は、 knowledge graph や contextual word embeddingのような他のembedding手法にも、この指標は拡張できることを示している。

そもそも、word embeddingが近傍何単語でトレーニングするかといったパラメータによって大きくパフォーマンスが変わってくることが分かっている。しかしその影響が、後段のNLPタスクにどの程度の影響が出るかが検討されていなかった。

例えば、embeddingのトレーニングに1%のデータを追加しただけで、感情分析タスクで15%の違いが出るようになった。この論文では、メモリ使用量とのトレードオフも調査されており、2倍のメモリを使うようにしたところ5~37%程の性能低下を抑えることができるようになった。

この論文で提唱されている、eigenspace instability measureは二つのword embeddingの固有空間がどれだけ重なるかを表した指標である。これを用いると、どの程度embeddingが変化したかが分かり、さらに下流のモデルを再学習することなくdimension-precisionパラメータを選択できるようになる。

この指標は他の指標で選んだパラメータに比べて、後段のタスクの性能低下が少なく済んでおり、なおかつ理論的にこの指標とモデルの性能に関係性があることを示している。

前提

WordEmbeddingのアルゴリズムの解説や、 圧縮技術としてuniform quantizationを利用などが解説されている。

また、WordEmbedding同士の距離の測り方として、以下の4種類を活用して比較実験している。

  • k-Nearest Neighbors(k-NN) Measure
    ランダムにサンプルされた単語に対してk個の近い単語を2つのEmbeddingから出して、どれだけ重なりがあるかを測る指標
  • Semantic Displacement
    Orthogonal Procrustes Problemを解いて、二つのEmbeddingが近くなる変換行列を求めて、それをかけたときのコサイン距離の平均を取る指標
  • Pairwise Inner Product Loss
    二つのEmbeddingのグラム行列同士の差分をノルムを取った値
  • Eigenspace Overlap Score
    特異値分解して得られた行列U同士を掛け合わしてノルムを取った値

実験

Semantic AnalysisとNamed Entity Recognition のタスクを後段として実験している。 Embeddingの次元数を25, 50, 100, 200, 400, 800と変化させて実験。Precisionも1bit~32bitまで変化させて性能がどう変わるかを確認している。

コーパスにはWikipediaの17年と18年のデータセットを用いて、コーパスが変わったとみなしてどれだけ相違があったかを示したのが、論文中Figure1。

次元数とPrecisionが上がるにつれて、相違が減る傾向が見て取れる。Precisionが4bitを超えたあたりから影響は小さくなってきている。若干の違いではあるが、2倍精度を上げた方が、2倍の次元数にするよりも性能低下が抑えられている。同じメモリ消費量であっても、トレードオフ関係で相違が3%位出ることもある。

Analyzing Embedding Instability

Eigenspace Instability Measureという指標を定義している。これは、各Embeddingを特異値分解して左特異ベクトルの張る空間がどれだけ重なっているかを示す指標となる。

このように定義するとそれぞれのEmbeddingを利用して訓練した線形モデルの誤差の差分がEigenspace Instability Measureに比例することが証明できるという。

実験してみるとk-NN指標と同等程度の結果となっている。k-NN指標は理論的な裏付けがないため、本提案の方が優れていると主張している。
そのほかにもknowledge graph や contextual word embedding(BERT)のような他のembedding手法にも、この指標は拡張できることを示している。

所感

2つのEmbedding間の後段タスクに与える影響を、後段のモデルをトレーニングすることなしに予測できるのは、どのEmbeddingを使えばよいかの選択に有用だと感じた。理論的なバックグラウンドがあるのが本手法の優れたところと著者らは主張しているが、k-NN Measureも直観的には2つのEmbeddingがどれだけ近しいかを表していると理解できるように思え、なおかつk-NNの方が全体的に精度が良いタスクがあるため、常にこの論文で提案されているEigenspace Instability Measureを使えば良いというわけでもなさそうである。

ニューラルネットワークのPruningをメタアナリシスした論文:What is the State of Neural Network Pruning?

MLSys 2020という学会で発表された面白そうな論文を読んだ。タイトルは「What is the State of Neural Network Pruning?」で、Neural Network Pruningについてメタアナリシスを行った論文。

概要

pruningに関するメタアナリシス論文。標準化されたベンチマークやmetricsが無いことが分かった。そこでShrinkBench(https://github.com/jjgo/shrinkbench)というオープンソースのpruning評価用のフレームワークを作成した。

著者らは81本のpruning論文を調査したところ、データセットやネットワークの比較の無いものや、他のpruning技術との比較が無いものなどが多く、適切にどの手法が良いのかを比較することが難しかった。

Pruningについて

pruning手法は大体pruneとfine-tuneを繰り返す手法が多い。 pruneの仕方にはsparsity structure, scoring, scheduling, fine-tuningの4つの観点で選択ポイントがある。

structure

ランダムにパラメータを削減する手法だと、現代のH/Wでは速度向上につながらない可能性がある。そこで、何らかの構造的なグルーピングからパラメータを削減する手法がある。

Scoring

重みの係数やgradientsなどから不要なパラメータを抽出するのが一般的。局所的にスコアを比較する手法や、大局的にスコアの低いパラメータを探し出すなどの手法がある。

Scheduling

何ステップごとに枝刈りを行うかも一つのポイント。複雑な関数によってSchedulingを決定する手法も出てきている。

Fine-tuning

枝刈り前の状態からファインチューニングするのが一般的だが、もっと前の段階や初期状態からファインチューニングする手法も提案されている。

評価指標

ストレージサイズを重視するのか、推論速度を重視するのかなど、様々な指標が存在しうる。そこには効率と質のトレードオフが存在する。FLOPsや画像分類のTop-1~5の性能で測られることが多い。

Lessons from the Literature

Pruningの効果

論文を調査していくと、pruningは効果があるということが分かった。小規模なpruningによって性能が向上した例もあったという。
ファインチューニングする手法の方がランダムに初期化して再学習するよりも効果的な例の方が多い。
パラメータ数を固定して比較した場合、スパースなモデルが密なモデルよりも性能がいいことがある。
しかし、モデルアーキテクチャを改善した場合(ResNet vs VGGのようなケース)の方がpruningよりも効果的な傾向にあった。

Missing Controlled Comparisons

しっかりとした比較が行われることが少ない。これは標準化された結果報告基準がないためだろうと述べている。

2010年以前の論文と比較されづらいのに加えて、近年の手法であっても比較されていない論文は多い。データセットもImageNetやMNISTで比較されることが多いが、MNISTはグレイスケールだし単純なモデルでも99%の精度が出たりするので、実験対象として適切ではない。データセットと評価指標が論文によってバラバラなので適切に比較することが困難である。また、モデルやデータセットが同じであっても、augmentationやハイパーパラメータ、使用するライブラリによって差が出るので直接比較が難しい。さらに、微妙な違いであっても、改善率1%以下を報告している論文が多いので、もともとのモデルの性能で大きく結果が左右されることになる。

そのほかにも、ResNetやVGGと述べられても、複数のバリエーションが存在するので一意に特定することができない。また酷いものだと存在しないようなアーキテクチャを既存のモデルとして述べているようなものもあったという。

それに加えて、 モデルの圧縮率や速度向上も論文によって微妙に定義が異なっていることもあり、比較の妨げとなる。

ではどうするか?

著者らは以下のような指針を定めて、手法を比較することを提案している。

  • アーキテクチャ・デーセット・メトリクスを正確に決める。
  • 少なくとも3つのペアの大規模データセット・最近のモデルで比較する
    圧縮率と速度向上の計算式を定義する
  • ImageNetではTop-1とTop-5を報告する
  • メトリクスを報告する際は、prune前のモデルの同じメトリクスを報告する
  • 比較対象とする手法と一緒にトレードオフのカーブを図示する
  • トレードオフカーブは5段階の圧縮率でプロットする
  • 報告する数値は平均と標準偏差も出す
  • 同じライブラリ、データ読み込みなどできるだけコードを比較対象とそろえる。

これらの比較が出来る環境としてShrinkBenchというフレームワークを作成している。

ShrinkBenchを使って実験したところ、以下のような発見があったという

  • 圧縮率と速度向上のトレードオフは完全に相関するものではない。なのでどちらか一方だけではなく、両方を報告する必要がある。
  • データとモデルの組み合わせによって、有効なpruning手法が変わる場合がある
  • 初期モデルの重みによって手法の優劣が変わる場合がある。
手法比較の一例
圧縮率と速度向上は必ずしも完全な相関関係にあるわけではないことを表している。

所感

pruningは近年非常に重要な研究分野で論文も多く出ているが、このようにメタアナリシスを行うとどの手法が良いと一概にいうことは難しいかもしれないと感じた。

ただ新しい手法を考案しても計算量の問題もあって多くの既存研究と比較するのはコストが大きいため、この論文で提案されているようなShrinkBenchのようなフレームワークを研究者が活用して、統一的なスコア報告がなされるようになると研究がもっと進みやすいかと思われる。

対話生成におけるマルチカリキュラム学習の活用論文:Learning from Easy to Complex Adaptive Multi-curricula Learning for Neural Dialogue Generation

AAAI 2020の論文「Learning from Easy to Complex: Adaptive Multi-curricula Learning for Neural Dialogue Generation」より。

概要

カリキュラム学習を用いた対話生成の手法に関する論文。一般的なカリキュラム学習では一つの指標に応じてComplexityを決定して、易しい順に学習を進めていくが、対話生成においては単一の指標で複雑さを測れるものではない。

そこで、複数の複雑度指標を定義して、対話の複雑度を測定できるようにした。作成された複数(この論文では5つ)の複雑度指標を用いて multi-curricula学習によって、学習状況に応じて異なったcurriculaを自動的に選択することで学習を進めていく。

背景

例えば、既存のデータセットである、OpenSubtitlesには学習が難しい受け答えデータが含まれている。そのようなデータに対していきなりモデルが学習を行うことは難しい。

そこで、人間の子供のように簡単なデータから難しいデータへと学習していく方針を考える。これはいわゆるカリキュラム学習と呼ばれる分野であるが、対話システムのデータの場合、他のタスクと違って、単一の複雑度というものを決めづらい。そこでこの論文では5つの側面から複雑度を設定して、5つのcurriculaを作成している。

5つの指標

Specificity

対話システムは得てして、一般的な回答を返しがちである。できるだけ特定の会話内容に対しての返答を行ってほしいのでSpecificityという指標を考える。Normalized IDFを回答の中の単語に対して計算して平均を取る。それをSpecificityとして考える。

Repetitiveness

同じ単語ばかり使って回答を生成するよりも、いろいろな単語を使って回答を生成している方が文章の複雑度は高いと考えられる。そこで、過去に使った単語をどれだけ繰り返しているかというのをRepetitivenessという複雑度指標として考えることができる。

Query-relatedness

質問に対して関係する回答をしているかどうかというのは複雑度指標として使える。具体的な計算方法としては、質問と応答の文章の類似度を埋め込み表現のコサイン類似度を取ることで計算する。

Continuity

Query-relatednessと近い概念だが、応答に対する次の文章がどれくらい類似しているかを計算することで、会話が一貫してつながっているかを考えることができる。これも同じようにコサイン類似度を取ることで複雑度指標と考えることができる。

Model Confidence

モデルの出力の確信度も、回答についての難易度を示すものになると考えられるので、複雑度の指標として用いることができる。

これら5つの属性は相関を計算すると、ほとんど相関が無いことが分かるのでこれらの指標の取り方は良さそうだと考えられる。

5つの属性を活用するために、Adaptive Multi-curricula Learningを提唱。各カリキュラムからのデータ取得はバリデーションデータに対するモデルのパフォーマンスに応じて決定される。 決定方法は強化学習の考え方を使って決める。

実験

実験は3タスクについて、各5モデルを実行しているが、ほぼ全てのケースでこのカリキュラム学習方式を導入した方が性能向上している。人間による主観評価でも、4割以上は良いと評価され、4割程度は優劣つかなかったので、全体としては今回の手法が主観的にも良い結果を出しているといえる。

Ablation Studyとして、5つの属性のうち1つだけ使ってみた場合もそれぞれ検討されているが、全体的に5つすべての指標を使ってカリキュラム学習した方が性能が良い。そのほかにも強化学習ベースの代わりにランダムポリシーを使った場合と、難しいものから先に学習する場合が実験されているが、どちらも今回の提案手法には及ばない。

所感

カリキュラム学習の考え方は人間の学習に関する方法からアイデアを受けているが、確かに一つの指標からデータの難易度は決められないと思うので、今回の複数指標を用いたカリキュラム学習で性能向上するのは直感にあっている。

今回の複雑度指標は、データセットから計算できるものであるため、人手による難易度付けが不要なため、その他のタスクについても活用できる部分があるのではないかと感じた。

文字認識をWatermarkで騙す手法の論文:「Attacking Optical Character Recognition (OCR) Systems with Adversarial Watermarks」

Attacking Optical Character Recognition (OCR) Systems with Adversarial Watermarks」という論文を読んだ。

概要

OCRシステムを騙すためのAdversarial Exampleを作成する手法の論文。OCRにかけるような文書は写真などとは異なり背景が白・文字が黒、となっているので写真データに対するAdversarial Exampleの手法を使うと、人間が見ておかしいことに気づく。
そこでこの論文ではWatermarkと呼ばれるスタンプを文書に付与することで、文書読み取りの結果を改変することを目指している。
Watermarkは例えば「Sample」や会社名みたいなスタンプを文書に重ね合わせる。そのWatermarkと重なる部分のピクセルを上手い具合に変えると、文書の意味を反転するような形でのAdversarial Exampleをいくつか作成できている。

基本的には評価はモデルがホワイトボックスだと仮定したうえで行っているが、ブラックボックスのOCRシステムとしてTesseract OCRに対してもWatermark を付与したAdversarial Exampleが働くことを確認している。ブラックボックスシステムに対しては、ホワイトボックスモデルに対してAdversarial Exampleを作成して、そのAdversarial Exampleを入力とすることで確認している。

アルゴリズム

具体的なアルゴリズムとしては、元文書とAdversarial Exampleのノルムを閾値以下である・Watermarkの中に含まれるピクセルをのみを変更する、という制約の下でCTC loss functionと呼ばれる最終層で出力される値から正解のデータ列になりうる確率を元に計算する損失関数を最小化するように最適化問題を解いていく。論文では、再急降下法+モーメンタムのようにして文書ベクトルを更新していくと述べられている。

実験結果

具体的な実験では以下の図のように、いくつかの文の意味を変えるように改変することができたことを示している。免許証の番号を変える例も示されている。

Future Work

この論文ではWatermarkの位置は固定なので、任意の箇所を改変できるようになっていないが、今後は自由な位置・形状でWatermarkを追加することも考えている。

所感

WatermarkがつけられたらそもそもOCRは上手くいかなさそうなので、Watermarkがついた部分は人間がチェックするべきではないかと思った。手法としてWatermark付与以外にも文字のエッジの部分を改変することで、印刷がかすれているように見せかけて人間とOCRを騙す方法も述べられており、これが進んでいくと悪用される可能性もありそうに思った。

論文読み:Squeeze-and-Excitation Networks

元論文:Squeeze-and-Excitation Networks

最近良くCNN関連のタスクでよく使われる手法なので、論文を読んでみたときのメモ。
ググると他にも詳しい解説記事があるので、あくまでも個人的なメモとして残します。

概要

Squeeze-and-Excitationブロック(SEブロック)というモジュールを導入することで、明示的にチャンネル間の相互作用をモデル化できる手法。
チャネル間の相互作用はイメージがつきにくかったが、例えばある特徴マップとまた別の特徴マップが同時に強く反応する場合に、特定のクラスと判定されるといったケースだろうか。チャンネル方向でSEブロックの処理を行うことで、チャンネル間の相互作用を表せるということのようだ。
SEブロックい色々なCNNに組み込んだSENetは様々なデータセットに対して効果的であったことを確認した。既存のCNNに少しの計算コストを追加するだけで性能を高めることもできた。

Introduction

CNNは画像認識の分野で広く使われている。CNNは畳み込みフィルタによって局所的な特徴をつかみ、層を重ねることで局所から大局までの広い範囲の画像特徴をつかむことができる。近年は高精度なネットワーク構造を作ることが研究のフロンティアであるが、いくつかの研究では既存のネットワークにモジュールを追加することで精度向上を目指す取り組みもある。

この論文で提案されたSEブロックはそのような取り組みの一つにあたる。SEブロックは特徴の再調整(論文ではfeature recalibrationと書かれている)を果たすように設計されている。

論文中Fig.1にあるように、SEブロックは特徴マップを受けとってチャンネルごとに空間情報を凝縮する(Squeeze)。そして、Excitationと呼ぶ操作によりチャンネルごとの重みづけを行ったベクトルとしてSqueeze後の情報を変換する。これによって生成されたベクトルを元の特徴マップにかけ合わせることで、特徴マップがチャンネル間の相互作用をモデル化することができる。つまり価値の高いチャンネルを強調することで表現の質を挙げることを目指している。
目的に応じてSEブロックをどこに配置するかを決めることもできる。例えば、ネットワークの初めの方の層にSEブロックを入れると、クラスに依存しない局所的な特徴を共有することができ、後ろの方の層に入れるとクラスに依存した特徴の相互作用を共有することができる。

Related Work

モジュールを追加することでネットワークの性能を向上させる手法は色々と研究されている。多くの手法はチャンネル間の相互作用はクラスに無関係な関数の合成で表すことができると仮定しており、チャンネル間の相互作用を取り入れていない。一方、この論文では、チャンネル間の相互作用を非線形の変換を用いて調整することで、効果的に学習を進めることができるようになるというのが著者らの主張。

Squeeze and Excitation Blocks

Squeeze: 各特徴マップはフィルタがかけられた局所的な部分の情報の集まりであり、大局的な情報を持っていない。そのためSqueeze処理でチャネルごとの統計情報を取得する。具体的にはGlobal Average Poolingをかける。もっと複雑な処理を使っても良いかもしれないと著者らは述べている。

Excitation: 非線形なチャネル間の相互関係を学習し、複数チャネルが強調されることを許可するような設計になるように、ReLUを挟んでSigmoidを使っている。2層の全結合層で途中で削減率rをもちいてネットワークをいったんくびれさせている。

そして最後に元の特徴マップにSEブロックの結果をかけ合わせることで、特徴マップを強調することができる。
前述の通り、SEブロックはCNNの特徴マップを出力するところなら組み込むことができ、VGG, Inception, RexNet, ResNeXtなどに適用できる。

Model and Computational Complexity

SEブロックを追加してもパラメータ数の増加はSE-ResNet-50で約10%程度。推論速度も数ミリ秒程度の増加に抑えられており効率的。
SEブロックをCNNの最後の方に置くと、特徴マップの枚数が多いため計算量がその分増えるが、最後の層にSEブロックを追加するのを止めても性能はそれほど変わらずパラメータ数を削減できると論文中で議論している。

Experiments

様々なデータセットでSEブロックを追加してあげることでSoTAを達成した。

Ablation Study

Ablation Studyとは構成要素を1つだけ抜いた手法を比較すること。他のパラメータを固定して、あるパラメータを変化させた場合の挙動を調査している。
Reduction ratio r: Reduction ratioを増やしていくと精度は落ちていくが、線形の関係ではない。Reduction ratioが小さいと精度が上がるがパラメータ数が増える。16くらいが精度とパラメータ数のバランスが良いと述べられている

Squeeze Operator: Global Average PoolingとGlobal Max Poolingを比較したが大差はない。ここの選択にはSEブロックは頑健

Excitation Operator: 最後のSigmoidをReLUやTanhに置き換えた結果が示されているが、Sigmoidが一番良い。

Different Stages: ResNetのステージのどこにSEブロックを入れるかで実験しているが、どこでも精度は向上する。どこに入れるかは互いに補いあう関係なので、複数個所入れると精度がさらに上がると述べられている。

Integration Strategy: SEブロックをどこに入れ込むか。大差がないので、入れ込む一に関しては頑健だろうと述べている。

Role of SE Blocks

SEブロックの役割を現実的なレベルで理解するための考察が述べられている。Global Average Poolingを行わないNoSqueezeというモジュールを構成し、精度を見るとSEブロックよりも下がる。これはSEブロックが特徴マップ全体の情報を活用していることを示している。また、Excitationの理解のために、ImageNetの異なるクラスの画像に対して特徴マップが各層でどのように反応しているかを見ている。

Conclusion

SEブロックは強力。チャネル間の相互関係を利用した精度向上手法であり、今後はこのような方向性の研究が出てくることを期待している。著者らは最後にチャネルの重みづけを、ネットワークの枝刈りに使えるのではないかと提案している。

所感

非常に簡単な構成で、精度が向上するのが驚き。Kaggleなどでも使われるようになってきており、解説記事も多いので理解はしやすかった。

小規模データセットに対するニューラルネットの汎化性能の理由に迫る論文:Modern Neural Networks Generalize on Small Data Sets

NeurIPS 2018の論文で「Modern Neural Networks Generalize on Small Data Sets」という論文があったので読んでみた。

ニューラルネットは大規模データで成功を収めてきているが、小規模なデータに対しても過学習しすぎることはなく結構良い精度が出る。大規模パラメータを持つネットワークであっても上手くいく理由はパラドックスだと言われていた。
この論文ではニューラルネットを複数の小規模なネットワークに分解して性能を見ることで、大規模ニューラルネットがランダムフォレストのように複数のモデルのアンサンブルとして予測を行っていることを示している。
このようなサブネットワークを集めることによって、過学習しすぎることなく小規模なデータセットに対しても良い性能を出せている。

ニューラルネットの分解方法として、線形計画法を用いて各サブネットワーク同士の相関が低くなり、サブネットワーク自体の性能も高くなる分割を探している。

実験として、確率的に生成された2次元疑似データセットでベイズルール、ニューラルネット、ランダムフォレストの境界を可視化している。ランダムフォレストでは一つ一つの木は高いバリアンスを持っているが、集計することでバリアンスを減らせていることが分かる。同様にニューラルネットも分割した複数のサブネットワークたちはバリアンスが高いが、1つのニューラルネットにまとまると集計されてバリアンスが減っている様子が分かる。

実際に、UCI Machine Learning Repositoryから小規模データの116データセットを用いてニューラルネットとランダムフォレストの精度比較も行っている。ニューラルネットは10層、各層は100ノードと比較的大規模なものであるが、大体のデータセットでランダムフォレストに近い性能が出せている。また、ドロップアウトを使うとさらにランダムフォレストの結果に近づくことができており、ドロップアウトが正則化の一手法として機能していることが分かる。

小規模データに対するニューラルネットワークの活用可能性については、最近気になってい分野なので継続して論文を読んでいきたい。

Attentionによるニュース推薦の論文「NPA: Neural News Recommendation with Personalized Attention」

KDD2019のApplied Data Science Track Paperからピックアップして「NPA: Neural News Recommendation with Personalized Attention」という論文を読んだ。

ニュースをユーザ毎にパーソナライズして推薦する手法の論文で、Attentionのメカニズムをユーザとニュースタイトルの両方に用いることで高い精度を実現している。
この考え方の背景には、異なるユーザは普通異なった興味関心を持っており、同じユーザであっても複数の興味を持っているため、異なったユーザ同士が同じ記事を違う興味からクリックする可能性が考慮されている。つまり、あるニュースのタイトルがあったときにユーザによって着目した単語が異なってクリックしたということをモデル化している。

細かい精度向上のためのポイントとしては、推薦分野の特徴として興味を持たれない負例サンプルが非常に多く不均衡なデータのため、Negative samplingを施した方が精度が向上している。

いくつかの従来のアルゴリズムと精度比較を行っているが、複数の指標で有意性を持って精度向上を達成している。
実験結果を見てみると、異なるユーザごとにニュースタイトルのどこに着目しているかが分かり、あるユーザはスポーツに興味があり、他のあるユーザは映画に興味があるなどの指向が見えてくる。

この研究ではユーザとニュースタイトルのAttentionを使って推薦を行っていたが、次はニュース本文も使っていく方向に進んでいくと考えられる。そうなると入力が長くなるので、どのように計算量を減らしたり無駄な文章を減らすかなどの方向もポイントになっていくのかもしれないと思った。

Microsoftでの時系列データ異常検知手法の論文:「Time-Series Anomaly Detection Service at Microsoft」

KDD2019の論文を少しずつ読んでいってる。特にApplied Data Science Track Paperの方は、企業で実際に機械学習を運用している際の話が書かれているので面白く読める。

今回はMicrosoftの時系列異常検知の論文を読んだ。
https://arxiv.org/pdf/1906.03821.pdf

Microsoftでは定常的にモニターしている時系列データとして400万件ほどのデータがあるらしい。これだけの規模になると何らかの自動化の仕組みで異常検知をしないと追いつかない。
実際にMicrosoftではこの論文の手法を用いて、異常が検知されるとメールが飛んでくるシステムになっていて、メールのリンクから異常時の時系列プロットへと飛べるようになっている。

ただ時系列異常検知の難しい点として、以下の3点が挙げられている。

  1. 時系列データは時間とともに、データの分布が変わっていくことが多い。そしてほとんどのデータはラベルがつけられていないため、学習データとして用いる際に異常個所が分かっていない
  2. 時系列データはデータの種類によってパターンが色々とあるため、汎用的なモデルを作るのが難しい
  3. データが数秒、数分ごとに入ってくるため、効率的に高速な処理を行う必要がある

この論文ではSpectral Residualモデルという画像のSaliencyを表示する手法を、時系列データに対して適用し、その後1次元CNNを用いて異常検知する方法を提案している。
時系列データの異常が発生した箇所というのは、結局はデータの中で目立つ箇所であるので、Saliencyで着目すべき箇所を検出するとそこが異常個所だったりする。

手法の細かい点では、いくつかの工夫がなされている。例えば、Spectral Residual手法は、予測する点がウィンドウの中心位置にあった方が精度がよいので、予測する際には後ろ何点かを前のいくつかの点から予測してからSpectral Residualを算出する工夫が行われている。

実験として、実際の時系列データに適当に異常値を注入してそこを予測できるかを、既存の時系列異常検知アルゴリズムと比較している。今回のSR-CNN手法は、他のアルゴリズムに比べて精度や処理速度を考慮するとよい結果が出ている。
また、Spectral Residualを用いることで、教師なし学習として異常検知を行う手法が挙げられているが、もしデータセットに異常のラベルがついている場合は、Spectral Residualを一つの特徴量とみなして、後段の処理をCNNからDNNに置き換えるとさらに良い精度が出るとも報告されている。

実際にMicrosoftで時系列異常検知に用いられているモデルであるという点で信頼がおける手法だと考えられる。Spectral Residualを計算して時系列データから顕著な点を前処理的に用いるという考え方は面白かった。

時系列クラスタリングの研究サーベイ論文を読んだ

Time-series clustering – A decade review」という論文を読んだ。過去10年間の時系列クラスタリングの研究動向についてサーベイした論文。クラスタ手法のみではなく、効率や品質、複雑性などの観点での動向も調べられている。

」という論文を読んだ。過去10年間の時系列クラスタリングの研究動向についてサーベイした論文。クラスタ手法のみではなく、効率や品質、複雑性などの観点での動向も調べられている。

背景

近年、ストレージの増加や計算性能の向上により、バイオロジー、ファイナンス、気象などなど様々な分野でデータが大量に蓄積されてきている。それらのデータは必然的に時系列データとして扱うことができ、データマイニングの研究ターゲット(例えば可視化、分類、要約、トレンド解析など)とされてきた。

時系列データのクラスタリングの課題として、一般的に時系列データは大規模なものになりやすくメモリに乗りきらない場合がある、高次元になりやすい、類似度の計算が(時系列データはノイズや外れ値が入っていることが多く、系列ごとに長さが異なることが一般的なため)複雑なものになる、といった点がある。

ほとんどの時系列クラスタリングは3カテゴリーに分類できる。一つ目は Whole time-series clustering。これは個別の時系列データに対してのクラスタリング。二つ目は Subsequence clustering。単一の時系列からスライディングウィンドウなどにより部分系列を複数取り出して、クラスタリングするカテゴリー。三つ目は Time point clustering。これは時間的な近さと値の関係をもとにしてクラスタリングするパターン。

多くの研究では Whole time-series clusteringのパターンがとられており、著者らの分類によると Whole time-series clusteringはさらに3つの特徴で細かく分類できる。shape-basedアプローチは古典的なクラスタリングアルゴリズムを時系列データそのものに対して利用する。feature-basedアプローチはいったん生の時系列データを低次元の特徴量のベクトルに落とし込んでからクラスタリングを行う。model-basedの手法は一つの時系列データを1組のパラメトリックなモデルのパラメータに変換して、複数のパラメータに対してクラスタリング手法を用いてクラスタリングする。

時系列クラスタリングにおいて重要な要素の一つは次元削減である。時系列データはノイズも多く、系列長が長くなるとクラスタリングの計算コストが増えるために適切な次元削減を施してから、クラスタリングする場合がある。
近年よく使われるデータの表現方法は、Data adaptive(任意の長さのセグメントに対してデータを圧縮できる), Non-data adaptive(固定長のデータに適する), Model-based(マルコフモデルのようにモデルでデータを表現する), Data dictated(Model-basedとは対照的に圧縮率はデータに応じて決定される)の4種類に分類できる。それぞれの分類ごとにデータを表現するアルゴリズムがいくつか挙げられている。
そのほかにもclipped seriesと呼ばれる、データの値を平均より上か下かで0/1のbit列として扱うような形式でも、時系列の変化の形をクラスタリングするのには十分であるという研究結果もある。

類似度について

時系列データの類似度はクラスタリングにおいて重要な役割を果たす。何をもとに2つの時系列が似ているとするのかは様々な手法が提案されている。
ノイズが乗っているだけの系列どうしは似ていると判断してほしいし、増幅されているものや、間が途切れていたりする場合も似ている時系列と判断したいかもしれない。
一般的に類似度計算の手法が重視する観点が3つあり、それぞれ異なったアプローチが要求される。

  1. 時間の観点で似ている時系列を見つける。
    単純なユークリッド距離による類似度が用いられる。生の時系列データに対して計算すると高コストのことがあるため、フーリエ変換などを施してから計算されることが多い。
  2. 形状の観点で似ている時系列を見つける。
    いつパターンが起こったのかよりも、形が似ているかどうかを重要視する類似度計算手法。Dynamic time Warpingのような手法が使われる。
  3. 変化の観点で似ている時系列を見つける。
    隠れマルコフモデルやARMA系列のようなモデルが使われる。例えば自己回帰のパターンが似ているモデルどうしは同じタイミングで変化するので似ていることになる。長期間の時系列データに適している。

様々な類似度が提案されているが、計算量と精度のトレードオフの関係もあったり、ユークリッド距離でも十分な精度が得られるといった研究もあるそうなので、どれを使うべきかはケースバイケースなのかもしれない。

4章 Time-series cluster prototype

クラスタを代表する時系列(prototype)をどのように表すかにも大きく分けて3通りある。

  1. medoidをprototypeとする。要するにクラスタ内の分布の中で一番中央値的な時系列を代表とする。
  2. 平均値を使う。固定長の場合は単純に平均値を取れば良い。Dynamic Time WarpingやLongest Common Sub-Sequenceのように可変長の時系列をクラスタリングする距離を用いている場合にも、平均的なprototypeを作成する手法が提案されている。
  3. local searchを使う。medoidを求めて、warping pathで平均prototypeを求める。その後平均prototypeに対して、新しいwarping pathを計算する。この手法がほかの手法よりも精度の良いprototypeが得られるのかは分かってはいないようだ。

5章 時系列クラスタリングアルゴリズム

6種類に分けられる。

  1. 階層クラスタリング
    agglomerative(bottom-up)やdivisive(top-down)な手法によって階層クラスタリングできる。細かい調整ができないため、一般的には他の手法と組み合わせて使われることも多い。
    結果を可視化して分類の理解に役立つことや、事前にクラスタ数を決めなくても良いことなどが、時系列クラスタリングであっても長所である。弱点として計算量が系列数の2乗のオーダーなので小さなデータセットに適用先が限定されることがある。
  2. Partitioning clustering

  3. 事前に設定されたクラスタ数kにより、k個のクラスタに分類する手法。k-Meansがよく知られた手法であるが、時系列データに対してはk-Medoidsアルゴリズムが使われることが多い。
    クラスタに属するか否かを分ける手法に対して、ある度合いでどのクラスタに属するか、という指標でクラスタリングするFCM(Fuzzy c-Means)というような手法も提案されており、話者特定のようなタスクに応用された事例がある。
  4. Model-based clustering
    クラスタごとに1つのモデルを作って、クラスタ内のデータはそのモデルに誤差のノイズが加わって得られたと考えるクラスタリング手法。統計的なアプローチやニューラルネットワークの手法が用いられる。
    一般的にモデルベースのクラスタリングは2つの欠点がある。1つはパラメータを設定する必要があるが、そのパラメータはユーザのある仮定(間違っている可能性がある)に基づいており、低い精度につながる場合があることだ。2点目は大規模データセットに対してモデルの構築に時間がかかり遅い。
  5. Density-based clustering
    DBSCANが有名な手法であるが、データの密度が高い近くの空間に向けてクラスタを拡大していく手法。
    時系列データについては多変量の場合複雑度が高くなるため、あまり使われない。
  6. Grid-based clustering
    データをグリッドセルに分けてからグリッドのクラスタリングを行う手法。時系列データに使われた例は今のところないらしい。
  7. Multi-step clustering
    数は少ないがいくつかの研究では複数の手法を組み合わせて時系列クラスタリングを行っている。例えば、形状の類似度でクラスタリングしてから、時間的な類似度でクラスタリングをかける、といったような今まで挙げた手法を組み合わせて、精度向上や速度向上を目指した手法が提案されている。

6章 時系列クラスタリングの評価手法

時系列クラスタリングの評価手法としては例えば以下のような点に従うことが推奨されている。
・アルゴリズムの評価にはデータセットの複数区間を用いること
・実験を注意深く設計することでバイアスの混入を防ぐこと
・可能ならばデータとアルゴリズムを自由に入手可能とすること
・新しい類似度の指標は簡単で安定しているユークリッド距離のような指標と比較可能であること

大きく分けて可視化と数量的な指標による評価方法が存在する。
数値的なクラスタリング指標にはGround Truthなどとの比較によるExternal indexと、クラスタ内だけの情報によるInternal indexに二分される。

7章 Conclusion

時系列クラスタリングの研究はいろいろと行われているが、一般的なクラスタリング手法が上手く働くのを阻害するような要因が存在している。例えば高次元なデータやノイズ、高い相関などが阻害要因である。

様々な研究は高次元なデータを低次元に落とし込む手法と距離をどのように設定するかをターゲットとして行われている。時系列クラスタリングの研究には図に挙げられている通り4種類の課題が存在しており、それらに対する研究成果がサーベイとして本論文では示されていた。著者らは今後の研究の方向性としては、これらの課題に対して既存の手法もしくは新規手法を組み合わせたハイブリッドなクラスタリングアルゴリズムを考えてい方向に進んでいくだろうと、展望を述べている。