mechatronics / robotics
Blog
  • HOME »
  • Blog »
  • 機械学習

機械学習

A*アルゴリズムによる最短経路探索

前回のダイクストラ(Dijkstra)法に続いてA*をやってみました。違いは、探索候補を決めるときにダイクストラ法ではスタート地点からの距離が最小になるものを選んでいたのに対し、A*ではそれに加えてゴール地点からの距離(マンハッタン距離)も考慮するというものです。考慮といっても単純に加算するのみです。マンハッタン距離とは縦横の移動のみを認めて斜め移動は禁止する道のりのことです。斜め移動しない設定にしているからです。 結果はダイクストラ法と同じになりますが、あさっての方向を探索しなくなるのでかなり効率的になります。マトリクスを見ても未探索のフリーのセルが結構残っています。

ダイクストラ(Dijkstra)法による最短経路探索

10×10のマス目の土地でスタート地点、ゴール地点、障害物の位置が既知とします。アルゴリズムがスタート地点からゴール地点までの最短経路を探索します。ダイクストラ法はスタート地点からの距離の短さを手掛かりに、割としらみつぶしに当たって行く方法です。matlabで実装したものをpythonに書き換えてみました。 アルゴリズムを簡単に言葉で書くと以下のようになります。 ・スタート地点から始める ・全セルのスタート地点からの距離を大きな値に設定、スタート地点は0に設定 ・今いるセルの上下左右のセルについてスタートからの距離を自セルの距離プラス1とする ・自セルの距離を最大値に戻す ・全体を見て距離最小のセルを選びそれをカレントのセルに更新 ・カレントセルは前回のカレントセルを自分の親として覚えておく ・上3行を繰り返しゴールに到達したら終了 ・ゴール地点から親をたどっていくと最短経路となる 下のコードはそのまま実行できると思います。距離のマトリクスとステータスのマトリクスを次々に表示します。最短経路はステータスのマトリクス中に数字0で表示されます。

スタンフォードの機械学習講座 第11週 Photo OCR

第11週は写真の中から文字を見つけて解読する手法(Photo OCR)についてです。最後なのでもうあまり深く突っ込まず概要をさらっと流す感じでした。パイプラインという考え方で、 ・画像の中から文字が書かれているエリアを探す ・1文字ごとに区切る ・何の文字かを認識する という流れに沿って行われます。 ということで機械学習のコースを無事終了しました。何か久々の達成感を感じています。Final Gradeは98点でした。これは途中で先を急ぐあまり進級の課題で間違えたところをそのままにしていたからだと思います。MatLabのプログラミング課題は少し難易度が高いと感じましたが理系の大学生なら問題ないでしょう。本を買って読むより確実にモチベーションは上がります。 何らかの形で実務に生かせるとよいのですが。 これは2011年に撮られたもので講師のAndrew Ng先生は今中国の百度のほうと仕事をされているようです。 P.S.日本語字幕を付けてくれた方に感謝!

スタンフォードの機械学習講座 第10週 大量データの扱い・オンライン学習など

・大量データの扱い データの分量が100万、億の単位(いわゆるビッグデータ)になった時の勾配降下法のやり方についてです。確率的勾配降下法と呼ばれ、パラメータの更新をするときにすべてのデータを使わずにひとつのデータのみを使うというものです。1回ごとの精度は低いけれども最後には最小値の付近に到達し、それを数回繰り返すことで通常のやり方と同等の結果を得られます。 ・オンライン機械学習 WEBショップなど継続的に顧客のデータが得られる場合などに使われる手法で、上記の考え方に似ていて常に新しい単独のデータをもとにパラメータを更新していきそのデータは次回からは使われません。長期にわたって状況の変動などにも対応できます。 ・並列処理(Map Reduce) ビッグデータを複数のコンピュータに分散して処理する手法。 今回プログラミング課題はありませんでしたが、初回の進級テストが5問中3問正解で不合格になりました。もちろん再挑戦できます。翌日Corseraから「Don’t give up!」のメールが届いていました。 ****************************** We noticed that you didn’t pass Large Scale Machine Learning in Machine Learning yet! We wanted to remind you that there’s no penalty, so feel free to try again. Research shows testing will help you remember and apply the information more easily, so this exam is not only a way to gauge how well you’ve mastered the material – it will actually help you learn! ******************************* 次週は最後です。

