ぱたへね

はてなダイアリーはrustの色分けができないのでこっちに来た

NN論文を肴に酒を飲む会 #9

tfug-tokyo.connpass.com

先週の水曜日にたまたま東京出張が入っていたので参加してきました。 会場をご提供いただいたgranica様ありがとうございました。

NoriakiOoshitaさん

薬関係の論文の紹介でした。グラフに関するMLは最近興味を持っているのですが、何よりもDruglikenessという指標が気になってしまいました。薬らしさの意味でしょうか。○○とくっつき易い薬をDruglikenessの指標として使う事で、ある特徴を持った薬を見つけやすくなったりしそうと聞いてなるほどーと思いました。

tamaki さん

AIに関する説明責任のお話。結構難しい話をわかりやすく説明していただきました。データの扱いについて、中国、アメリカ、日本を並べて比較してあるのは面白かったです。MSの論文の紹介があったのですがメモを忘れました。

龍一郎 さん

自然言語処理系の発表でした。僕は全然知らない分野なのに、皆さんふんふんと聞いていたので、ある程度常識だったりするのかなーと思いながら聞いていました。

f:id:natsutan:20190907193001p:plain

論文の本筋じゃないんですが、この図が面白かったです。ドイツ語のdieと、死ぬの意味のdie、サイコロのdieがちゃんと分類できていることの可視化です。

koreyou さん

これも自然言語処理の話。データのラベリングを、効率的にする話です。質問に答える形のアノテーションでは、yes, noの1ビットの情報しか無くもったいない。判断の理由を使う事で、アノテーション付きデータを量産します。その仕組みが、雑に作ったルールベースであっても、上手くフィルターすることで有効なルールのみを使えるようにになります。面白い。

TetsuoIshigaki さん

テーラー展開を使って、DLのモデルが入力画像のどこに反応しているかを可視化する手法の紹介でした。数式の展開は途中までついていったけど、途中で力尽きました。そもそもの所で、「テーラー展開の第一項は勾配と同じ」は分かるんだけど、じゃあGRAD-CAMみたいに勾配を直接使ったらあかんの?ってのが分からなかったです。

最後に

こういう何が出てくるかわからない勉強会は面白いですね。意外に自然言語処理が多くて楽しめました。

次、大阪でTFUG KANSAIやります。そこで、僕も機械学習の解釈について話します。僕の発表はこれから機械学習の理由付けをしないといけない人や単に興味を持っている人向けで、難しい式などはでてきません。興味ある人は是非来てください。

tfug-kansai.connpass.com

ちなみに今回も僕以外の発表者は超豪華です。

最後の最後にTFUG KANSAIのオーガナイザーも募集しています。興味ある方は一度TFUG KANSAIのイベントに参加していただいて声をかけてください。

Iterated greedyでグラフの彩色問題

Courseraで離散最適化を勉強していたら、フォーラムにIG(iterated greedy) というアルゴリズムが出てきたので紹介します。

元の論文はこちら。

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.7721

グラフ彩色の練習問題で使ってみたところ、非決定性もなく、むつかしい操作もなく、そこそこの計算量でそれなりの解が得られました。メモリの使用量や計算時間も、エッジのソート分を見ておけばOKなので組込みなどの厳しい環境でも使えます。

グラフ彩色問題

https://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%BD%A9%E8%89%B2
今回はエッジに対する色分け問題です。実装と評価が簡単なので、他の問題でもとりあえずやってみる価値はあると思います。

アルゴリズム

通常のgreedy algorithmは一回で近似解を求めに行きますが、IGではgreedy algorithmを繰り返すことでより良い近似解を求めます。

f:id:natsutan:20190821171450p:plain
graph
このグラフに対して、abc順にgreedy algorithmを使うと、a=1, b=1, c=2, d=2, e=3, f=4なり4色使う結果になります。次に、この色順でgreedyを適用します。順番がfecdabとなり、greedy algorithmでも2色の最適解を得ることができます。

