最小二乗法によるデータ解析

今回は「最小二乗法」をやります。
ざっくり言うとデータがどんな関数から作られたか予測しよう!ってことです。
名前の由来は最初に出てきたコンセプトで、実際のデータと予測値の誤差を二乗したものを最小にし(近づけ)よう!ってなとこからです。
前提条件はいくつかありますがそんなのは最小二乗法 - Wikipediaに任せましょう。
さて。まず最初に覚えてもらうことがあります。
AI(今回は違いますが)とかの学習に使う元のデータを「データセット」と言います。テストに出します。
関数と言いましたが正確には多項式です。つまり多項式近似をするプログラムと言い換えられます。

理由は後にして具体的な方法を話すと、前述のWikipediaに載っている「正規方程式」を使います。
行列の計算によってまとめて答えをはじき出します。それだけ。
{ \displaystyle \boldsymbol{a} = (G^\textrm{T} G)^{-1} G^\textrm{T} \boldsymbol{y}}を解くだけですね。
とは言っても記号の意味とかわからねえよ!と思うのでWikipediaには書いてありますが一つづつ説明します。
まず、データセットの形式ですが、XとYの1:1対応(YはXの関数だと想定しています)なので、

No X Y
1 0.1 0.0
2 0.2 0.3
3 0.3 0.5
4 0.4 0.3
5 0.5 0.0

ってな感じになります。Noはプログラム中でしか使わないので無視してもらって構いません。
で、{ \displaystyle G }ですが、これはXを作りたい関数にそのまま入れてできた行列です。
今回は{ \displaystyle f(x) = a_1 + a_2 x + a_3 x^2 ... a_n x^\textrm{n-1}}のような多項式を想定しているので、先ほどのデータを使うと

0.1^0 0.1^1 0.1^2
0.2^0 0.2^1 0.2^2
0.3^0 0.3^1 0.3^2
0.4^0 0.4^1 0.4^2
0.5^0 0.5^1 0.5^2

となります。Tは転置行列を表すので、

0.1^0 0.2^0 0.3^0 0.4^0 0.5^0
0.1^1 0.2^1 0.3^1 0.4^1 0.5^1
0.1^2 0.2^2 0.3^2 0.4^2 0.5^2

こんな感じになります。ひっくり返したって感じで、詳しく知りたい人は調べるなり下記のソースコード(transposedMatrix())を参照してください。
で、行列が隣り合っているのは行列の積を表します。書くのが大変なので省略します。dot()参照。
行列の-1乗は逆行列を表します。inverseMatrix()参照。
yは文字通りy成分です。

じゃあそれぞれの理由についてですが私なりの解釈が多分に含まれているのでご留意ください。
まずなぜ誤差を2乗するのか、は-を消すため、大きい誤差をより重大だと捉えるため、が考えられます。
最小二乗法と言っているのにそれを計算していないのは、偏微分する際には使ったが最終的な方程式には出てこない、ということだと考えています。数学に強くないので詳しくは分かりません。
Wikipediaにはあまり良くない方法みたいなことが書かれているけど、なぜ別の方法を使わなかったのかというと、理解できなかった計算的な無駄はありますがどうせコンピュータがやる上、最近のCPUは非常に早いのでわかりやすさを優先しました。

また、ここではDouble型を使っていますが、わずかに誤差が出るのでFloatを推奨します。Floatを使うと消える程度の計算上のバグです。
なので、doubleの精度が必要な状況ではミスが出る可能性があります。
ここでは、学習させるデータと同じサイズのテスト用データも生成して「学習しすぎ」を防ぎます。
「学習しすぎた」状態のことをオーバーフィッティングと言います。過学習、ないし過剰適合とも言われます。
最適な値を出すためには、学習用データとテスト用データのerrorがともに下がっている最大のところを取ります。
以下ソースコードになります。

import java.util.Random;

/*    列↓ 列↓ 列↓ 列↓
   行→ 0   1   2   4
   行→ -1  2   0   1
   行→ 1   0  -2  -1
   行→ 3   1   1   3
   Array[行][列]
*/
public class LeastSquaresMethod {
    public static void main (String[] args){
        int[] power = {0,1,3,5,9};
        int size = 20;
        double[][] dataSet = generateDataSet(size);
        double[][] testData = generateDataSet(size);
        double[][] a = new double[size][1];
        showArray(dataSet);
        showArray(testData);
        for(int i = 0; i < size; i++){
            a[i][0] = dataSet[i][1];
        }
        for(int p = 0; p < power.length; p++){
            power[p]++;
            double[][] g = new double[size][power[p]];
            for(int i = 0; i < size; i++){
                for(int j = 0; j < power[p]; j++){
                    g[i][j] = Math.pow(dataSet[i][0], j);
                }
            }
            System.out.println("Power : " + (power[p] - 1));
            double[][] ans = dot(dot(inverseMatrix(dot(transposedMatrix(g), g)), transposedMatrix(g)), a);
            showArray(ans);
            
            double error = 0d;
            double errorTest = 0d;
            for(int i = 0; i < dataSet.length; i++){
                double tmp = 0d;
                double tmpTest = 0d;
                for(int j = 0; j < ans.length; j++){
                    tmp += ans[j][0] * Math.pow(dataSet[i][0], j);
                    tmpTest += ans[j][0] * Math.pow(testData[i][0], j);
                }
                error += Math.pow((dataSet[i][1] - tmp), 2);
                errorTest += Math.pow((testData[i][1] - tmpTest), 2);
            }
            System.out.println("error     : " + error);
            System.out.println("errorTest : " + errorTest + "\n");
        }
    }
    
