Designated Survivor in The Era of Artificial Intelligence

備忘録的なブログです。主に統計学・機械学習の技術について学習したことをまとめます。

AtCoder Beginner Contest 023D 射撃王

競技プログラミング

atcoder.jp

ABC023D 射撃王を解きました。
初見では全然歯が立たず、解説を読んでなんとか解くことができました。
以下本問題を解いて気がついたところです。

最大となるものを最小にする

この問題一見すると、なんとか工夫して貪欲法を使って最小化を行うことができるように見えてしまいます。
私は一秒後の高さが高い順に消していけばうまくいくのではないかという直感を元に解こうとしましたが、あえなく撃沈。。

そう、この問題そのままでは最適化をうまく行うことができないのです。。
どういう風に問題を読み替えれば、この最適化問題を解きやすい形に変換できるか？を考える必要があります。

この問題は、すべての風船をX以下の高度で撃ち落とすとした場合の最小のXを求める、という問題に置き換えることできます。

この発想の転換が問題攻略の第一の鍵です。

二分探索！二分探索！二分探索！

問題を置き換えることができても、そのXなるものをどうやって求めれば良いのでしょうか？
貪欲に全ケースを試していては時間が足りなくなるケースがでてきてしまいます。

そこで二分探索の出番です！
Xは条件に対して単調なので（ある数以上のXはすべて条件を満たし、ある数より小さいXはすべて条件をみたさない）、二分探索を適用することができます。
二分探索の適用を思いつけるかが問題攻略の第二の鍵です。

[Xとしてあり得る数の最小値 - 1, Xとしてあり得る数の最大値 + 1]の範囲で二分探索をつかって探索を行い、条件を満たすXの最小値が答えになります。

ちなみに、探索範囲を[Xとしてあり得る数の最小値, Xとしてあり得る数の最大値 ]とするとコーナーケースでひっかかってしまうので注意してください。

終わりに

次は独力で解けるようにします。

Spark自学自習(1) 遅延評価について

昨年末ごろから業務でPySparkを使っているので、そこで勉強したことを何回かに分けてまとめていきたいと思います。
まず、第一回目としてSparkの遅延評価についてまとめたいと思います。 本記事の内容は基本的には、以下の本を参考にしています。今回の内容は１章・２章で解説されています。

Spark: The Definitive Guide

そもそもSparkとはなにか？

Spark: The Definitive Guideでは、

Apache Spark is a unified computing engine and a set of libraries for parallel data processing on computer clusters. (p.3.)

という風に説明されています。

ここでは、Sparkとは並列分散処理を行うために必要な機能を提供するプラットフォームなんだな、くらいで理解していただければ大丈夫かと思います。
Sparkの概要についてわかりやすく解説された記事がインターネット上にたくさんあるので*1、詳しくはそちらを参考にしていただきたく思います。

Sparkの遅延評価 (Lazy Evaluation)について

筆者のようなデータサイエンティスト見習いが、Sparkを勉強していて最初に戸惑うのは遅延評価（Lazy Evaluation）という仕組みではないでしょうか？

プログラミング言語では、与えられた式に対してどの時点で実際の計算を行いその値を得るかについて複数の戦略が存在しています。 Pythonを含む多くの言語では先行評価という方法で式の評価を行っています。先行評価は、Sparkで使われている遅延評価と対になる戦略となっています。

本節では、まず先行評価についてまず確認を行ったあと、遅延評価の仕組みについて解説して行きたいと思います。

先行評価について

Pythonでは他の多くの言語と同じく先行評価という戦略で、与えられた式の評価が行われています。
例えば以下のPython3のコードでは、yの値は２行目で即時に計算され、そこで格納された値が３行目で出力されるという仕組みなっており、式の定義と評価が同時に行われています。

x = 10
y = x **  2 + x 
print(y)

この評価戦略は直感的に理解しやすいので、Sparkを勉強するまでは他の評価戦略が存在していることを想像したことすらありませんでした。

遅延評価について

Pythonとは異なりSparkでは遅延評価という戦略で与えられた式の評価を行っています。

遅延評価とは、評価しなければならない値がある時に、実際にその値が必要になるまで計算を行わないことを指しています。以下でPySparkのコードを使って遅延評価の動作を解説していきたいと思います。（Spark: The Definitive Guideのp.17~p.20の例 ）

myrange = spark.range(1000).toDF("number")
divisBy2 = myRange.where("number % 2 = 0")
print(divisBy2.count())