本質的にはこれだけです。これでうまくいく理由は、一般的に制約プログラミングでは、制約の厳しい所から値を設定していくのが有効と言われています。一回目のgreedy algorithmで彩色した結果、彩色が厳しかったところから再度greedy algorithmを使うことで、うまく精度を上げています。これにヒューリスティックな方法を組み合わせることで、さらに良い解が見つかる可能性があります。

もっと厳密な話は上の論文を読んでみてください。

とあるグラフでやってみた結果

エッジの数 n = 1000でIGを試してみた結果です。

f:id:natsutan:20190821171512p:plain
Iterated greedy

縦軸を色数K、横軸をIGのイテレーション数としてプロットしてみます。iteration=0は、通常のgreedy algorithmの結果です。イテレーションを回すと、色数Kが少しずつ減っているのがわかります。これに、様々な既存手法を加えることで、さらに色数を減らすことが期待できます。

ナップサック問題の近似解を求める

Courseraの離散最適化コースを勉強していたところ、二週目の問題がこなせず一ヶ月以上停滞してしまいました。物の数(n)が30個くらいなら授業の方法で解けるのですが、40個で全然駄目になりました。練習問題は1000個とか10000個まであり厳密解でやるアプローチは見るからに無理、Webで調べても近似解の求め方はあまり見つからず苦労しました。

そんなとき、近似アルゴリズム―離散最適化問題への効果的アプローチ― という本がちょうど良いタイミングで発売され、そこに書いてあるアルゴリズムで上手く計算できたのでまとめます。

https://www.kyoritsu-pub.co.jp/bookdetail/9784320121775

Corseraの練習問題が元ネタです。そのまま回答になってしまうためコードは無しですいません。ちなみにRustで書きましたが、問題が大きくなると時間よりも先にメモリ不足で落ちてしまいました。そんなときも、近似解を求めることで使用メモリ量も制御できます。

問題

 入力:n組の2個の正整数 a_i, c_i(i=1,2,...,n) と正整数b

 タスク: \Sigma_{i\in X} a_i \leq b を満たすような部分集合 X \subseteq  {1,2,...n} のうち、和 \Sigma_{i \in X} ci が最大になる物を求める

ナップサックの用語にするとaiが大きさ、ciが価値、bがナップサックの大きさです。nの物品のなかから大きさの合計がb以下になる組み合わせで、価値の合計が最大になる組み合わせを探す問題です。

アルゴリズム(厳密解)

ナップサック問題における疑似多項式時間アルゴリズム(pseudo polynomial time algorithm)を使います。アルゴリズム自体は厳密解を求めます。最後に書くように、同じアルゴリズムで簡単に計算量を減らした近似解を求めることもできます。アルゴリズム時代はDP(動的計画法)の一種なのですが、いまいち正しい名前のような気がしません。

価値の最大値

 C = max \{ c_i : i = 1, 2, ..., n \}

とおくと   O(n^{2}C)  の計算時間で解くことができます。Cの値によって計算量が変わってきます。

今回はこの例でやってみます。

 a_i = \{4, 5, 8, 3, 2\}

 c_i = \{6, 10, 12, 4, 4\}

b = 11, n = 5です。

テーブルを作る

DP法と同じように二次元のテーブルを作ります。全ての物品の価値を足してPとします。

 P = \Sigma_{i=1}^{n} c_i = c(\{1, 2, ... n\})

配列をこのように作ります。

# 配列を初期化
a = [4, 5, 8, 3, 2];
c = [6, 10, 12, 4, 4];

テーブルの初期化

n×P+1の二次元配列を作る。 A[i][0]を0で初期化し、A[0][最初の物の価値]に最初の物の重さを入れる。それ以外は無限大とする。

配列の中を計算する

iとpで2重ループさせる。ループを疑似コードで書くとこう。

for(i=1;i<n;i++) {
  for(p=0;p<=P;p++) {
    処理
    }
}

処理の部分は、

  • p<c[i]ならば A[i][p] = A[i-1][p];
  • p >= ciならばA[i][p]は、①A[i-1][p]と②a[i]+A[i-1,p-c[i]]の小さい方とする。

