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を計算して時系列データから顕著な点を前処理的に用いるという考え方は面白かった。

書評:The Data Science Design Manual

少し前に「The Data Science Design Manual」という本を読んだので紹介します。

この本の著者はAlgorithm Design Manualを書いた、Steven S. Skiena先生であり内容自体はデータサイエンスの基礎的な内容を網羅的に説明した本です。非常にユーモアがある書き方で、データサイエンスの勉強はもちろん純粋な読み物としても楽しめる部分があります。
どのくらいユーモアがあるかというのは序文のCaveatという部分を読めばわかります。以下はその部分の引用です。
「It is traditional for the author to magnanimously accept the blame for whatever deficiencies remain. I don’t. Any errors, deficiencies or problems in this book are somebody else’s fault, but I would appreciate knowing about them so as to determine who is to blame.」

技術的な内容は数式を使ってしっかりと解説されており、ところどころにSkiena先生が実際に体験したデータ分析する上での罠や手法の説明を書いた「War Story」という節が挟まれており、読んでいて飽きないように工夫されています。
内容自体はデータの前処理から可視化、モデル作成と一通り書かれており、統計や線形代数の基本的な内容もカバーされているので1冊で基本的な部分が簡潔に学べるようになっていました。

このような本の類書は最近非常に増えており、内容的には大体理解している部分が多かったが、系統立てて読んでみると知識の抜けている部分が分かるので、英語に抵抗がなくて何か一冊データ分析の本を選ぶなら、読み物として面白いので割とおすすめできる本でした。


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

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種類の課題が存在しており、それらに対する研究成果がサーベイとして本論文では示されていた。著者らは今後の研究の方向性としては、これらの課題に対して既存の手法もしくは新規手法を組み合わせたハイブリッドなクラスタリングアルゴリズムを考えてい方向に進んでいくだろうと、展望を述べている。

「欠測データ処理」を読んだ

データ分析の前処理における重要なポイントの一つとして、欠測データをどのように扱うかがある。
入門向けの記事だと単純に平均値や0埋めなどを施して、そのまま機械学習モデルに投入する例が多いが統計学的にはこのような単一代入法と呼ばれる手法はバイアスを生じる。
そこで使われるのが多重代入法と呼ばれる手法である。

多重代入法について詳しく知りたかったので、評価の高い「欠測データ処理」を読んだ。

本書では欠測データの種類、単一代入法・多重代入法の理論的な側面とともにRによる実際のコード例も紹介されている。
例えば、一口に欠測データといってもその生成メカニズムとしてMCAR, MAR, NMARなどの種類が存在する。ある調査では経験的に完全にランダムに欠損が生じているデータ(MCAR)は公的統計の調査においては約10~20%程度という結果もある。
MARによる欠損は単一代入法ではバイアスが生じるため、多重代入法を利用するべきである。多重代入法とは欠測データの分布から独立かつ無作為に抽出されたM個のシミュレーション値によって欠測値を置き換えるものである。

最後の「おわりに」の章にある3つの疑問に対する回答が、なぜ多重代入法を使うのかという説明として非常にわかりやすかった。「なぜ複数回の代入が必要なのか」という疑問に対して、複数回の代入を行うことで推定に関する不確実性を代入されたデータに取り入れることで、標準誤差を適切にすることができると書かれている。これによって母集団パラメータの推定を妥当なものとすることができる。

外れ値処理の一手法:Winsorizingについて

機械学習や統計の分野における外れ値処理の手法の一つとしてWinsorizingと呼ばれる手法がある。日本語の解説が少なかったので書いてみる。

手法自体は非常に簡単で、外れ値を外れ値以外の最大値・最小値で置き換えるというものである。表形式データを考えると、単純に外れ値を除去するよりも、データサイズが少ない場合はほかのカラムの情報を有効活用することができる。

ちなみに英語版のWikipediaにはページが用意されている。
https://en.wikipedia.org/wiki/Winsorizing

このページにあった例を見てみると、numpy配列の上下5%のデータを最大値と最小値で置き換える方法が書かれている。

import scipy.stats
import numpy as np 
a = np.array([92, 19, 101, 58, 1053, 91, 26, 78, 10, 13, -40, 101, 86, 85, 15, 89, 89, 28, -5, 41]) 
scipy.stats.mstats.winsorize(a, limits=[0.05, 0.05])

1053が101に、-40が-5へと置き換えられる。
少し考えるとわかるが、単純に外れ値を除去して平均を取った場合とWinsoringをしてから平均を取った場合では値が異なる。

機械学習による化合物テストツールの論文:「PrePeP – A Tool for the Identification and Characterization of Pan Assay Interference Compounds」

PrePeP – A Tool for the Identification and Characterization of Pan Assay Interference Compounds
Maksim Koptelov (University of Caen Normandy); Albrecht Zimmermann (University of Caen Normandy); Pascal Bonnet (University of Orléans); Ronan Bureau (University of Caen Normandy); Bruno Crémilleux (University of Caen Normandy)
https://www.kdd.org/kdd2018/accepted-papers/view/prepep-a-tool-for-the-identification-and-characterization-of-pan-assay-inte

KDD2018の論文読み3本目。Applied Data Science Trackの続き。