上記コードの処理概要

line1: 0 ~ 999までを要素に持つDataFrameを生成しmyRangeという変数に格納
line2: myRangeのなかで偶数のものに絞り、divisBy2をという変数に格納
line3: divisBy2の個数をカウント

さて、上記コードを先行評価で読むと、line2の段階ですでにmyRangeのなかで偶数のものを絞りこむという処理が行われているように見えます。

しかし、遅延評価では、line2では実際の計算は行われず、line3でカウントを行う際に実際のline2で定義された絞りこみの計算が行われています。これは実際にその値が必要になるまで計算を行わないという遅延評価の仕組みによるものです。確かにline2の段階では、データ変換の定義を行っているだけで、なんらかの値が必要になっている訳ではなさそうです。

Sparkでは、上記例のline3のように実際の値が計算が行われるメソッドのことをActionsと呼び、上記例のline2のように変換を定義しているメソッドのことをTransformationsと呼びます。これらについては次回記事でまとめたいと思います。

遅延評価のメリット

遅延評価の概要についてはわかりましたが、ではその遅延評価を行うことでどのようなメリットがあるのでしょうか？

遅延評価のメリットは、Spark側で処理の最適化が行えることです。例えば、あるテーブルに対していくつかの処理を行い、そこから特定の行の結果を取り出したい場合を考えます。得たい結果が特定の一行だけの場合、最初にその一行を抜き出してきて計算を行うほうが、テーブル全体に対して計算を行ってからその特定の一行を取り出してくるより効率的です。このように、Sparkでは処理の順序を入れ替えることで大幅に効率化できることがあります。遅延評価の仕組みを取り入れることで、Spark側で自動的に処理の順番を入れ替えることで効率化を行えるというメリットがあります。

*1:例えば、https://qiita.com/whata/items/8915182cbd3759eebe6dとか

mAPとは

はじめに

物体検出で精度評価指標として用いられるmAP (mean average precision)について調べたので将来のために記録を残します。

以下の記事に英語ですが非常によくまとまっています。

medium.com

mAPとは

mAP (mean average precision) とは、AP (average precision)のクラス間の平均のことです。
したがってmAPを理解するためにはAPについて理解する必要があります。

APの説明に入る前に、そもそも物体検出とはなにか？についてごく簡単に説明したいと思います。また、APを理解するためにRecallとPrecisionについて知っておく必要があるので、それについても後ほど解説させていただければと思います。

物体検出とは

物体検出（Object Detection)とは、画像に写っている物体の位置の特定とクラスの分類を一度に行うタスクのことです。
以下のYouTubeのビデオをご覧いただければ、わかりやすいかと思います。

www.youtube.com

PrecisionとRecallについて

PrecisionとRecallについては以下の記事にまとめました。

kt-taroha.hatenablog.com

APについて

上記の記事で使用したPR曲線の例をここでも使いたいと思います。PR曲線は以下のようになっています。 f:id:KT_taroha:20190319100518p:plain

APとは、各Recall値に対してその値かそれ以上のRecall値におけるPrecisionの最大値の平均のことです。
・・・文章だと伝えるのが難しいですね。
あるRecall値に対してその値かそれ以上のRecall値におけるPrecisionの最大値ということを、数式にすると以下のように表すことができます。

p_{interp} (r) = \max_{\hat{r} \ge r} p (\hat{r})

ここでpはPrecisionを、rはRecallを表しています。
これを表で表すと以下のようになります。(先ほどのページの例を持ってきました。)

確信度 みかん/ぽんかん Recall Precision p_{interp}
0.9 みかん 1/5 1/1 1
0.8 みかん 2/5 2/2 1
0.75 ぽんかん 2/5 2/3 1
0.6 みかん 3/5 3/4 3/ 4
0.5 ぽんかん 3/5 3/5 3/4
0.4 ぽんかん 3/5 3/6 3/4
0.36 みかん　　　　 4/5 4/7 4/7
.... .... .... .... ....

これを先ほどのPR曲線に重ねると以下のようになります。 f:id:KT_taroha:20190319105151p:plain

青色の線が通常PR曲線、オレンジ色の線が p_{interp}です。
APはそれの平均なので、オレンジ色の線の下の面積を求めることと同値になります。

おわりに

mAPとはAPのクラス間の平均です。

PrecisionとRecallについて（はじパタ第3章）

はじめに