スタンフォードの機械学習講座 第9週 異常検知・レコメンドシステム

第9週は異常検知とレコメンドシステムです。 異常検知はわかりやすいです。データのばらつきを見て全体からはずれているものを異常とみなすというものです。定性的には2次元データの分布図をみて目視で検出すればよいわけですが、機械学習的にはガウス分布をあてはめて平均値から一定以上はずれたものを異常としてはじきます。 レコメンドシステムは今機械学習技術者が最も重要視しているアプリケーションだそうです。一般人にとっても最も身近な例でもあります。手法としては、協調フィルタリングというものを使います。図のように商品(サービス)とユーザーの評価(好み)を表すマトリックスがあってユーザーにどの商品をすすめたらよいかを、商品の特徴(フィーチャー)を表すベクトルとユーザーの好みを表すベクトルを全く未知のところから探り当ててしまうアルゴリズムです。最初のころにやった線形回帰は回帰直線の係数Θを求めるものでしたが、今回はデータ側のXも作り出してしまうような感じです。生データだけがあってコンピュータが人間の手を借りずに意味づけを勝手にしてくれちゃう感じといったらよいのでしょうか。 こういう手法を使えば何かほかの領域でも応用ができそうな気がします。 プログラミング課題はちょっと苦労しました。このコース自体が数学的な理解はそれほど重要視しなくてもよいというスタンスなので課題もただのプログラミング練習になってしまいがちです。

スタンフォードの機械学習講座 第8週 教師なし学習・主成分分析

第8週は教師なし学習と主成分分析です。今まではすべて教師あり学習だったということですね。 教師なし学習ではK-MEANS法という手法を取り上げています。 答えが決まっていないデータ群をうまいこと分類してくれるのですが、そのアルゴリズムがビジュアル的におもしろいというか直感的に理解しやすいです。 図はその過程を示しています。未分類のデータに適当に代表点(この場合2つ)を落として、それぞれのデータが自分がどの代表点に近いかで分類先を決めます。次に代表点は自分に属してくれたデータ群の重心位置に移動します。この過程を繰り返していくといい感じのところに落ち着くというものです。 プログラミング課題では画像データの圧縮を扱いました。 主成分分析はデータの次元を圧縮する手法です。 これは人工知能というよりも昔からある統計的手法という印象があります。

スタンフォードの機械学習講座 第7週 サポートベクターマシン

第7週はサポートベクターマシンです。名前は聞いたことがありました。 今までと同様に散らばったデータ群に境界線を引いてうまく分類するための手法です。特徴は境界線と近傍データとの距離を最大化するように線をひく、というものです。数学的な説明もありましたが、実際にSVMをプログラミングする必要はなくむしろ既存のソフトウェアを使うべし、とのことです。本講座はとにかく実地で機械学習を使えるようになることを主眼にしているので、無駄に時間を浪費するようなことは推奨されません。そんなわけで今回のプログラミング課題は比較的楽な内容でした。スパムメールの分類問題でしたが、英語の場合と日本語の場合とでは同じ手法でいけないのでは?との疑問が残りました。 それと前から気になっていたのですが、アメリカではグラフを描くときに○と×の使い方が日本とは逆ですね。ポジティブが×でネガティブが○なのでどうしても違和感があります。

スタンフォードの機械学習講座 第6週 機械学習の運用