良く分からないのでやってみましょう。 Pが、c = [6, 10, 12, 4, 4]の各要素の和なので36です。n=5なので、5x37の二次元配列Aを作ります。 iとpでループを回し、A[i][p]でアクセスします。

最初にi=0の行を初期化します。 A[0] = 0, A[c[0]] = a[0];で後の項はA[6]=4;になります。A[0]行のそれ以外の要素は無限大で初期化します。

p 0 1 2 3 4 5 6 7 8 ...
A[0][p] 0 4 ...

右側はp=36まで∞が続きます。

次にi=1の行を処理します。 c[i]=10なので、c[0]からc[9]までは上の列をコピーします。 c[10]は、①がA[0][10]で∞、②がa[1] + A[0][p-c[1]]=5+A[0][10-10] = 5+A[0][0] =5 になります。A[1][10]=min(①、②)なので、A[1][10]は5になります。同じように、A[1][16]が5+4で9になり、それ以外は∞です。

p 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...
A[0][p] 0 4 ...
A[1][p] 0 4 5 9 ...

これをi=4まで繰り返すとこうなります。

p 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
A[0][p] 0 4
A[1][p] 0 4 5 9
A[2][p] 0 4 5 8 9 12 13 17
A[3][p] 0 3 4 5 8 8 9 12 12 13 16 17 20
A[4][p] 0 2 4 5 5 8 7 9 10 11 13 14 15 17 18 19 22

最大値探す

Aの値が決まると、次に一番下の行から、A[4][p] <= bとなる最大のpを探します。

p 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
A[4][p] 0 2 4 5 5 8 7 9 10 11 13 14 15 17 18 19 22

bが11なので、A[4][20]、つまりp=20が最大値となります。この値が条件を満たす最大の価値qになります。

ナップサックの中身を決める

今度はq=pとして、iでn-1から1まで逆向きにループします。 疑似コードです。

for(i=n-1;i>=1;i--) {
  処理
}

処理の部分は、A[i][q]<A[i-1][q]ならば、そのiをナップサックの中に入れて、q=q-c[i]とします。ちょうど、表の一つ上と比較して、値が大きくなっていたらその物を追加し、qを価値分減らしていきます。最後、ループを出た後にq>0であれば、i=0の物もナップサックに加えます。厳密解を求めるときは、ループを出た後のqは、0かc[0]のどちらかです。

P=20より右側は無視してかまいません。

p 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
A[0][p] 0 4
A[1][p] 0 4 5 9
A[2][p] 0 4 5 8 9 12 12
A[3][p] 0 3 4 5 8 8 9 12 12
A[4][p] 0 2 4 5 5 8 7 9 10 11
  • i=4:A[4][20]の一つ上を見て11 < 12 なので、ナップサックに入れ、qを16にします。
  • i=3:A[3][16]の一つ上をみて、同じ値なのでナップサックに入れない。qはそのまま。
  • i=2:A[2][16]の一つ上をみて、同じ値なのでナップサックに入れない。qはそのまま。
  • i=1:A[1][16]の一つ上をみて、9 < ∞なのでナップサックにいれ、qを4にします。
  • 最後、q!=0なので、i=0もナップサックに入れます。

最終的に i={0,1,4}が厳密解になります。

アルゴリズム(近似解)

このアルゴリズムの計算量は [tex] O(n^{2}C) ] なので、Cが大きくなると遅くなります。例えば、C>nという状況では、n3以上の計算オーダーになります。

近似解の求め方は簡単で、物の重さ(c)とナップサックの容量bを、ある値で割って小さくする(Scaling)事で近似解を得ることができます。

a = [422, 543, 802, 322, 223];
b = 11234;

のような入力に対してaもbも100で割り最適解を求めると、それがそのまま近似解の組み合わせとなります。近似解の精度も保証されており、証明が気になる方は上の本を買って読んでみてください。

7/25日に東京でエッジAIのイベントやりまーす

イベント概要

7月25日、パソナテック本社で「これからのエッジAI」というタイトルでイベントを行います。

申し込みはこちらから。 https://connpass.com/event/137100/