クラス分類の精度を測るために用いられる尺度の一つとしてRecallとPrecisionが存在します。
RecallとPrecisionについては、はじパタの第三章で詳しく解説されています。
自分なりにかなり噛み砕いて記事にしてみました。

RecallとPrecisionとは

みかんについてWebで検索する場合を考えます。世の中にみかんに関するページが5件存在しているとします。
検索をしてみると6件のページがヒットしました。そのうち3件がみかんに関するページ、3件がぽんかんに関するページでした。

この検索システムの精度をRecallとPrecisionを用いて評価すると、

  • Recall = (検索結果のうちの正解) / (全体の正解)
    = 3/5
    = 0.6
    (全正解のうちどれくらいシステムが拾ってきているか?)

  • Precision = (検索結果のうちの正解)/(検索結果数)
    = 3/6
    = 0.5
    (拾ってきた結果のうちどれくらいが正解か？)

したがって、 Recallは検索の網羅性について評価している指標で、

Precisionは検索の正確性について評価している指標となっています。

PrecisionとRecallのトレードオフについて

RecallとPrecisionはトレードオフの関係にあります。
検索結果の確信度が高い順に以下のように並べたとします。
検索結果の確信度とは、検索システムがそのWebページがどれくらいの確信度でみかんのページであると思っているか、ということを表しています。

確信度 みかん/ぽんかん Recall Precision
0.9 みかん 1/5 1/1
0.8 みかん 2/5 2/2
0.75 ぽんかん 2/5 2/3
0.6 みかん 3/5 3/4
0.5 ぽんかん 3/5 3/5
0.4 ぽんかん 3/5 3/6
0.36 みかん　　　　 4/5 4/7
.... .... .... ....

確信度の閾値を下げていけば、Recallが上昇し、Precisionが低下して行く様子が上の表からわかるかと思います。先ほどの検索システムでは確信度の閾値は、0.36から0.4の間に設定されていました。

PR曲線とは

Recallを横軸にPrecisionを縦軸にして、このトレードオフの関係を図示したのがPR曲線です。 したがってPR曲線は右肩下がりになります。
上のPrecisionとRecallをグラフにすると以下のようになります。

f:id:KT_taroha:20190319100518p:plain

まとめ

今回はかなり噛み砕いてPrecisionとRecallについて説明してみました。

はじめてのパターン認識　第2章

はじめに

本章の主な話題は - データから識別規則を学習する方法の概略
- 汎化能力とはなにか？
- 手元のデータセットで汎化能力を評価する方法
- 過学習/バイアス・分散トレードオフ です。

汎化性能は、機械学習を実際の問題に適応する際に非常な重要な指標となってくるので、確実に理解する必要があります。

2.1 識別規則と学習法の分類

識別規則とは、入力データからクラスへの写像のことです。

入力データをどのようにクラスに写像するかによって、様々な手法が存在します。
- 事後確率を最大にするクラスに分類
- 距離によって分類（k最近傍法など）
- 関数値による方法
- 決定木による方法

本章では、線形識別関数をクラス分類に適用する場合を念頭に汎化性能や過学習といった概念を説明しています。

まず学習法には、教師あり学習と教師なし学習という二つが存在します。

教師あり学習とは、入力データに対して正解データがひも付けられているような場合に使用する学習法です。
教師なし学習とは、入力データに対して正解データがひも付けられておらず、似た性質をもつデータをまとめて自動的にクラス（似たデータの塊）を生成することを目的とする学習法です。

実は筆者は機械学習の勉強を始めた当初、恥ずかしいことにk最近傍法とK-平均法を混同していました。

k最近傍法は教師あり学習です。学習データ内の各入力データには正解クラスがひも付けられています。 新しいデータが入力されたら、入力データの近傍k個のデータがどのクラスに属しているかに基づいてクラス分類を行います。

K-平均法はクラスタリング（教師なし学習）の手法です。学習データには正解クラスはひも付けられていません。 各データはk個のクラスタに分類され、そのクラスタ内の平均ベクトルを用いてクラス分類が行われます。

2.2 汎化能力

学習データを用いて識別関数のパラメタを学習したあと、学習された識別関数が未知のデータに対しても正しく識別を行えるかどうかを確認する必要があります。この未知のデータに対する識別能力のことを汎化能力と呼びます。

誤り率

汎化能力の推計法について理解するためには、まず誤り率について知っておく必要があります。

誤り率とは、ある学習データ D_ Lで設計された識別規則を、学習データとは別のテストデータ D _ Tに適応した時の誤りの割合のことで、以下のように表されます：