    public static void showArray(double[][] array){
        for(int i = 0; i < array.length; i++){
            for(int j = 0; j < array[0].length; j++){
                //System.out.printf("%.3f ", array[i][j]);
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
    
    public static double[][] generateDataSet(int size){
        Random rand = new Random();
        double[][] output = new double[size][2];
        for(int i = 0; i < size; i++){
            output[i][0] = (double)i / size;
            output[i][1] = Math.sin(2d * Math.PI * output[i][0]) + rand.nextGaussian() * 0.3d;
        }
        return output;
    }
    
    public static double[][] transposedMatrix(double[][] input){
        double[][] output = new double[input[0].length][input.length];
        for(int i = 0; i < output.length; i++){
            for(int j = 0; j < output[0].length; j++){
                output[i][j] = input[j][i];
            }
        }
        return output;
    }
    
    public static double[][] dot(double[][] input, double[][] input2){
        if(input[0].length != input2.length){
            return null;
        }
        int length = input[0].length;
        double[][] output = new double[input.length][input2[0].length];
        for(int i = 0; i < input.length; i++){
            for(int j = 0; j < input2[0].length; j++){
                double tmp = 0d;
                for(int k = 0; k < length; k++){
                    tmp += input[i][k] * input2[k][j];
                }
                output[i][j] = tmp;
            }
        }
        return output;
    }
    
    public static boolean swapRow(double[][] targetArray, int target, int target2){ // target行とtarget2行を入れ替えます
        int arrayColLength = targetArray[0].length;
        for(int i = 0; i < arrayColLength; i++){
            double tmp = targetArray[target][i];
            targetArray[target][i] = targetArray[target2][i];
            targetArray[target2][i] = tmp;
        }
        return true;
    }
    public static double[][] inverseMatrix(double[][] input){//掃き出し法(ガウス・ジョルダン法)で逆行列を計算します
        if(input.length != input[0].length){
            return null;
        }
        int length = input.length;
        double[][] target = connectArray(input, identityMatrix(length)); //単位行列を結合します
        for(int i = 0; i < length; i++){
            double max = Math.abs(target[i][i]);//行の入れ替えをします
            int maxPiv = i;
            for(int j = i; j < length; j++){
                if(Math.abs(target[j][i]) > max){
                    max = Math.abs(target[j][i]);
                    maxPiv = j;
                }
            }
            swapRow(target, i, maxPiv);
            
            for(int j = 0; j < length; j++){//前進消去します
                if(i == j || target[j][i] == 0){
                        continue;
                }
                double tmp = target[j][i] / target[i][i];
                for(int k = 0; k < length * 2; k++){
                    target[j][k] -= target[i][k] * tmp;
                }
            }
        }
        for(int i = 0; i < length; i++){//左側を単位行列にします
            double tmp = target[i][i];
            for(int j = 0; j < length * 2; j++){
                target[i][j] /= tmp;
            }
        }
        double[][] output = new double[length][length];
        for(int i = 0; i < length; i++){ //右側(計算結果)を切り出します
            for(int j = 0; j < length; j++){
                output[i][j] = target[i][j + length];
            }
        }
        return output;
    }
    
    public static double[][] identityMatrix(int size){ // 単位行列を作ります
        double[][] output = new double[size][size];
        for(int i = 0; i < size; i++){
            output[i][i] = 1;
        }
        return output;
    }
    public static double[][] connectArray(double[][] input, double[][] input2){ //inputにinput2を横に(列を増やして)結合します。行数が同じもののみです
        if(input.length != input2.length){
            return null;
        }
        double[][] output = new double[input.length][input[0].length + input2[0].length];
        for(int i = 0; i < output.length; i++){
            for(int j = 0; j < output[0].length; j++){
                if(j < input[0].length){
                    output[i][j] = input[i][j];
                }
                else{
                    output[i][j] = input2[i][j - input[0].length];
                }
            }
        }
        return output;
    }
}

参考文献:
最小二乗法 - Wikipedia
過剰適合 - Wikipedia
ガウスの消去法 - Wikipedia
行列の乗法 - Wikipedia

にゃーんAPI

お久しぶりです。
今回は思い付きでTwitterでにゃーんAPIを作ったので紹介します。
決してAIが難しくて逃げているわけではありません。

さて、まずTwitter Application Managementでアクセスキーを4つ取得します。ここらへんはほかのブログでも解説されているでしょう。

次に、適当なとこからPHP実行環境を作ります。なんかPHPでやっている人が多そうだったのでそれに倣いました。
今回はWAMP, MAMP and LAMP Stack : Softaculous AMPPSを使いました。
んで、インストールしたらフォルダ見て、AMPPS/www直下にNyaanAPIってフォルダ作って、そこにGitHub - abraham/twitteroauth: The most popular PHP library for use with the Twitter OAuth REST API.からダウンロードしたのをtwitteroauthにリネームして入れて、
PHPからTwitterツイート(2015年2月版) - Qiitaのをコピペして、適当に付け足してできました。

<?php
$head = '';
$body = '';
$foot = '';
if(rand(0,1) == 0) $head .= 'にゃ';
else $head .= 'に゛ゃ';
$max = rand(1,10);
for($i = 0;$i < $max; $i++){
	switch (rand(0,10)) {
		case 0:
			$body .= 'にゃ';
			break;
		case 1:
			$body .= 'に゛ゃ';
			break;
		default:
			$body .= '~';
			break;
	}
}
if(rand(0,1) == 0) $foot = '~';
else $foot = 'ん';
$text = $head . $body . $foot;

// OAuthライブラリの読み込み
require "twitteroauth/autoload.php";
use Abraham\TwitterOAuth\TwitterOAuth;

//認証情報4つ
$consumerKey = "XXXXX";
$consumerSecret = "XXXXX";
$accessToken = "XXXXX";
$accessTokenSecret = "XXXXX";

//接続
$connection = new TwitterOAuth($consumerKey, $consumerSecret, $accessToken, $accessTokenSecret);

//ツイート
$res = $connection->post("statuses/update", array("status" => $text));

//レスポンス確認
var_dump($res);
?>

ね?簡単でしょ?

人工知能でできること

今日は今後の目標と人工知能の歴史、未来について書きます。技術系の記事ではありません。

さて、未来を予測するには、過去と現在を踏まえる必要があります。
当然、積み重ねですから。歴史については人工知能の歴史 - Wikipediaを参照した方が早いと思います。


と、言うわけで、大雑把に話します。
まず、人工知能という呼び名で命名されたのは1956年です。
しかし、古代から同等の概念があり、それに対して様々なアプローチがされてきました。

現在の人工知能の土壌となった考え方は数多くあり、その中でも多くの数学者たちが「思考を体系的に行う」ことについて考えていたことは重要です。
また、人工知能とコンピューターには多くの共通点が存在し、その双方に貢献したアラン・チューリング - Wikipedia
の名前は覚えて損はないでしょう。
彼は、チューリングマシン(アルゴリズムを実行するための計算機)や、チューリングテスト(人とコンピューターの区別ができるか)、チャーチ=チューリングのテーゼ(計算できる関数を帰納的関数と同一視する)など、この分野の発展に大きく貢献しました。
数学とコンピューターを結び付けて考えられるようにしたことは特記すべきでしょう。

生物からのアプローチとして、1943年に形式ニューロン(神経細胞)が発表され、これがニューラルネットワーク(神経回路網,生体の脳のモデル化が目標)の基礎となりました。
これらは話題になっているディープラーニングの基です。ジェフリー・ヒントン - Wikipediaについても見ておくことを推奨します。アラン・チューリングに次ぐ(あるいは超える)革命の親とも言えるかもしれません。


そして人工知能の未来ですが(僕の予測になりますが)、まず隠れた性質を発見することが目的のものを用いて、地震予知マーケティング(売れる弁当と天気の相関など)、機械の設計(より良い性質を合算していく)などがまず上がります。
それから人工'知能'らしいものとして、自動推論(そしてそれをコード化)、会話できるもの、研究に関する論文の抽出を上げられます。
非常に優秀な助手が来るイメージですね。
これらは既存の技術で十分に可能なはずです。

あとはアンドロイド、人工生命あたりでしょうか。(完全に筋の通った)会話ができるものを一から構築する試みはもう少し時間がかかると思います。
主だったものでもこれだけありますし、ゲームのRTAにも使えます。

最初に目標は会話できるもの、としましたが具体的にアップデートすると、ディープラーニングないしそれを発展させたものを構築することです。完成には時間がかかると思われますが近況をあげつつ技術のステップアップができればと思います。
その初歩となるものに数学がとても使われていて微積から勉強を始めることに…数式を見ると眩暈が…

人工知能学習1

今日は強化学習の一つであるε-greedy法で多腕バンディット問題を解きます。

これは、複数のアーム(腕)から最良のものを選択する問題です。

見えていない確率を払い戻しを元に推定していきます。

もともと、スロットマシン(バンディットマシン)での問題だったので、こう呼ばれているようです。

さて、実際に使うε-greedy法は、貪欲法と呼ばれるgreedy法を拡張したもので、greedy法が最も価値の高いものを(一定期間の学習を経たあと)選び続けるのに対し、こちらは学習しつつ最も価値の高いものを選択します。

これにより長期的に払戻額が大きくなるような選択を(最良の選択を)できる確率が高まります。

具体的なアルゴリズムは、

1.まだ選んでいない手があるならその中からランダムに選ぶ

2.確率εで全ての手の中からランダムに選ぶ

3.そうでなければ最も価値の高い手を選ぶ

となっています。

import java.util.Random;

public class e_greedy {

	public static void main(String[] args) {
		Random r = new Random();
		double e = 0.1d;//確率ε
		int gene = 100;//繰り返す(世代を重ねる)回数
		double[] table = {0.6 , 0.5 , 0.4};//確率テーブル(バンディット),払戻額は同じとします
		int[][] log = new int[table.length][2];//選んだ回数と払い戻された回数なので2
		int myarm = 0;
		for(int g = 0;g < gene;g++){//世代数分ループ
			double[] winrate = new double[table.length];//ここから勝率,上書きするので後ろから
			for(int i = 0; i < table.length;i++){
				if(log[i][0] != 0){
					winrate[i] = log[i][1] / (double)log[i][0];
				}
			}
			for(int i = 0; i < winrate.length;i++){
				if(winrate[myarm] >  winrate[i]) continue;
				if(winrate[myarm] == winrate[i] && r.nextDouble() <= 0.5d) myarm = i;
				if(winrate[myarm] <  winrate[i]) myarm = i;
			}
			if(Math.random() <= e) myarm = r.nextInt(table.length);//確率εでランダム
			
			boolean[] zerolist = new boolean[table.length];
			int countzero = 0;
			for(int i = 0; i < table.length; i++){//まだ出していない手をリストに
				if(log[i][0] == 0){
					zerolist[i] = true;
					countzero++;
				}
			}
			
			if(countzero!=0){
				while(true){	
					int tmp = r.nextInt(table.length);//乱数を出してまだ出していない手をランダムに
					if(zerolist[tmp]){
						myarm = tmp;
						break;
					}
				}
			}
			log[myarm][0]++;
			if(r.nextDouble() <= table[myarm]) log[myarm][1]++;
			System.out.println("Gene : " + g + " myarm : " + myarm);
		}
		
	}

}

greedyアルゴリズムは適当に100世代分くらい均等に選んでからそれのみを選択するという手法で簡単にできると思います。

世代の進行と最適化をグラフ出力したかったのですが断念

ライブラリの導入がめんどくさいので...Pythonなら楽そうなんだよなぁ...

人工知能開発0

のんびりやろうと思いつつ日課にしたい気持ちもあり、とりあえず目標をたてます。

このブログの対象は(当然)初心者向けになるので、ざっくり「会話できるものを作る」とします。

 

とはいっても、まず「人工知能とはどういったものなのか」という疑問があると思います。

Wikipediaをみてみると、「日常語としての『人工知能』という呼び名は非常に曖昧なものになって」いるそうなので、「考えて、答えを出すもの」としておきます。

「考えるとは何か」などといった問いは哲学者に任せます。

「何ができるか」と言われても天気と弁当の売れ行きの相関だとかコンピュータ将棋だとか、様々です。最終的に人間の(あるいはそれを超える)知能を作ろうという試みですから当然ともいえます。

 

 

さて、まず人工知能は2パターンに分類されます。一つが「教師あり学習」、もう一つが「教師なし学習」です。

 

教師あり学習は、問題と答えの組が与えられて、それを基に学習します。子供の頃、1+1=2,1+2=3...と学習したように、コンピュータに学習させます。入力に対して(常に)正しい出力を返すことが目的です。

 

それに対して、教師なし学習は与えられた問題のみで考えます。データをどう分類するか、ゲームをどうやってクリアするか、等。正答が決まっていない問題について考えることが目的です。

 

説明しようとすると自分の理解の浅さを実感しますが、実際に作ればわかると思います。多分。

 

開発はjavaで行うつもりです。Pythonを使ってみたいですがハードルあげすぎても(僕が)詰まると思ったので。

まあプログラミングはおまけなので、まあ、うん。

頑張ります。

ブログの方針

人工知能とプログラミングの初心者がなんやかんやして成長しようとするモチベを上げるためのブログです