申し込みページの案内が微妙&微妙なので、勝手に見所をお知らせします。ちなみに関係者と言うよりは、もろ主催者側の人間です。

今回登壇していただく方は3名、Google佐藤様、DMP大渕様、パソナテック林の豪華ラインナップです。案内が企業様向けとなっていますが、テクノロジー好きな人達の発表なのでどうしてもテクノロジーに寄ると思いますよ!登壇の順序とかタイムテーブルとかよくわかんないですけど、それぞれ45分程度の発表と聞いています。正式な案内を待ちましょう。

では講演内容の紹介です。

グーグル合同会社 Google Cloud デベロッパーアドボケイト 佐藤一憲様

タイトル:TensorFlow Lite、AutoML、Edge TPUで加速するエッジデバイスの機械学習

概要: 機械学習のエッジデバイス導入におけるの大きな課題は、ニューラルネットワークのモデルサイズとCPU消費です。Googleでは、これらの問題を解消する技術として、エッジデバイス向けの機械学習フレームワーク「TensorFlow Lite」と、そして低消費電力の推論プロセッサ「Edge TPU」を開発しました。このセッションでは、 TensorFlow LiteやEdge TPUを用いてモバイルアプリやエッジデバイスに最新のAIを導入するための課題や各種手法を解説します。また機械学習モデルの作成を自動化するAutoML Vision Edgeを利用し、モバイルアプリやエッジデバイス向けの機械学習モデルをプログラミングレスで作成する例を紹介します

俺ポイント: 僕がはまっているAutoMLからのEdge TPU。AutoML技術があれば、あなたも私もすぐにDeep Learningできるようになります。先月くらいから日本でもAutoMLが話題になっていますが、まだ話を聞いたことが無い人はぜひ聞きに来てください。AutoML知らないのは遅れてますよ。そしてEdge TPU、謎のデバイスの秘密が今明かされるかも。プロセッサマニアは正座して聞くべし!

株式会社ディジタルメディアプロフェッショナル 常務取締役開発統括部長 大渕栄作様

タイトル:エッジにおけるAI処理とそれを実現するDMP ZIA C3モジュールについて

概要: エッジデバイスにおけるAI処理の動向を紹介するとともに、NEDO IoT横断プロ ジェクトにおける省電力AIエンジンのアーキテクチャ及び、それをモジュール化 したDMP ZIA C3について紹介します。 DMPはこれまで省電力GPUアーキテクチャの研究開発をおこなってきたスタートアップベンチャーで、設計物のIPコアとし て、ニンテンドー3DSやデジカメ、プリンタといった機器で採用されています。 日本では貴重となったGPUベンダーとして近年ではAIアプリケーションで省電力GPUコアを活用したソリューションとして省電力AIエンジンの研究開発を進めて います。 本講演では、AI動向やディープラーニングを用いた画像認識とは?という基本から、省電力化に向けたアプローチを紹介します。

俺ポイント: DMPさんは10年ほど前、三鷹にお邪魔したことがあります。当時はバリバリベンチャーでしたが、今やGPU界で老舗のイメージすらあります。ZIA C3モジュールなので、Xilinx Zynq UltraScaleですね。FPGAですよ!AIのFPGA実装と、国産GPUの話を聞きたい人は集まれ。

株式会社パソナテック IoEソリューション事業部 AIプロダクトG Qumico Tech Lead  林徹

タイトル:『AI・IoT分野の開発サポートツール「Qumico」について』

概要: 今、発表資料を作ってるんじゃ・・・。

俺ポイント: 二年前に一瞬だけメディアに取り上げられて消えてしまったコキュートス。その血を引くQumicoがパソナテックの正式なプロダクトとして登場します。コンパスの案内だとデモだけっぽいですが、45分の公演もあります。プアーな環境でも組込 Deep Learning が動かせるツール。開発者自らが語るQumico開発の狙いと実機デモをお楽しみください。

最後に

企業様向けと書いてありますが、絶対エンジニアも楽しめるイベントです。 ここだけの話ですが、社内では企業様向けで企画が動いているため、あるタイミングで営業が動き出すと枠が一気に埋まってしまいます。個人での参加はお早めに。