\varepsilon (p _ L , p_T)

p _ Lは学習データの分布、 p _ Tはテストデータの分布のことです。

真の誤り率とは、母集団を学習データとテストデータに用いた時の誤り率のことで、以下のように表されます：

\varepsilon (p , p)

pは母集団の分布。

再代入誤り率とは、学習データとテストデータが同じ時の誤り率のことで、以下のように表されます：

\varepsilon (p _ L , p _ L)

学習データとテストデータの分け方

1 ホールドアウト法

データセットの一部を学習データ、残りをテストデータとして用いる方法です。この方法で得られる誤り率のことをホールドアウト誤り率といい、以下の関係が成り立つことが知られています：

E_{D _ L} \{\varepsilon (p _ L , p _ L)\} \leq \varepsilon(p, p) \leq E_{D _ T} \{\varepsilon(p _ L, p _ T) \}

ここで、 E _ {D _ T} は多数の学習データを用いて設計して計算した再代入誤り率の期待値を、 E_{D _ T}は一つの学習データセットで構築した識別規則に対して多数のテストデータセットを適用してもとめたホールドアウト誤り率の期待値を表しています。

2 交差確認法

データセットをM個に分割し、M - 1個分のデータを学習データセットとして使用し、残りをテストデータして用いる方法です。そして求められた誤り率の平均を性能評価の指標として用います。

3 ブートストラップ法

ブートストラップサンプリングを用いて、再代入誤り率のバイアスを推計する方法です。

再代入誤り率は学習データとテストデータが同一なので、真の誤り率とくらべて低く出てしまいます。これをバイアスと呼びます。
ブートストラップ法では、ブートストラップサンプリングを用いてこのバイアスを推計し、その補正を行います。

ブートストラップサンプリングとは、例えばN個のデータが手元に存在する場合、そのデータセットに対してN回の復元抽出を行い学習データを構築する方法です。
復元抽出とは、あるデータを抽出した後、そのデータを再びデータセットに戻してから次の抽出を行うということです。したがって、1つのデータが複数回抽出される可能性があります。

手元にあるデータセットの集合を N、ブートストラップサンプリングされたデータの集合を N ^ *とすると、バイアスは以下のように計算できます：

bias = \varepsilon (N ^ * , N ^ *) - \varepsilon (N ^ * , N)

ここで、 \varepsilon (N ^ * , N ^ * ) は再代入誤り率なので、 \varepsilon (N ^ * , N ^ * ) \leq \varepsilon (N ^ *, N ) という関係が成り立ち、 bias \leq 0となります。

ブートストラップサンプルを多数生成し、それによって得られる誤識別率の平均を用いて、真の誤識別率を推計することができます。

\varepsilon = \varepsilon (N , N) - \overline{bias}

モデル選択とバイアス・分散トレードオフ

誤識別率を推計する手法はこれまでで説明しましたが、誤識別率が目標より小さくならない場合はどうすれば良いのでしょうか？
この場合にはモデルを変更することが考えられます。モデルを複雑なものに変更すればモデルの表現能力が向上するので、誤識別率の低下が望めます。
本章では線形回帰を例にモデル選択とバイアス・分散トレードオフについて説明しています。

線形回帰の性能を測る指標としてMean Squared Errorがよく用いられます。

MSE_D = E_D \{ (y(x ; D) - h(x))^2 \}

y(x ; D)は学習された線形関数、 h(x)は推計したい信号成分、 E_D { } は多数の学習データを用いて学習を行った場合の期待値を表しています。

では、バイアス・分散トレードオフとは何のことでしょうか？
詳細は本に書いてあるので省きますが、イメージは以下のようなものです。

  • バイアス：関数がどれだけデータにフィットしているかを表している指標。バイアスが小さければ小さいほど、学習データへの当てはまりがよいことを表しています。
  • 分散：複数のデータセットで学習を行う場合を考えます。分散はそれぞれのデータが学習された関数がどれだけお互いに異なるかを表しています。分散が大きければ、服数の学習データセットで学習した際、データセットごとに推計されるパラメタの値が違ったものになると予想される。

分散とバイアスはトレードオフの関係にあります。バイアスを小さくしようと次数を大きくすると分散が大きくなり、分散を小さくしようと次数を小さくするとバイアスが大きくなります。

MSEを分解すると分散とバイアスのトレードオフがわかりやすくです。