第6週は実際に機械学習を活用するに当たっての注意点や効率化の方法などについての話でした。とにかくやり方を間違えると半年や1年はすぐに経ってしまう、データの数量を集めることに時間を浪費しないように、ということが強調されていました。 ・Train/Validation/Test sets 学習/検証/テストのサンプルデータ 全体のデータセットを60:20:20の比で分けて、それぞれを学習用、検証用、評価用のデータとする。 検証用のデータは、正規化の度合い(λ)を決定するのに用いる。 ・Bias vs Variance バイアスと分散 バイアスと分散といっても何のことかわからないが、データにあてはめた直線(曲線)がどれくらいデータにフィットしているか(underfit/overfit)をあらわす。ほどよいフィットを得るには、学習用/検証用のデータを使ってたとえば近似曲線の次数をいろいろ変えてやってみてグラフをかいてみる。どのグラフの様子から見当をつけることができる。 ・Precision(精度) / Recall(再現率) がん検診の例でいうと、Precisionはがんと予測したなかで実際にがんである率、Recallは実際にがんであるなかで正しく予測した率。仮説の関数HΘの閾値によってPrecisionとRecallの値を操作することができる。その評価にはF1 scoreというものを使う。 実際の問題へ応用については、アルゴリズムを適用してグラフを描いてみる、実データの傾向をよりよく表すようにアルゴリズムを改善していく、ということの繰り返しのようです。やはり実務となると泥臭い感じになってきます。 PrecisionとRecallを一瞬でイメージするのは難しいです。毎回しばらく考えないとわかりません。

スタンフォードの機械学習講座 第5週 ニューラルネットワーク

前回の課題ではニューラルネットのパラメータΘが予め与えられていました。今回はバックプロパゲーションという手法を使ってこれを求める課題です。コスト関数はニューラルネットのすべてのノードについて足していきます。 logが出てくるところは2乗誤差と思ってもらってもかまわないということです。イメージの限界は凡人もスタンド―ドの先生もさほど変わらないようです。 ランダムに作ったイニシャルのパラメータ(重み)Θを使って右向きに各ノードの値を計算していきます。出力の層(レイヤー)まできたら答え(教師データ=Y)合わせをしてその差を算出(delta)。今度はdeltaを左向きに同じパラメータΘを使って戻していきます。こうすることでうまいことパラメータΘが良い方向に修正できる、という仕組みです。数学的な説明は難しいので割愛!ということでしたが、まあ使えればよしとしましょう。 下は具体的なプログラミングのやり方です。c言語などと違ってmatlab/octaveではなるべくforループは使わず行列表現で書いていくのが作法です。ようやく慣れてきました。 matlabフリー版の使用期限があと1カ月くらいになってしいまいました。なんとか最後まで終わらせるようにがんばりたいです。

スタンフォードの機械学習講座 第3週 ロジスティック回帰

第3週は、教師有り学習のなかのロジスティック回帰、腫瘍が良性か悪性かとか試験に受かりそうか落ちそうかとか2値の答えを予測するような問題です。 線形回帰のときは既存のデータにあてはめる仮説の関数を、  hθ(x) = θ0 + θ1 * x のようにしました。今回は答えが〇かXか(0か1か)なのでそのような性質をよく表すことができるものとして、シグモイド関数を使います。 h(x) = g(θT x) g(z) = 1/(1 + exp(z)) この値が0.5のところを境界線としてデータ平面(2次元の時)を1と0の領域に分けます。 実際の計算は前回とだいたい同じ方法ですが、式の形が少し変わります。コスト関数は2乗和の代わりにlogを使います。予測hと答えyが一致した時には0となり違った時には大きな数になるという性質を単に利用したものと思います。 J() = 1/m*sum(i=1:m)(-y(i)*log(h(x(i)))-(1-y(i))*log(1-h(x(i))) 最急降下法に使う式はJの偏微分で、前回と同じです。 2値分類のときにはyは0,1です。これがマルチクラス分類になるとyは[1,2,3,4]ではなく、[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]のように設定しないといけないのが注意点です。 進級試験はまたOctave/Matlabを使ったプログラミング問題です。 答えとしてはこれぐらいの短いコードなんですがまたまた時間がかかってしまいました。 3週目のコースの途中で課題がでてくるのですが、内容的にはビデオを最後までみてからのほうがよいと思います。 次週からはようやくニューラルネットワークがでてくるようで楽しみです。 今回のビデオの最後で、ここまでやればシリコンバレーのたいていの機械学習技術者よりも知識は上だ、みたいなことを言っていました。顔が笑っていたので冗談だと思いますが。

Page 1 / 212
PAGETOP
Copyright © Meuse Robotics All Rights Reserved.
Powered by WordPress & BizVektor Theme by Vektor,Inc. technology.