https://connpass.com/event/137100/

俺ポイントは完全に想像なので外していたらごめんなさい。

世界で闘うプロダクトマネジャーになるための本

https://www.amazon.co.jp/dp/4839951772/

「今日から君はプロダクトマネージャーだ」と言われた人が、世界レベルになるための本と思ってタイトル買いしたが、ちょっと内容が違いました。半分以上が、履歴書の書き方だったり、面接の受け答え、知っておくべき知識など、転職活動のアドバイスでした。

原初のタイトルは、Cracking the PM Interview: How to Land a Product Manager Job in Technology なので、完全に就職対策本ですね。日本語タイトルはちょっと不満があります。とはいえ、最初の方のプロダクトマネージャーの仕事とは、プロジェクトマネージャとの違いとは、って所はわかりやすく書いてありました。その次の章で、有名企業でのプロジェクトマネージャの役割も楽しく読めたので、値段分以上の内容はあると思います。

転職してプロダクトマネージャーになりたい人にはお勧め。

AutoMLその後

一番下に追記しました。 結論から言うと、26万円の請求は正しい請求で、今回は諸事情 *1を考慮し減額してもらいました。Googleさんありがとう!もやもやが晴れました。

元の記事

AutoMLで破産しないように気をつけたいポイントのつづきです。 natsutan.hatenablog.com

あの後、Googleのサポートの方に相談して、26万円の支払いを11万円に減額していただきました。26万円のうち、トレーニングで請求された費用15万円が減額対象になり、Prediction用として確保したGPUインスタンス分は減額の対象となりませんでした。

サポートメールからはこのような返事が来ました。

「弊社担当チームと再度確認を行いました。想定外の金額が発生したAuto ML Trainingのご利用分のみ返金となった事が分かりました。Auto ML Predictionに関しては問題が見受けられず、請求に関しても返金は行われないとの事です。」

この想定外が、僕にとっての想定外なのか、Googleにとっての想定外なのかはメールからは良く分からないです。減額処理も今回だけですと書いてあったので、Googleのミスでしくったからごめんという雰囲気では無いです。

オフィシャルな通知が見つからないので伝聞ですが、 - 今のAutoMLは24hで止まるのでトレーニングで想定外の請求が発生することは無い - 推論についてはより分かりやすいI/Fになる予定 と聞いています。(こう書いておけば、オフィシャルな通知が出ると期待)

これで安心して使えるのかどうかは僕は確信が持てないですが、会社のお金でやった方が良いのは何度も言っておきますね。

AutoMLに関しては、地方でDeep Learningやりたい企業や、専門家を抱えられない企業にとっては、非常に役に立つ技術だと思いいます。使えるアプリは限られていますが、10万、20万で専門家と同じレベルまで持って行けます。東京のベンチャー企業の人を地方に呼んで、自分が用意したデータでそこそこ良い物を作ってもらおうとすると、10万、20万では済まないですよね。よくお客さんと話していてExcelの関数にDeep Learningが欲しいとネタに出てきますが、専門家で無くても使える為の大きな一歩だと思います。

今のAutoMLは識別を除くとGoogleのクラウド上でしか動かないです。有料でトレーニングをした後、さらに追加料金を支払うとONNXフォーマットでダウンロードできるようにしてもらえるとうれしいです。それでも、Deep Learningが分かるエンジニアを貼り付けるよりはよっぽど安く済むはずです。

減額されてうれしい気持ちと、Googleの返事にもやっとする気持ちと、今後のAutoMLへの期待を書いてみました。

2019/06/26 追記

Googleからの回答です。内容をブログに記載OKとの事なので、そのまま貼り付けます。

学習について:夏谷さんの実行した学習ジョブについて、サービスと課金は正しく動作していたことが確認できました。以下の2つのジョブです。ただ、サービスのわかりにくさのために夏谷さんの予想外の課金がされてしまったことを考慮し、学習については今回に限って返金いたします。