E_D \{ (y(x ; D) - h(x))^2 \} = (E_D \{y(x ; D) \} - h(x) )^2 + E_D \{ (y(x ; D) - E_D \{y(x ; D) \} )^2 }

第1項はバイアスを、第2項は分散を表しています。

最適なモデルを選択するためには、バイアスと分散のトレードオフを考慮して、テストデータでのMSEが最小となるモデルを選択する必要があります。

おわりに

技術ブログ第二回目です。長く書きすぎました。
次回からはメリハリをつけて書きたいと思います。

はじめてのパターン認識　第1章

機械学習

はじパタについて

機械学習を勉強するものにとってもはやバイブルとなっている”はじめてのパターン認識/平井有三著"。
各所でおすすめされている良著ですが、ざっと読んだ感じでは初めて機械学習を勉強するにはすこし難易度が高い気もします。
ただ勉強会等で使用された各種資料が多く公開されているので、それらで不足分を適宜補いつつ学習をすすめていきたいと思います。
第1章では、パターン認識とはそもそも何であるかについて概説されています。短い章なので、さらっとまとめます。

1.1 パターン認識について

券売機のコイン識別を例に、パターン認識とはどのような問題を扱うものであるかを解説しています。
本節のポイントは、
1. パターン認識は特徴抽出と識別規則の適用の2段階からなる。
2. 特徴抽出で特徴ベクトルを作成し、それに識別規則を適用して分類を行う。
3. 本書では2段階目の識別規則の適用と学習を扱う。(特徴量エンジニアリングなどの話題は扱われない)

1.2 特徴の型

識別に用いられる特徴として、定性的特徴と定量的特徴があります。名義尺度・順序尺度・比例尺度・間隔尺度についてそれぞれ説明されます。
名義尺度と順序尺度は簡単に理解できますが、比例尺度と間隔尺度については一瞬、ん？となったので簡単に整理します。

比例尺度と間隔尺度の違いは原点の位置を変更しても意味が変わるか否かです。

間隔尺度の場合は原点の位置を変更しても意味は変わりません。例えば、0~100点で採点される数学のテストを考えます。
Aさんの点数は50点、Bさんの点数は90点、Cさんの点数は30点だったとします。それぞれの点数に対して100点を足してAさん150点、Bさん190点、Cさん130点にしてもその点数が表している情報は不変です。

一方で比例尺度の場合は原点の位置を変更すると数値の意味が変わってしまいます。
体重がそれぞれAさん50kg、Bさん70kg、Cさん90kgだった場合、それぞれに100を足したらまったく別の情報となってしまいます。

このように原点の位置をずらしても数値の意味が変わらないか否かが間隔尺度と比例尺度の違いです。

1.3 特徴ベクトル空間と次元の呪い

この章を読むまで次元の呪いとは、次元が増えるごとに計算量が指数的に増加してしまうことだと思っていました。

本章で説明される次元の呪いとは、次元が増えるごとに未知の関数を学習するためのデータ量が指数関数的に増加してしまうことです。

例として手書き文字認識が挙げられています。手書き文字認識で用いられる16*16ピクセルの画像は256次元のベクトルとして表現されます。
それぞれの次元が16段階の階調を持つ場合、256次元の各軸が16段階の区間を持つことになり、全体として16256区間存在することになります。
1つのデータ点はそのうちの1区間のみを占めることになるので、学習には大量のデータが必要になります。

まとめ

はじめて技術ブログを書きました。不備がありましたら修正いたします。ご指摘いただければ幸いです。

文系院卒がデータサイエンス業界で生き残るために

このブログの筆者は文系院卒です(経済系/修士(専門職))

  • 学部・大学院共に経済学を勉強しました。修論は家計の日本の家計の住宅選択行動をlife-cycle modelを用いて、シミュレーションを行いました。
  • 大学院入学時には政府系金融機関への就職を考えていましたが、研究・就職活動を経て考えが変わり、データ解析を専門としている企業に就職することにしました。
  • 統計学は計量経済学を履修した際に学習しましたが、機械学習に関しては初学者です。数学に関しては微分積分・線形代数の基礎がわかる程度です。
  • 学部時にイリノイ州立大学に一年ほど留学していました。現地では、学部4年生向けの統計学の授業を一通り履修しました。
  • 留学していたこともあり、英語は結構得意です(TOEIC 960/英検一級保持)。今後別のブログで英語学習のtipsについても発信できたらと考えています。

このブログは技術ブログです

このブログは備忘録的性格を持っています

  • 筆者の備忘録して使用します。