製薬分野における機械学習を応用した論文。製薬などの分野で新たな化合物を作った際に、所望の性質を満たしているかを確認する作業がある。
対象物質が増えるとこの作業に非常に多くの時間とリソースがとられてしまう。そこで著者らは化学者向けのツールであるPrePePを作成し、専門家たちがビジュアル的に化合物の様子を探索し、テストの結果予測やその理由などをわかるようにした。

結果としてはiFH(infrequent hitters)と呼ばれるテストに成功しない多数派のクラスをうまく分類が出来ておらず、今後の改良が必要と述べられている。

具体的な機械学習モデルとしては解釈性を持たせるために決定木ベースでランダムフォレストのような形で、予測モデルを作成した。
また、化学の専門家が簡易に使えるように、その界隈で有名なツールを拡張する形でGUI付きのソフトウェアを開発している。

化学の専門知識が足りないためか、なかなかイメージが理解しづらいが、機械学習部分は基本的な内容だった。こういった分野でも機械学習の応用が進みつつあるのだと実感した。

機械学習によるユーザ離脱率の予測論文:「I Know You’ll Be Back: Interpretable New User Clustering and Churn Prediction on a Mobile Social Application」

I Know You’ll Be Back: Interpretable New User Clustering and Churn Prediction on a Mobile Social Application
Carl Yang (University Of Illinois, Urbana Champaign); Xiaolin Shi (Snap Inc.); Jie Luo (Snap Inc.); Jiawei Han (University of Illinois, Urbana Champaign)
https://www.kdd.org/kdd2018/accepted-papers/view/i-know-youll-be-back-interpretable-new-user-clustering-and-churn-prediction

KDD2018の論文読み2本目。産業界の応用事例を集めたApplied Data Science Trackのほうが自分の興味に近いのでそちらにシフトして上から読み始めた。

Snapchatの大規模なデータを集めて、ユーザタイプをクラスタリングにより6種類に分類して、その中の3種類のユーザタイプが平均よりも登録2週間後の離脱率が高いということが分かった。
このクラスタリング結果をもとにして、著者らはユーザ登録後の2週間のデータをもとにして離脱予測のモデルを作成した。

予測モデル作成において、いくつかの課題がある。
データが非常にノイズが多く、変動が大きいため、隠れマルコフモデルのような典型的な時系列モデルでは上手くいかない。また、データは非常にスパースであり、activityの数も非常に偏った(一部のユーザが非常に多くのactivityを行っている)データのため予測が難しいといえる。また、ユーザタイプによって離脱率が異なってくるが、最初の2週間のデータが少ない状態でユーザタイプの情報はそろっていないため、今までのモデルではユーザタイプの情報を使うことはできていなかった。

これらの課題を解決するために、複数のLSTMを組み合わせた予測モデルを用いて離脱率の予測を行っている。具体的には、活動をEmbeddingするレイヤーをLSTMの前に持たせてスパースなデータに対応し、2週間のデータからユーザタイプをクラスタリングシステムで予測し、そのユーザタイプを予測するようなK個のLSTMをトレーニングして、Attentionで着目するLSTMを決めて離脱率を予測するモデルを構築している。

この論文で書かれている離脱率予測のモデルはClusChurnというシステムとして、Snap Inc.のリアルタイム予測システムに組み込まれている。
機械学習による離脱率予測モデルの一例として参考となる論文であると思う。

[KDD2018 論文読み] Smoothed Dilated Convolutions for Improved Dense Prediction

Smoothed Dilated Convolutions for Improved Dense Prediction
Zhengyang Wang (Washington State University); Shuiwang Ji (Washington State University)
https://www.kdd.org/kdd2018/accepted-papers/view/smoothed-dilated-convolutions-for-improved-dense-prediction

KDD2018の論文読みを始めた。1本目。

Image Segmentationの分野でよく使われているdilated convolutionという手法はグリッド状のアーチファクトがでるという課題があった。
Dilated Convolutionは周期的なサンプリングをしてそこに畳み込みフィルターをかけて、並びなおすという操作を行う。並べなおされた後は、隣のピクセルは離れたピクセルの畳み込み後の値なのでアーチファクトが出てしまう。

これを解消するために、著者らはSmoothed Dilated Convolutionsという手法を提案し、公開データセットにて通常のDilated Convolutionに比べて精度が向上していることと、実際にグリッド状のアーチファクトが軽減されていることを確かめた。

具体的には、Group Interaction Layerという各Dilated Convolutionフィルタ間の全結合ネットワークを用いて、各フィルタ間の関係性を学習させている。

また、Dilated Convolutionをかける前に、Separable and Shared Convolutionという各チャネルごとにフィルタをかける形の処理を行うことで、Dilated Convolution処理の前に関係性を学習することができる。

PSCAL VOC2012データセットを用いて評価しており、全体的に過去の高性能モデルよりも良い結果が出ている。また、ERF可視化という方法でグリッド状のアーチファクトが軽減されていることを確認している。

XGBoost 0.81でtrain()が落ちる

タイトルの通り、XGBoostの現時点での最新バージョンを入れてtrain()を呼び出したところ、Jupyter Notebookで「”The kernel appears to have died. It will restart automatically.”」と出て強制終了となった。どうもデータかパラメータに依存して起きる現象っぽい。

色々と調べて試してみたが、ここを参考にしてバージョンを下げたところ問題なく動くようになったのでバグっぽい。

インストール方法:

pip install xgboost==0.80