23.85 hours x 9 nodes x $3.15 = $676.3
22.85 hours x 9 nodes x $3.15 = $647.9

  • 推論について:こちらはドキュメント記載通りの課金となるため、大変残念ながら返金はいたしかねます。ただし、いただいたフィードバックは今後の製品開発に活かさせていただきます。

とうわけで、AutoMLで物体検出を回すと実際にこれだけお金がかかります。みんな注意してね。

実際には11万請求だからな!

*1:学習したモデルを実際には使っていないことも確認がありました

AutoMLで破産しないように気をつけたいポイント

はじめに

AutoMLを使っていたら一気に26万円の請求が来ました。 他の人が同じ事故にあわないようにやってしまったことを書きます。

2019/06/24、2019/06/26 追記書きました。15万円減額してもらえました。請求自体は正しく、トレーニングに関しては一回回すとこれだけの費用が発生します。

natsutan.hatenablog.com

やったこと

前回、こんな記事を書きました。

AutoML Vision Edgeが作るニューラルネットワーク

この続きで、物体検出のAutoMLを評価してみようと思いました。VOC2012のデータを用意してAutoMLへかけてみました。トレーニングの前に物体検出の方はtfliteへの変換が選べないことが分かったのですが、トレーニングさえ終わらせておけば何か方法がみつかるかもしれずと思い、精度優先と速度優先の2つのオプションでAutoMLを実行してしまいました。

前回の識別では3時間程度で学習が終わっており、今回も無料期間から足が出ても少しかなとたかをくくってました。

費用の内訳はこうなっています。

  • AutoML Image Object Detection Model Training 14万
  • AutoML Image Object Detection Online Prediction 11万

ここから無料枠分が差し引かれ、消費税が8%乗っています。

AutoML Image Object Detection Model Training

まずはトレーニングにかかった費用です。上に書いたとおり、比較をしたかったので2つの設定でトレーニングを回しています。トレーニングが2回で420時間かかっています。

トレーニングの価格体系はこちらに記載してあります。

https://cloud.google.com/vision/automl/pricing?_ga=2.243008706.-112799687.1556789167

5000枚程度なら5時間とあり、VOC2012が約27000枚なので、24時間見ておけばよいかなと甘く見ていました。

結果は、2回のトレーニングで420時間動いてしまい、合計で14万円の請求になりました。

AutoML Image Object Detection Online Prediction

こちらは識別のAutoML時にはかからない費用だったので、完全に見落としていました。訓練時にデプロイをするかどうかにチェックを入れることができます。訓練した後、絵を入れてみたいのであまり気にせずチェックしてしまいました。これも間違いでした。

上のリンク先に太字で「予測が行われない場合であっても、デプロイしたノード単位での料金が発生します。」と書いてあるように、デプロイするだけでGPUノードを1つキープし続けます。今回2つ訓練をしたので2ノードをキープし続けました。

こちらが11万円です。

よくある言い訳

  • 警告のメールは来ていたが、完全に見落としていた。
  • 請求のルールが識別のAutoMLと同じだと思っていた。
  • 仕事が忙しくて、とりあえず投機的にAutoML回しておこうと考えてしまった。結果の確認が遅れた。

反省点

  • 警告メールはいくつかの閾値で定義し、わざと警告を出させてちゃんとチェック機能が働くか確認した方がよい。
  • 仕事が忙しい時に青天井に費用が出ていくことに挑戦しない方がよい。余裕を持って成果と費用をチェックできるときにやろう。
  • AutoMLは会社のお金で回そう

最後に

今回は悲しい結果になってしまいましたが、AutoMLはリサーチャをかかえられない企業に取っては救世主になると信じています。
費用に関しては改良して欲しいです。「ユーザーがオペレーションをキャンセルした場合は、課金されます。」と書いてあるとおり、いつ終わるか予想ができないのに、途中で止めると費用は発生しているのにモデルが無いという状況になります。費用なり、時間なりでリミットを決められないと怖くて使えないです(今回は200時間だったが、Googleがその気になれば1000時間でも2000時間でも回せる)。 VOC2012のような有名なデータセットを例に、料金や時間の目安は事前に案内があっても良かったと思います。

最後に、物体検出もエッジで動くようにして欲しいです。