ホームに戻る
機械学習についての覚え書き(2)
０、はじめに
この記事は2022年頃の記事です。
個人的な覚え書きで、見解は個人的なものです。
１、機械学習の歴史
AIはArtificial Intelligenceの略です。
AI自体は1950年代頃から存在します。
第一次AIブームは単なる全探索でした。
臨機応変な対応ができない、計算量の限界がありました。
第二次AIブームは思考をデータとして与える方法でした。
これは思考を与える手間がかかる、柔軟さに欠ける。
第三次AIブームは囲碁、将棋AIの活躍と画像認識です。
実用的なAIが登場しましたが、まだ一部の分野です。
さて、ここまでAIと書いてきましたが、
実際には機械学習と置き換えることができます。
本来AIは知性や感情も持ち合わせなければいけませんが、
この分野に関してはほとんど成果がありません。
現在のAIができることのほとんどは機械学習です。
機械学習とはデータを元に学習し成果を出すことです。
２、機械学習の種類
現在、機械学習で検索すると以下のように分類されます。
機械学習
教師あり学習 回帰、分類(SVM、深層学習など)
教師なし学習 クラスタリング(k-means法など)
強化学習 Q学習など
例えば、回帰は単なる線形回帰であっても回帰に含みます。
グラフに点を打って線を引いてAIの学習とみなせます。
機械学習の原理はどれも5分ほどで理解できますが、
問題はいかに応用して現実世界で成果を出すかです。
３、機械学習の成果と評価
線形回帰を例にします。
xy平面上の点群と直線との距離の誤差が最小な線を引きます。
このときの評価を最小二乗法で行って直線が引けます。
この直線上の値を予測値として利用することができます。
予測値が現実世界での正解率を上げれば実用的と言えます。
評価は実データを用いた正解率の検証が必要になります。
第三次AIブームでは深層学習が注目されています。
画像認識では以前は正解率が70%程度でした。
しかし、深層学習は正解率を90%以上に上げました。
今や人間の正解率も超えるとも言われています。
囲碁や将棋における盤面評価にも深層学習は応用できます。
第三次AIブームは深層学習が大きな役割を担っています。
４、全探索について
しばらくは機械学習以前の話をします。
全探索については深さ優先探索と幅優先探索があります。
全探索が可能であればそのAIは最強と言えます。
現状の計算機は1秒で100000000程度の計算は行えます。
全探索ができれば全探索を考えましょう。
５、モンテカルロ法とヒルクライム法
全探索するには時間が足りない場合を考えます。
モンテカルロ法は乱数を用いて選択を決定します。
乱数で試行を何回か行って最も良い結果を選択します。
ヒルクライム法は最初はモンテカルロ法で試行を行います。
試行の数か所を変更し結果が良くなった場合を採用します。
悪くなった場合は更新せずに次の変更を試します。
変更を繰り返して結果を改善していきます。
モンテカルロ法とヒルクライム法は実装が簡単です。
そのわりにはそこそこ良い結果を残します。
６、ビームサーチ法
例えばビーム幅3のビームサーチ法を考えます。
１手目で最も有効な3つの手を選択します。
2手目で1手目から辿れる有効な3つの手を選択します。
このように幅を一定にして深く進む方法です。
どの手を有効と評価するかで結果は異なってきます。
７、ミニマックス法、アルファベータ法
対戦ゲームでは自分の選択は最も有効な手、
相手の選択は自分の最も不利な手になるはずです。
この前提で探索を減らす方法がミニマックス法です。
アルファベータ法はミニマックス法の発展です。
アルファ値は自分の選択の最大値として記録します。
ベータ値は相手の選択の最小値として記録します。
アルファ値とベータ値を元に無駄な探索をカットします。
このように無駄な探索をカットする方法を枝刈りと呼びます。
８、深さが膨大な場合の評価について
有効な手を選択するにはその手の評価が必要です。
全探索が可能なら良いのですが、深さが膨大では不可能です。
簡単な方法はモンテカルロ法、ヒルクライム法です。
そうでなければ評価関数を作成するのが良い方法です。
評価関数は人間の手で作ったり、機械学習で作成します。
９、ハッシュテーブル
状態数が膨大になる場合にはメモリ不足が発生します。
ハッシュテーブルはメモリを省略する良い方法です。
ハッシュテーブルの弱点は衝突です。
ハッシュ値に複数の状態を入れることは可能ですが、
同ハッシュ値の状態探索には線形時間が必要です。
１０、強化学習(Q学習)
強化学習とは以下の式のような更新を行います。
Q(s,a)←Q(s,a)+α(r+γmaxQ(s',a')-Q(s,a))
式だけ見ると謎ですが、本質はとても簡単です。
rは現在の状態で得られる報酬です。
αは学習率、γは割引率と呼びます。
Q(s,a)とは状態sと行動aを持つ評価値でQ値と呼びます。
Q値は単に有効な評価値を記録しておくだけの変数です。
Q(s',a')は次の行動の評価値のことです。
maxQ(s',a')とは次の行動での最大の評価値です。
さて、順を追って値の更新をしていきます。
a)ある状態の初期評価値はQ(s,a)とします。
Q(s,a)
b)ある状態に移行すると報酬rを受け取ることができます。
Q(s,a)←r
c)次の状態に移行して得る評価値も加算します。
Q(s,a)←r+Q(s',a')
d)もちろん次の状態は最も評価の高いものを選びます。
Q(s,a)←r+maxQ(s',a')
e)次の状態の評価を100%負担させずに一定の割合γにします。
Q(s,a)←r+γmaxQ(s',a')
f)これをすでにあったQ(s,a)に増分加算する表現に変えます。
Q(s,a)←Q(s,a)+(r+γmaxQ(s',a')-Q(s,a))
g)増分加算を100%負担させずに一定の割合αにします。
Q(s,a)←Q(s,a)+α(r+γmaxQ(s',a')-Q(s,a))
以上のようにして式は表現されています。
式を理解すれば何かすごいことをしてくれる方法ではなく、
より良い値に更新する普遍的な手法とわかります。
１１、Q学習のサンプルコード
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
// じゃんけんは3回勝負です。
// 勝つと3点、あいこは1点、負けは0点です。
#define GAME 3
#define WIN_SCORE 3
#define TIE_SCORE 1
#define LOSE_SCORE 0
string hand = "gcp";
double al = 0.1; // 学習率
double ga = 0.1; // 割引率
int score = 0;
map<string,double> q;
unsigned int xor128(void) {
static unsigned int x = 123456789;
static unsigned int y = 362436069;
static unsigned int z = 521288629;
static unsigned int w = 88675123;
unsigned int t;
t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
// じゃんけんの勝敗判定
int judge(char c0, char c1){
if(c0==c1)return TIE_SCORE;
if(c0=='g'&&c1=='c')return WIN_SCORE;
if(c0=='c'&&c1=='p')return WIN_SCORE;
if(c0=='p'&&c1=='g')return WIN_SCORE;
return LOSE_SCORE;
}
// 次に出す手を考えます
char test(string s){
double mn = 1000.;
string mn_s = "gg";
for(int i = 0; i < 3; i++){
double mx = 0.;
string mx_s = "gg";
for(int j= 0; j < 3; j++){
string s1 = s;
s1 += string(1,hand[j]);
s1 += string(1,hand[i]);
if(q[s1]>=mx){
mx = q[s1];
mx_s = s1;
}
}
if(mx<=mn){
mn = mx;
mn_s = mx_s;
}
}
return mn_s[1];
}
// 3回のじゃんけん トレーニング mode=0 実践 mode=1
string play(int mode){
string ret;
for(int i = 0; i < GAME; i++){
cout << "phase: " << i;
cout << " ('g' , 'c' or 'p')" << endl;
cout << "hand? >> ";
char c0;
cin >> c0;
if(c0!='g'&&c0!='c'&&c0!='p'){
continue;
}
char c1;
if(mode == 0){
c1 = hand[xor128()%3];
}
else{
c1 = test(ret);
}
cout << "you: " << c0 << " ";
cout << "com: " << c1 << endl;
ret += string(1,c0);
ret += string(1,c1);
int res = judge(c0,c1);
if(res==WIN_SCORE){
score += WIN_SCORE;
cout << "win." << endl;
}
else if(res==TIE_SCORE){
score += TIE_SCORE;
cout << "tie." << endl;
}
else{
score += LOSE_SCORE;
cout << "lose." << endl;
}
}
return ret;
}
// Q学習の本体
void train(string s){
string s1 = s;
for(int i = GAME-1; i >= 0; i--){
char c1 = s1.back();
s1.pop_back();
char c0 = s1.back();
s1.pop_back();
double r = judge(c0,c1);
double mx = 0.;
for(int j = 0; j < 3; j++){
for(int k = 0; k < 3; k++){
string s2 = s;
s2 += string(1,hand[j]);
s2 += string(1,hand[k]);
mx = max(mx,q[s2]);
}
}
q[s] += q[s] + al*(r+ga*mx-q[s]);
s = s1;
}
}
int main(){
// ランダム手で100回学習する
for(int i = 0; i < 100; i++){
score = 0;
cout << "train_game: " << i << endl;
string res = play(0);
train(res);
cout << "score: " << score << endl;
cout << endl;
}
// 学習した結果で5回テストする
for(int i = 0; i < 5; i++){
score = 0;
cout << "test_game: " << i << endl;
play(1);
cout << "score: " << score << endl;
cout << endl;
}
}
１２、強化学習についての考察
上のじゃんけんプログラムは手の出かたを学習します。
例えば1回戦でどの手を出すべきかを学習します。
1回戦でグーパー、2回戦でチョキチョキが出たとき、
3回戦ではどの手を出すべきかも学習します。
Q学習は学習した結果を使うのが特徴です。
よって、以下のような2つの特徴があらわれます。
1つ目、じゃんけんでランダムな手を使い学習すると、
ほとんどランダムな手を使う学習結果が得られます。
なんらかの特徴がないと学習しようがないのです。
2つ目、学習した手法と実践の手法が異なると効果がない。
すなわちグーの勝率が高くなるように学習させると、
実践でこちらがパーを出せばより勝てるということです。
１３、深層学習
入力をセットして重み付きのフローを流すことで、
入力の特徴を出力に反映させて判定に用いるものです。
学習することで重みを微調整していきます。
簡単な仕組みなわりには実用的な結果が出ます。
画像認識には畳み込みやプーリングの手法を組み合わせます。
上述しましたがゲーム盤面の評価判定にも使えます。
１４、深層学習のサンプルコード
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
unsigned int xor128(void) {
static unsigned int x = 123456789;
static unsigned int y = 362436069;
static unsigned int z = 521288629;
static unsigned int w = 88675123;
unsigned int t;
t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
class DL{
// 学習率(重みの更新値に加える比率)
double rate = 0.1;
// シグモイド関数で使用するイプシロン値
double epsilon = 1.0;
vector<int> layers;
vector<vector<vector<double> > > weights;
vector<vector<double> > questions;
vector<vector<double> > answers;
vector<vector<double> > outputs;
// 活性化関数で用いるシグモイド関数
double sigmoid(double d){
return 1./(1.+pow(2.71828,-epsilon*d));
}
// -1.0から1.0までの乱数を作成
double get_rnd(){
return ((xor128() % 2000001 * 1.)-1000000)/1000000;
}
void forward(vector<double> v){
outputs.clear();
outputs.push_back(v);
for(int i = 0; i < layers.size()-1; i++){
vector<double> v1;
for(int j = 0; j < layers[i+1]; j++){
double d = 0.;
for(int k = 0; k < outputs[outputs.size()-1].size(); k++){
d += weights[i][j][k]*outputs[outputs.size()-1][k];
}
v1.push_back(sigmoid(d));
}
outputs.push_back(v1);
}
}
void backward(vector<double> v){
vector<vector<double> > vv = calc_delta(v);
for(int i = layers.size()-1; i > 0; i--){
for(int j = 0; j < layers[i]; j++){
for(int k = 0; k < layers[i-1]; k++){
weights[i-1][j][k] += rate * vv[i-1][j] * outputs[i-1][k];
}
}
}
}
// backward で使用
vector<vector<double> > calc_delta(vector<double> v){
vector<double> teacher;
for(int i = 0; i < layers.back(); i++){
teacher.push_back(v[i]);
}
vector<vector<double> > vv;
for(int i = layers.size()-1; i > 0; i--){
vector<double> v1;
for(int j = 0; j < layers[i]; j++){
double d = 0.;
if(i==layers.size()-1){
d += epsilon * outputs[i][j] * (1.-outputs[i][j]) * (teacher[j] - outputs[i][j]);
}
else{
for(int k = 0; k < vv.back().size(); k++){
d += epsilon * outputs[i][j] * (1.-outputs[i][j]) * vv[vv.size()-1][k] * weights[i][k][j];
}
}
v1.push_back(d);
}
vv.push_back(v1);
}
reverse(vv.begin(),vv.end());
return vv;
}
public:
DL(){
// 各レイヤーのノード数を指定
int data[] = {2,6,2};
layers = vector<int>(data,end(data));
}
// テストケースとその答えを設定
void set_testcase(vector<double> v1, vector<double> v2){
questions.push_back(v1);
answers.push_back(v2);
}
// 重みを初期化
void init_weights(){
for(int i = 0; i < layers.size()-1; i++){
vector<vector<double> > vv;
for(int j = 0; j < layers[i+1]; j++){
vector<double> v;
for(int k = 0; k < layers[i]; k++){
v.push_back(get_rnd());
}
vv.push_back(v);
}
weights.push_back(vv);
}
}
// 学習率の設定
void setRate(double r){
rate = r;
}
// 学習率の取得
double getRate(){
return rate;
}
// set_testcase で設定したケースをすべて学習する。
void train(){
if(questions.size()==0){
cout << "Please set_testcase" << endl;
return;
}
for(int i = 0; i < questions.size(); i++){
forward(questions[i]);
backward(answers[i]);
}
}
// 学習した重みでテスト
int test(vector<double> v){
if(v.size()!=layers[0]){
cout << "numbers of input is incorrect" << endl;
return -1;
}
forward(v);
int ret = -1;
double mx = -1.0;
for(int i = 0; i < outputs.back().size(); i++){
if(outputs.back()[i] > mx){
ret = i;
mx = outputs.back()[i];
}
}
return ret;
}
// 結果値を出力
void print_output(){
for(int i = 0; i < outputs.back().size(); i++){
cout << i << " " << outputs.back()[i] << endl;
}
}
// 重みを出力
void print_weights(){
for(int i = 0; i < layers.size()-1; i++){
vector<vector<double> > vv;
for(int j = 0; j < layers[i+1]; j++){
for(int k = 0; k < layers[i]; k++){
cout << j << " " << k << " " << weights[i][j][k] << endl;
}
}
}
}
};
int main(){
DL dl;
dl.init_weights();
// テストケースを300個登録
for(int i = 0; i < 300; i++){
vector<double> v1, v2;
if(xor128()%2==0){
v1.push_back(1.0);
v1.push_back(0.0);
v2.push_back(0.9);
v2.push_back(0.1);
}
else{
v1.push_back(0.0);
v1.push_back(1.0);
v2.push_back(0.1);
v2.push_back(0.9);
}
dl.set_testcase(v1,v2);
}
// 学習率 0.1 で 100 回学習
dl.setRate(0.1);
for(int i = 0; i < 100; i++){
dl.train();
}
// 学習率 0.01 で 100 回学習
dl.setRate(0.01);
for(int i = 0; i < 100; i++){
dl.train();
}
// 300個の問題を解いてみる
for(int i = 0; i < 300; i++){
vector<double> v;
if(xor128()%2==0){
cout << "Question:A" << endl;
v.push_back(1.0);
v.push_back(0.0);
}
else{
cout << "Question:B" << endl;
v.push_back(0.0);
v.push_back(1.0);
}
dl.test(v);
dl.print_output();
}
return 0;
}
１５、深層学習についての考察
深層学習についても学習した結果を用いるのが特徴です。
この際に何層にするか、各層に何ノード使うか、
活性化関数に何を使うかで迷うと思います。
定番の方針は定まっておらず試行錯誤が必要です。
