Archives

TensorFlowをec2のgpuインスタンスで実行するまでの手順

Python、データ分析界隈はTensorFlowの登場でにわかに沸き立っていますが、実はTensorFlowはデフォルトでサポートしているgpuに制限があり、Nvidia Compute Capability 3.5 以上のgpuしか使えません。そして大体のひとが使うであろうawsのgpuインスタンスの GRID K520 のNvidia Compute Capabilityは3.0です。ドラゴンボールだと一般人以下です。つまりゴミ以下なのでTensorFlowは使えません。

もちろん既にGitHubでもissueが立っており、公式に対応してくれています。

https://github.com/tensorflow/tensorflow/issues/25

configure時に

TF_UNOFFICIAL_SETTING=1 ./configure

とすればNvidia Compute Capability選択させたるで!とのこと。やったね!

ってbuild必要なんかい!というわけで環境構築を行います。なお、途中でcuDNNが必要になりますが、cuDNNのダウンロードはnvdiaに登録後、1日ぐらい審査に時間がかかるので、早めに申請することをおすすめします。

前準備

awsのリージョンはオレゴンとかの田舎にしましょう。安いので。Ubuntu 14.04のインスタンスを起動します。


# localeをtokyoに変更
sudo cp /usr/share/zoneinfo/Asia/Tokyo /etc/localtime
sudo locale-gen ja_JP.UTF-8

# rootになる
sudo su -

# 各種ツールをインストール。
# linux-image-extra-virtualのインストールでは、"install the package maintainer's version"を選択する。(cudaのインストールに必要。)
apt-get update && apt-get install -y build-essential linux-image-extra-virtual wget git default-jdk zip zlib1g-dev swig

# cudaをインストールする前に既存のドライバ(nouveau)を無効化する
vi /etc/modprobe.d/blacklist-nouveau.conf
# 下記を書いて保存 ----------------------
blacklist nouveau
blacklist lbm-nouveau
options nouveau modeset=0
alias nouveau off
alias lbm-nouveau off
# ---------------------------------------

echo options nouveau modeset=0 | sudo tee -a /etc/modprobe.d/nouveau-kms.conf
update-initramfs -u
reboot


# 再起動後、anaconda pythonをインストール
sudo su -
wget --quiet https://repo.continuum.io/archive/Anaconda-2.3.0-Linux-x86_64.sh && /bin/bash Anaconda-2.3.0-Linux-x86_64.sh -b -p /opt/conda

# pathの設定
vi /etc/profile.d/path.sh
# ---------------------------------------
export PATH=/opt/conda/bin:$PATH
# ---------------------------------------

# path設定を読み込む
source /etc/profile.d/path.sh
# default encodingをutf-8にする。(TensorFlowには関係ないけど、やっといた方が後々助かる)
vi /opt/conda/lib/python2.7/sitecustomize.py
# ---------------------------------------
import sys
sys.setdefaultencoding('utf-8')
# ---------------------------------------

# CUDA 7.0のインストール (7.5は未サポート)
apt-get install -y linux-source linux-headers-$(uname -r)
export CUDA_MAJOR=7.0
export CUDA_VERSION=7.0.28
export CUDA_MAJOR_U=7_0
cd /tmp && wget http://developer.download.nvidia.com/compute/cuda/${CUDA_MAJOR_U}/Prod/local_installers/cuda_${CUDA_VERSION}_linux.run && chmod +x cuda_*_linux.run && ./cuda_*_linux.run -extract=`pwd` &&   ./NVIDIA-Linux-x86_64-*.run -s
modprobe nvidia
./cuda-linux64-rel-*.run
./cuda-samples-linux-*.run

# 確認 (これをしないと/dev/以下にデバイスファイルが出てこない)
cd /usr/local/cuda/samples/1_Utilities/deviceQuery
make
./deviceQuery
# ls /dev/ すると、nvdia系のデバイスが見えるようになっている。

# cudnn 6.5
# cudnn-6.5-linux-x64-v2.tgzはnvdiaのサイトに登録して自分でダウンロードしてくる
tar xvzf cudnn-6.5-linux-x64-v2.tgz
cp cudnn-6.5-linux-x64-v2/cudnn.h /usr/local/cuda/include
cp cudnn-6.5-linux-x64-v2/libcudnn* /usr/local/cuda/lib64
reboot

# 再起動後、buildに必要なbazelをインストール
git clone https://github.com/bazelbuild/bazel.git
cd bazel
# バージョンは0.1.0のみサポート
git checkout tags/0.1.0
./compile.sh
sudo cp output/bazel /usr/bin

TensorFlowのインストール


# install tensorflow
cd ~/
# submoduleとしてprotocol buffersを使うので、オプションが必要
git clone --recurse-submodules https://github.com/tensorflow/tensorflow
cd tensorflow

# configureで、Nvidia Compute Capability に3.0を許可する。
TF_UNOFFICIAL_SETTING=1 ./configure

# 以下のような出力が出るので、書いたとおりに入力する
Do you wish to build TensorFlow with GPU support? [y/n]  -> y エンター
GPU support will be enabled for TensorFlow

Please specify the location where CUDA 7.0 toolkit is installed. Refer to README.md for more details. [Default is /usr/local/cuda]: -> エンター
Please specify the location where CUDNN 6.5 V2 library is installed. Refer to README.md for more details. [Default is /usr/local/cuda]: -> エンター

WARNING: You are configuring unofficial settings in TensorFlow. Because some external libraries are not backward compatible, these settings are largely untested and unsupported.

Please specify a list of comma-separated Cuda compute capabilities you want to build with.
You can find the compute capability of your device at: https://developer.nvidia.com/cuda-gpus.
Please note that each additional compute capability significantly increases your build time and binary size.
[Default is: "3.5,5.2"]: -> 3.0 エンター
Setting up Cuda include
Setting up Cuda lib64
Setting up Cuda bin
Setting up Cuda nvvm
# ---------------------------------------

# ビルド時のデフォルトのincludeディレクトリは /usr/include/python2.7 になっているので、
# includeディレクトリをanaconda pythonのものに変更 (ソースを変更するのでも良いと思う)
sudo ln -s /opt/conda/include/python2.7 /usr/include/python2.7
sudo ln -s /opt/conda/lib/python2.7/site-packages/numpy/core/include/numpy /opt/conda/include/python2.7/numpy

# cuda, cnnのライブラリをシンボリックリンク (pipのパッケージを作成するときに必要。)
# バッドノウハウっぽいのでもっとスマートなやり方があれば知りたい
sudo ln -s /usr/local/cuda/lib64/* /opt/conda/lib

# build
bazel build -c opt --config=cuda //tensorflow/cc:tutorials_example_trainer

# テスト実行
# エラーが出なければおk
/usr/local/cuda/samples/1_Utilities/deviceQuery/deviceQuery
bazel-bin/tensorflow/cc/tutorials_example_trainer --use_gpu


# pipパッケージをbuild
sudo /opt/conda/bin/pip install --upgrade pip
sudo /opt/conda/bin/pip install wheel

bazel build -c opt --config=cuda //tensorflow/tools/pip_package:build_pip_package
bazel-bin/tensorflow/tools/pip_package/build_pip_package /tmp/tensorflow_pkg
sudo /opt/conda/bin/pip install /tmp/tensorflow_pkg/tensorflow-0.5.0-py2-none-any.whl

# pythonからの動作テスト(mnist)
cd tensorflow/models/image/mnist
python convolutional.py

こんな感じでなんとかインストールして実行出来ました。
マイami化しておくと、次に使う時は便利です。
早くpipのパッケージでもec2サポートしてくれれば良いのですが。。。

ほんとに速くなるのか

Python – TensorFlow 畳み込みニューラルネットワークで手書き認識率99.2%の分類器を構築 – Qiita

この記事で使われているCNNのサンプルを、gpuバージョンとそうでないバージョン(どちらもg2.2xlarge)で実行したところ、

gpuアリ: 10分ぐらい

gpuナシ: 50分ぐらい

で学習終了しました。最初に上げたGitHub issueでは、「そもそもawsのgpuインスタンスは速くない」みたいな話が出てました。まあこんなところかなという気がします。

lstmで自然な受け答えができるボットをつくった

(2016-12-11 追記) この記事で紹介している学習済モデルは、現行のchainerのバージョンでは使用できなくなっているので、chainer 1.4.1 をインストールしたdocker imageを使う方法を追記しました。新しく学習される方は最新のchainerを使うことをおすすめします。

 

コードを理解する程度のスキルがあればDeep Learningが使える世の中になっているので、試しに自然な受け答えができるボットを作ってみた。

学習

自然な受け答えを行う日本語のデータセットということで、ask.fmをクロールしたデータを用いる。

ask.fmのディレクトリは”ask.fm/アカウント名”のようになっていて、ask.fmのアカウント名のリストがないことにはクロールしようがない。今回は、トップページに訪れた際に表示されるアカウントのリストを定期的に収集することでアカウント名のリストを作った。

Ask_fm

負荷をかけすぎないよう、30分に1回ぐらいトップページにアクセスすること1ヶ月、1,600ぐらいのアカウント名が取得できた。各アカウントのページには最新の質問と答えがいくつか表示されているので、それらを取得する。データ量は8MBぐらいになった。(ちなみに10日ぐらいで600ぐらいのアカウント、学習データは4MBぐらいになるのでそれでも十分)

中身はこんな感じ。

lstm-input

質問と答えの後に1行空白行を入れている。

ChainerでLanguage ModelをLSTMで使うコードがあったので、ありがたく使わせてもらう。

https://github.com/yusuketomoto/chainer-char-rnn

askfmをクロールしたデータをinput.txtとした。パラメータはDeepDazaiを参考にして、隠れ層のノード数を増やした。

前に作ったCUDAとDockerをインストール済のAMIをオレゴンに作り、cudaとchainerをインストールしてあるDocker imageをpullして学習させる。


# gpuの有効化
/usr/local/cuda/samples/1_Utilities/deviceQuery/deviceQuery

# docker imageの起動
DOCKER_NVIDIA_DEVICES=”–device /dev/nvidia0:/dev/nvidia0 –device /dev/nvidiactl:/dev/nvidiactl –device /dev/nvidia-uvm:/dev/nvidia-uvm”
sudo docker run –name chainer -v $PWD:/notebook -p 8888:8888 -d $DOCKER_NVIDIA_DEVICES drunkar/cuda-caffe-anaconda-chainer

# deep-dazaiのbranchを取ってくる
git clone https://github.com/longjie/chainer-char-rnn.git
cd chainer-char-rnn
git checkout -b new-branch origin/new-branch

# cv/askfm、data/askfmディレクトリを作る
# 学習データをinput.txtとしてdata/askfmに置く

# 学習の実行
python train.py --data_dir data/askfm --checkpoint_dir cv/askfm --rnn_size 1024

4MBの学習データなら8時間ぐらい、8MBのデータなら20時間ぐらい学習にかかったと思う。オレゴンのgpuインスタンスで2000円ぐらい。高い。

学習途中にモデルデータがどんどん溜まっていくので、インスタンスの容量が少ない場合は適宜消さないと学習が途中で終わってしまうので注意。時は金なり(切実)。

hubotにしゃべらせる

モデルの学習が終わったら、それを使ってhubotにしゃべってもらう。getリクエストのパラメータに文字列を渡すと、続きを予測して表示してくれるAPIをtornadoで作り、hubotからAPIでアクセスする。hubot側の返答パターンは2通り。

  • askfmは「質問と答え」という特殊な文字列なので、「?」の後には回答が来やすくなる。なのでhubotは質問をメンションで受け取り、クエスチョンマークを末尾につけてAPIをコールするようにした。
  • たまに自然に会話に参加してほしいので、全発言をhearして、メンション以外の全発言に対して10%の確率で返答するようにした。APIは発言の続きを予測するので、2文目以降をhubotの発言とした。

しばらくしゃべってもらって調整したのは以下の2点。

  • クエスチョンマークの後にはクエスチョンマークがかなりの確率でやってきてしまう (「??」みたいな聞き方が多いため)ので、”?¥n”をAPI側でlstripした。
  • あまり意味が通じないとしても、hubotの発言は短ければそれなりに破綻しない発言として人間に解釈されやすい。ので、hubotの発言は1文か2文(ランダム)に制限した。

tornadoで作ったAPIとhubotスクリプトはgithubに上げてます。1,600アカウント分のデータを学習した学習済モデルも含まれているので、dockerがインストールしてあるマシンなら今すぐにでもしゃべらせられます。

https://github.com/Drunkar/japanese_talk_api


# apiデータをclone
git clone https://github.com/Drunkar/japanese_talk_api.git

# tornadoを動かすdocker containerを起動
# entrypointではjupiter notebookが走るけど気にしない
docker run --name japanese_talk_api -d -p 80:8787 -v japanese_talk_api:/app drunkar/cuda-caffe-anaconda-chainer

# (2016-12-11 追記)
# 学習済モデルを使う場合は、以下のコマンドでdockerを起動してください。
docker run --name japanese_talk_api -d -p 80:8787 -v japanese_talk_api:/app drunkar/cuda-caffe-anaconda-chainer1.4.1

# tornadoを起動するための別プロセスを走らせる
docker exec -it japanese_talk_api bash
# sampleモデルをダウンロード
cd /app/tornado/models ./download_sample_model.sh
# tornadoを起動
cd /app python tornado/app.py --port=8787 --debug=True
# プロセスを走らせたままcontainerから抜ける
ctrl+p, ctrl+q 

pickleモデル(chainermodel)のロードに30秒ぐらいかかるので、ちょっと待ってからAPIと試す。

http://localhost/?q=こんにちは

なんか適当にjsonが返ってきたらおk。後は付属のhubot scriptでアクセスしましょう。

名言集

hyohyoがボット。(名前は『カイバ』から。アイコンは忍野扇(女))

  • 出演を断る

hyohyo1__1_

  • ツイ廃

hyohyo2_2

 

  • 独特の世界観

hyohyo3

ask.fmがツイッターを中心としたメディアなので、やたらとツイッターのことを言ってくるし、淫夢厨だったりゲスかったりします。日本からask.fmにアクセスしているとはいえ、日本語以外のアカウントもまあまあ紛れているので英語や韓国語も話せます。

わかったこと

  • 人工無能でもAIは愛しい: 予想の斜め上をいく発言をしたり、うまく発言してくれなかったりすることもあって妙に可愛いです。AIBOがヒットする理由もなんとなく分かりましたし、ヒューマノイドが話相手になるということに確信が持てました。
  • チャットが和む: 普通に会話している時に突如パンツの話とかをしだすので、チャットが和みます。

C++で「はじめての機械学習」5章

5章は遺伝的アルゴリズムです。
ルーレット選択、一点交叉、突然変異、のsimpleGAです。最初は、目的関数最適化をめざすヒューリスティック。

/**
 * simpleGA:
 * 1 遺伝子プールの初期化
 * 2 loop{
 *  交叉(親の選択を含む)
 *  突然変異
 *  結果の出力
 * }
 * 使い方:
 *  $./simpleGA (遺伝子の桁数) (遺伝子の数) (終了条件スイッチ) (終了条件) > (出力ファイル)
 * 終了条件スイッチ:(終了条件)を指定。0->ループ回数、1->最高適応度下限
 **/

#include <iostream>
#include <string>
#include <limits>
#include <cstdlib>
#include <ctime>
using namespace std;

inline void initRand()
{
    srand((unsigned int)time(NULL));
}

inline int randLessThan(const int &n)
{
    int answer = n;
    while(answer == n) answer = ((double)rand() / RAND_MAX) * n;
    return answer;
}

/**遺伝子プールの初期化**/
void initializePool(int **pool, const int &numGene, const int &lenGene)
{
    initRand();
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = rand() % 2;
        }
    }
}

/**!!適用データに応じて変更!!**/
/**適応度の計算**/
int evaluateFitness(const int gene[], const int &lenGene)
{
    // 配列q中の数字を足すことで、最も499に近くなる組み合わせを探す。
    // 適応度が大きくなるほど最適となるように、1000から引いている。
    // このサンプルでは遺伝子数は20でなければならない。
    int q[] = {31, 41, 59, 26, 53, 58, 97, 93, 23, 84,
        -62, -64, -33, -83, -27, -95, -2, -88, -41, -97};
    int fitness = 0;
    for(int i=0; i<lenGene; ++i){
        fitness += gene[i] * q[i];
    }

    return 1000 - abs(499 - fitness);
}

/**!!適用データに応じて変更!!**/
/**交叉のための親を選択(ルーレット選択)**/
int select(const int roulette[], const int &numGene, const int &totalFitness)
{
    int ball;        // 玉(選択位置の数値)
    int acc = 0;     // 適応度の積算値

    ball =randLessThan(totalFitness);
    for(int i=0; i<numGene; ++i){
        acc += roulette[i];
        if(acc > ball) return i;
    }
}

/**!!適用データに応じて変更!!**/
/**特定の2遺伝子の交叉(一点交叉)**/
void crossing(const int &lenGene, const int father[],
        const int mother[], int child1[], int child2[])
{
    int crossPoint; // 交叉する点

    // 交叉点の決定
    crossPoint = randLessThan(lenGene);
    // 遺伝子の前半部分をコピー
    for(int i=0; i<crossPoint; ++i){
        child1[i] = father[i];
        child2[i] = mother[i];
    }
    // 遺伝子の後半部分をコピー
    for(int i=crossPoint; i<lenGene; ++i){
        child1[i] = mother[i];
        child2[i] = father[i];
    }
}

/**交叉**/
void mating(int **pool, const int &numGene, const int &lenGene)
{
    int roulette[numGene];           // 適応度を格納
    int totalFitness = 0;            // 適応度の合計値
    int father = 0, mother = 0;      // 親の遺伝子番号
    int nextPool[numGene][lenGene];  // 子の世代

    // ルーレットの作成
    for(int i=0; i<numGene; ++i){
        roulette[i] = evaluateFitness(pool[i], lenGene);
        totalFitness += roulette[i];
    }

    // 選択と交叉を繰り返す
    for(int i=0; i<numGene/2; ++i){
        while(father==mother){
            father = select(roulette, numGene, totalFitness);
            mother = select(roulette, numGene, totalFitness);
        }
        // 交叉
        crossing(lenGene, pool[father], pool[mother],
                nextPool[i*2], nextPool[i*2+1]);
    }

    // 次世代のプールをコピー
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = nextPool[i][j];
        }
    }
}

/**真理値の反転(突然変異に使う)**/
inline int notVal(const int &val)
{
    if(val == 1) return 0;
    else return 1;
}

/**!!適用データに応じて変更!!**/
/**突然変異(反転)**/
void mutation(int **pool, const int &numGene, const int &lenGene,
        const int &MUTATIONRATE)
{
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            if((double)randLessThan(100) / 100 <= MUTATIONRATE)
                pool[i][j] = notVal(pool[i][j]);
        }
    }
}

/**状態を出力**/
void printCondition(int **pool, const int &numGene, const int &lenGene,
                    int &elite, int &bestfit)
{
    int     fitness;
    double  totalFitness = 0;
    bestfit = 0;

    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            cout << pool[i][j];
        }
        fitness = evaluateFitness(pool[i], lenGene);
        cout << "t" << fitness << endl;
        // elite
        if(fitness > bestfit){
            bestfit = fitness;
            elite = i;
        }
        totalFitness += fitness;
    }

    // エリート解の適応度を出力
    cout << elite << "t" << bestfit << endl;
    // 平均の適応度を出力
    cout << totalFitness / numGene << endl;
}

int main(int argc,  char *argv[])
{
    // 定数
    const double MUTATIONRATE = 0.01; // 突然変異率

    // 変数
    int     lenGene, numGene;    // 遺伝子の桁数、遺伝子数
    int     iterationSwitch;     // 終了条件スイッチ
    int     numIteration = 0;    // 繰り返し回数(if iterationSwitch==0)
    double  fitnessLimit = 0.0;  // 最高適応度下限(if iterationSwitch==1)
    int     **pool = 0;          // 遺伝子プール
    int     elite;               // エリート遺伝子のインデックス
    int     bestfit = 0;         // エリート遺伝子の適応度

    // 引数のチェック
    if(argc != 5){
        cerr << "使い方 $./simpleGA "
            << "(遺伝子の桁数) (遺伝子の数) (終了条件スイッチ) (終了条件) "
            << "> (出力ファイル)" << endl;
        return -1;
    }
    if((lenGene=atoi(argv[1])) < 1){
        cerr << "遺伝子の桁数が不適切です" << endl;
        return -1;
    }
    if((numGene=atoi(argv[2])) < 1){
        cerr << "遺伝子の数が不適切です" << endl;
        return -1;
    }
    if((iterationSwitch=atoi(argv[3]))<0 || iterationSwitch>1){
        cerr << "終了条件スイッチは0か1を入力してください。" << endl
            << "0:終了条件は繰り返し回数" << endl
            << "1:終了条件は最高適応度の下限" << endl;
        return -1;
    }
    if(iterationSwitch==0){
        if((numIteration=atoi(argv[4])) < 1){
            cerr << "終了条件(繰り返し回数)が不適切です" << endl;
            return -1;
        }
    } else {
        fitnessLimit=atof(argv[4]);
    }

    // get memory
    pool = new int * [numGene];
    for(int i=0; i<numGene; ++i){
        pool[i] = new int [lenGene];
    }

    // 1. initialize pool
    initializePool(pool, numGene, lenGene);

    // 2. loop
    // 繰り返し回数が固定
    if(iterationSwitch==0){
        for(int i=0; i<numIteration; ++i){
            cout << i << "世代" << endl;
            mating(pool, numGene, lenGene);                 // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene, elite, bestfit);
        }
    // 適応度の下限が指定されている
    } else if(iterationSwitch==1){
        int iteration = 0;
        while(bestfit<fitnessLimit){
            cout << iterationSwitch++ << "世代" << endl;
            mating(pool, numGene, lenGene);                 // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene, elite, bestfit);
        }

    }

    // memory release
    if(pool != 0){
        for(int i=0; i<numGene; ++i) delete [] pool[i];
        delete [] pool;
    }

    return 0;
}

後半は、4章の論理式によるカテゴリ分類の組み合わせ最適化用にsimpleGAを書き換えます。

/**
 * gaml:
 * 各データの、特徴ごとの分類と含まれるカテゴリを入力データとして、
 * 最もデータを効率良く分類する特徴の組み合わせを探索する。
 * 遺伝子の桁数は、特徴数*2(否定)に分類回数をかけたものとなる。
 * 評価値は、分類率を%で表す。つまり100点満点。
 * 1 遺伝子プールの初期化
 * 2 loop{
 *  交叉(親の選択を含む)
 *  突然変異
 *  結果の出力
 * }
 * 使い方:
 *  $./simpleGA (遺伝子の数) (終了条件スイッチ) (終了条件)
 *              < (入力ファイル) > (出力ファイル)
 * 終了条件スイッチ:(終了条件)を指定。0->ループ回数、1->最高適応度下限
 * 入力ファイル(例):
 *  3        <-分類回数
 *  4        <-特徴数
 *  1 0 1 1 1   <-各特徴に対する分類と、最後にカテゴリ
 *  0 1 0 0 1
 *      :
 *      :
 **/

#include <iostream>
#include <string>
#include <vector>
#include <limits>
#include <cstdlib>
#include <ctime>
using namespace std;

inline void initRand()
{
    srand((unsigned int)time(NULL));
}

inline int randLessThan(const int &n)
{
    int answer = n;
    while(answer == n) answer = ((double)rand() / RAND_MAX) * n;
    return answer;
}

/**遺伝子プールの初期化**/
void initializePool(int **pool, const int &numGene, const int &lenGene)
{
    initRand();
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = rand() % 2;
        }
    }
}

/**真理値の反転(突然変異と論理式評価に使う)**/
inline int notVal(const int &val)
{
    if(val == 1) return 0;
    else return 1;
}

/**!!適用データに応じて変更!!**/
/**特定のデータに対する分類が正しいかを返す**/
int evaluate(const int gene[],
                const vector<int> &dataField,
                const int &numTerm, const int &numAttribute)
{
    int orValue, andValue, result;
    andValue = 1;
    // 論理積で項を結んだ、式全体の評価
    for(int i=0; i<numTerm; ++i){
        orValue = 0;
        // 論理和で結んだ項の評価
        for(int j=0; j<numAttribute*2; ++j){
            if((j%2) == 0) orValue += dataField[j/2] * gene[i*numAttribute*2+j];
            else orValue += notVal(dataField[j/2]) * gene[i*numAttribute*2+j];
        }
        if(orValue == 0) andValue = 0;
        else andValue += 1;
    }

    // 結果がカテゴリと不一致
    if(andValue == gene[numAttribute]) return 1;
    // 一致
    else return 0;
}

/**!!適用データに応じて変更!!**/
/**適応度の計算**/
int evaluateFitness(const int gene[],
                    const vector< vector<int> > &data,
                    const int &numTerm, const int &numAttribute)
{
    int point = 0; // 正しく分類されたデータの個数
    for(int i=0; i<data.size(); ++i){
        point += evaluate(gene, data[i], numTerm, numAttribute);
    }
    // 評価値(100点満点)を返す
    return 100*point / data.size();
}

/**!!適用データに応じて変更!!**/
/**交叉のための親を選択(ルーレット選択)**/
int select(const int roulette[], const int &numGene, const int &totalFitness)
{
    int ball;        // 玉(選択位置の数値)
    int acc = 0;     // 適応度の積算値

    ball =randLessThan(totalFitness);
    for(int i=0; i<numGene; ++i){
        acc += roulette[i];
        if(acc > ball) return i;
    }
}

/**!!適用データに応じて変更!!**/
/**特定の2遺伝子の交叉(一点交叉)**/
void crossing(const int &lenGene, const int father[],
        const int mother[], int child1[], int child2[])
{
    int crossPoint; // 交叉する点

    // 交叉点の決定
    crossPoint = randLessThan(lenGene);
    // 遺伝子の前半部分をコピー
    for(int i=0; i<crossPoint; ++i){
        child1[i] = father[i];
        child2[i] = mother[i];
    }
    // 遺伝子の後半部分をコピー
    for(int i=crossPoint; i<lenGene; ++i){
        child1[i] = mother[i];
        child2[i] = father[i];
    }
}

/**交叉**/
void mating(int **pool, const int &numGene, const int &lenGene,
            const vector< vector<int> > &data,
            const int &numTerm, const int &numAttribute)
{
    int roulette[numGene];           // 適応度を格納
    int totalFitness = 0;            // 適応度の合計値
    int father = 0, mother = 0;      // 親の遺伝子番号
    int nextPool[numGene][lenGene];  // 子の世代

    // ルーレットの作成
    for(int i=0; i<numGene; ++i){
        roulette[i] = evaluateFitness(pool[i], data, numTerm, numAttribute);
        totalFitness += roulette[i];
    }

    // 選択と交叉を繰り返す
    for(int i=0; i<numGene/2; ++i){
        while(father==mother){
            father = select(roulette, numGene, totalFitness);
            mother = select(roulette, numGene, totalFitness);
        }
        // 交叉
        crossing(lenGene, pool[father], pool[mother],
                nextPool[i*2], nextPool[i*2+1]);
    }

    // 次世代のプールをコピー
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            pool[i][j] = nextPool[i][j];
        }
    }
}

/**!!適用データに応じて変更!!**/
/**突然変異(反転)**/
void mutation(int **pool, const int &numGene, const int &lenGene,
        const int &MUTATIONRATE)
{
    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            if((double)randLessThan(100) / 100 <= MUTATIONRATE)
                pool[i][j] = notVal(pool[i][j]);
        }
    }
}

/**状態を出力**/
void printCondition(int **pool, const int &numGene, const int &lenGene,
                    const vector< vector<int> > &data,
                    const int &numTerm, const int &numAttribute,
                    int &elite, int &bestfit)
{
    int     fitness;
    double  totalFitness = 0;
    bestfit = 0;

    for(int i=0; i<numGene; ++i){
        for(int j=0; j<lenGene; ++j){
            cout << pool[i][j];
        }
        fitness = evaluateFitness(pool[i], data, numTerm, numAttribute);
        cout << "t" << fitness << endl;
        // elite
        if(fitness > bestfit){
            bestfit = fitness;
            elite = i;
        }
        totalFitness += fitness;
    }

    // エリート解の適応度を出力
    cout << elite << "t" << bestfit << endl;
    // 平均の適応度を出力
    cout << totalFitness / numGene << endl;
}

int main(int argc,  char *argv[])
{
    // 定数
    const double MUTATIONRATE = 0.01; // 突然変異率

    // 変数
    int     lenGene, numGene;    // 遺伝子の桁数、遺伝子数
    int     iterationSwitch;     // 終了条件スイッチ
    int     numIteration = 0;    // 繰り返し回数(if iterationSwitch==0)
    double  fitnessLimit = 0.0;  // 最高適応度下限(if iterationSwitch==1)
    int     **pool = 0;          // 遺伝子プール
    int     elite;               // エリート遺伝子のインデックス
    int     bestfit = 0;         // エリート遺伝子の適応度
    int     numTerm;             // 論理式の論理和項の個数
    int     numAttribute;        // 属性値の個数
    vector< vector<int> > data;  // 入力データ

    // 引数のチェック
    if(argc != 4){
        cerr << "使い方 $./simpleGA "
            << "(遺伝子の数) (終了条件スイッチ) (終了条件) "
            << "< (入力ファイル) > (出力ファイル)" << endl;
        return -1;
    }
    if((numGene=atoi(argv[1])) < 1){
        cerr << "遺伝子の数が不適切です" << endl;
        return -1;
    }
    if((iterationSwitch=atoi(argv[2]))<0 || iterationSwitch>1){
        cerr << "終了条件スイッチは0か1を入力してください。" << endl
            << "0:終了条件は繰り返し回数" << endl
            << "1:終了条件は最高適応度の下限"   << endl;
        return -1;
    }
    if(iterationSwitch==0){
        if((numIteration=atoi(argv[3])) < 1){
            cerr << "終了条件(繰り返し回数)が不適切です" << endl;
            return -1;
        }
    } else {
        fitnessLimit=atof(argv[3]);
    }

    // データ入力
    cin >> numTerm;
    cin >> numAttribute;
    lenGene = numTerm*(numAttribute*2);
    while(true){
        // データをdataBufferに読み込む
        int dataBuffer[numAttribute+1];
        cin >> dataBuffer[0];
        if(cin.eof()) break;
        for(int i=1; i<numAttribute+1; ++i){
            cin >> dataBuffer[i];
        }
        // dataBufferをrowBufferにコピー
        vector<int> rowBuffer;
        for(int i=0; i<numAttribute+1; ++i){
            rowBuffer.push_back(dataBuffer[i]);
        }
        // rowBufferをdataに追加
        data.push_back(rowBuffer);
    }

    // get memory
    pool = new int * [numGene];
    for(int i=0; i<numGene; ++i){
        pool[i] = new int [lenGene];
    }

    // 1. initialize pool
    initializePool(pool, numGene, lenGene);

    // 2. loop
    // 繰り返し回数が固定
    if(iterationSwitch==0){
        for(int i=0; i<numIteration; ++i){
            cout << i << "世代" << endl;
            mating(pool, numGene, lenGene, data, numTerm, numAttribute); // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene,
                            data, numTerm, numAttribute, elite, bestfit);
        }
    // 適応度の下限が指定されている
    } else if(iterationSwitch==1){
        int iteration = 0;
        while(bestfit<fitnessLimit){
            cout << iterationSwitch++ << "世代" << endl;
            mating(pool, numGene, lenGene, data, numTerm, numAttribute); // 交叉
            mutation(pool, numGene, lenGene, MUTATIONRATE); // 突然変異
            printCondition(pool, numGene, lenGene, data,
                            numTerm, numAttribute, elite, bestfit);
        }

    }

    // memory release
    if(pool != 0){
        for(int i=0; i<numGene; ++i) delete [] pool[i];
        delete [] pool;
    }

    return 0;
}

習作やるかなーやらない気がするが

C++で「はじめての機械学習」6章

与えられたデータセットと評価値に近づくように重みとしきい値を
バックプロパゲーションで調整する3層パーセプトロン

2章と3章
4章

/**
 * バックプロパゲーションによるニューラルネットの学習
 * 使い方
 *  $./backPropagation (変数の数) (中間層のセル数) (誤差の上限値) < (学習データセットのファイル名)
 *誤差の推移や、学習結果となる結合係数などを出力します
 **/

#include <iostream>
#include <vector>
#include <cstdlib>
#include <float.h>
#include <ctime>
#include <cmath>
using namespace std;

inline void initRand()
{
    srand((unsigned int)time(NULL));
}

/**シグモイド関数**/
inline double sigmoid(double u)
{
    return 1.0 / (1.0+exp(-u));
}

/**-1.0 - 1.0の実数乱数の生成**/
inline double randDouble()
{
    return (2.0 / RAND_MAX * rand())-1.0;
}

/**中間層の重みと出力層の重みを初期化(ランダム)**/
void initWeight(const int &n, const int &numAlliance,
                double **weightAlliance,  double *weightReaction)
{
    initRand();
    for(int i=0; i<numAlliance; ++i){
        for(int j=0; j<n+1; ++j){
            weightAlliance[i][j] = randDouble();
        }
        weightReaction[i] = randDouble();
    }
    weightReaction[numAlliance] = randDouble();
}

/**学習データをdataに読み込む**/
void readData(vector< vector<double> > &data, const int &n)
{
    // [n]は評価値
    double *buffer = new double [n+1];
    while(true){
        for(int i=0; i<n+1; ++i) cin >> buffer[i];
        if(cin.eof()) break;

        vector<double> bufferVector;
        for(int i=0; i<n+1; ++i) bufferVector.push_back(buffer[i]);

        data.push_back(bufferVector);
    }
}

/**順方向の出力の計算**/
double forward(double **weightAlliance, const double *weightReaction,
                double *outAlliance, const vector<double> &dataField,
                const int &n, const int &numAlliance)
{
    double out = 0.0;
    // outAllianceの計算
    for(int i=0; i<numAlliance; ++i){
        double u = 0; // 重み付き和
        for(int j=0; j<n; ++j){
            u += dataField[j] * weightAlliance[i][j];
        }
        u -= weightAlliance[i][n]; // しきい値の処理
        outAlliance[i] = sigmoid(u);
    }
    // outの計算
    for(int i=0; i<numAlliance; ++i)
        out += outAlliance[i] * weightReaction[i];
    out -= weightReaction[numAlliance]; // しきい値の処理

    return sigmoid(out);
}

/**出力層の重みの調整**/
void learnReaction(double *weightReaction, double *outAlliance,
                    const vector<double> &dataField, double outReaction,
                    const int &n, const int &numAlliance, const int &ALPHA)
{
    double diff; // 誤差
    diff = (dataField[n] - outReaction) * outReaction * (1 - outReaction);
    // 結合荷重の調整
    for(int i=0; i<numAlliance; ++i)
        weightReaction[i] += ALPHA * outAlliance[i] * diff;
    // しきい値の調整
    weightReaction[numAlliance] += ALPHA * (-1.0) * diff;
}

/**中間層の重みの調整**/
void learnAlliance(double **weightAlliance, double *weightReaction,
                    double *outAlliance, const vector<double> &dataField, double outReaction,
                    const int &n, const int &numAlliance, const int &ALPHA)
{
    double diff; // 重みが考慮された誤差
    // i番目の中間層セルについて
    for(int i=0; i<numAlliance; ++i){
        diff = outAlliance[i] * (1 - outAlliance[i]) * weightReaction[i] *
                (dataField[n] - outReaction) * outReaction * (1 - outReaction);
        // j番目の重みを調整
        for(int j=0; j<n; ++j)
            weightAlliance[i][j] += ALPHA * dataField[j] * diff;
        weightAlliance[i][n] += ALPHA * (-1.0) * diff; // しきい値の調整
    }
}

/**結合荷重の出力**/
void printWeight(double **weightAlliance, double *weightReaction,
                    const int &n,  const int &numAlliance)
{
    for(int i=0; i<numAlliance; ++i){
        for(int j=0; j<n+1; ++j)
            cout << weightAlliance[i][j] << " ";
    }
    cout << endl;
    for(int i=0; i<numAlliance+1; ++i)
        cout << weightReaction[i];
    cout << endl;
}

int main(int argc, char *argv[])
{
    // 定数
    const int                ALPHA = 10;           // 学習係数

    // 変数
    int                      n;                    // 変数の数=入力層の数
    int                      numAlliance;          // 中間層のセル数
    double                   errorLimit;           // 誤差の上限値
    vector< vector<double> > data;                 // 学習データセット
    double                   **weightAlliance = 0; // 中間層層の重み
    double                   *weightReaction = 0;  // 出力層の重み
    double                   *outAlliance = 0;     // 中間層の出力
    double                   outReaction = 0;      // 出力層の出力
    double                   error = DBL_MAX;      // データとの誤差
    int                      count = 0;            // 繰り返し回数のカウンタ

    // 引数のチェック
    if(argc != 4){
        cerr << "使い方 $./backPropagation "
             << "(変数の数) (中間層のセル数) (誤差の上限値) "
             << "< (入力ファイル)" << endl;
        return -1;
    }
    if((n=atoi(argv[1])) < 1){
        cerr << "変数の数の値が不適切です" << endl;
        return -1;
    }
    if((numAlliance=atoi(argv[2])) < 1){
        cerr << "中間層のセル数が不適切です" << endl;
        return -1;
    }
    if((errorLimit=atof(argv[3])) == 0.0){
        cerr << "収束しない可能性があります" << endl;
    }

    // get memory
    weightAlliance = new double * [numAlliance];
    weightReaction = new double [numAlliance+1]; // [numAlliance]はしきい値
    for(int i=0; i<numAlliance; ++i) weightAlliance[i] = new double [n+1];
    outAlliance = new double [numAlliance];

    initWeight(n, numAlliance, weightAlliance, weightReaction);
    readData(data, n);

    // 学習
    while(error > errorLimit){
        error = 0.0;
        for(int i=0; i<data.size(); ++i){
            // 順方向の計算
            outReaction = forward(weightAlliance, weightReaction, outAlliance,
                                    data[i], n, numAlliance);
            // 出力層の重みの調整
            learnReaction(weightReaction, outAlliance,
                            data[i], outReaction, n, numAlliance, ALPHA);
            // 中間層の重みの調整
            learnAlliance(weightAlliance, weightReaction, outAlliance,
                            data[i], outReaction, n, numAlliance, ALPHA);
            // 誤差の積算
            error += (outReaction - data[i][n]) *
                        (outReaction - data[i][n]);
        }
        ++count;
        // 誤差の出力
        cout << count << "t" << error << endl;
    } // 学習終了

    // 結果の出力
    // 1.結合荷重の出力
    printWeight(weightAlliance, weightReaction, n, numAlliance);
    // 2.学習データに対する結果の出力
    for(int i=0; i<data.size(); ++i){
        cout << i << " ";
        for(int j=0; j<n+1; ++j)
            cout << data[i][j] << " ";
        outReaction = forward(weightAlliance, weightReaction, outAlliance,
                                data[i], n, numAlliance);
        cout << outReaction << endl;
    }

    // memory release
    for(int i=0; i<numAlliance; ++i) delete [] weightAlliance[i];
    delete [] weightAlliance;
    delete [] weightReaction;
    delete [] outAlliance;

    return 0;
}

5章はちょっと習作を思いついたのでまた今度になるかも

C++で「はじめての機械学習」4章

昨日の記事の続きです。
4章は判断木の構成で、データの属するカテゴリと各属性に対する判別結果を入力データとして与え、どの判断を用いて分類すればよいかの選択を支援するプログラムと、後半ではそれを確率探索しています。
後半はまあいいかと思ったので前半部だけ。

/**
  判断木の構成を支援するプログラム
  (判断木を構成するためには、与えられたデータセットを
  適切に分類する属性を選択しなければならない。そこで
  ある属性を選んだ場合にどのように分類されるかを計算
  する。)
  入力は標準入力から与え、出力は標準出力に出力します
  使い方:
    $./decision < (入力ファイル名) > (出力ファイル名)
  入力ファイルでは、属性とカテゴリを0/1で記述します
  出力ファイルには、分類結果を表示します
 **/

#include <iostream>
#include <vector>
#include <sstream>
#include "utf8Func.hpp"
using namespace std;

int stringToInt(const string &str)
{
    int num;
    stringstream ss;
    ss << str;
    ss >> num;
    return num;
}

/**データを読み込んでvectorに格納**/
void readData(vector< vector<int> > &data)
{
    string line;
    while(getline(cin,  line)){
        vector<string> bufferString = split_utf8(line);
        vector<int>    bufferInt;
        for(int i=0; i<bufferString.size(); ++i){
            bufferInt.push_back(stringToInt(bufferString[i]));
        }
        data.push_back(bufferInt);
    }
}

/**属性の評価**/
void evaluateProperty(const vector< vector<int> > &data, const int &i, const int &answer)
{
    int numTotal = 0;
    int numCorrect = 0;
    for(int j=0; j<data.size(); ++j){
        // 求める解答をしているデータがあれば
        if(data[j][i] == answer){
            ++numTotal;
            // 解答が正しい分類に合致していたら
            if(data[j][i] == data[j].back()) ++numCorrect;
        }
    }
    cout << numCorrect << "/" << numTotal << "t"
         << (double)numCorrect/numTotal << endl;
}

int main()
{
    // 解答番号
    const int yes = 1;
    const int no  = 0;

    vector< vector<int> > data;
    readData(data);

    // 各属性による分類
    for(int i=0; i<data[0].size()-1; ++i){
        cout << "property" <<  i+1 << endl;
        // Yesに対応した学習データの数え上げ
        cout << "Yes" << "t";
        evaluateProperty(data,  i,  yes);
        // Noに対応した学習データの数え上げ
        cout << "No" << "t";
        evaluateProperty(data,  i,  no);
        cout << endl;
    }

    return 0;
}

utf8Func.hppはこれ

#ifndef __UTF8FUNC_HPP__
#define __UTF8FUNC_HPP__

#include <vector>
#include <string>

/**utf-8のstringを一文字ずつ分割する**/
std::vector<std::string> split_utf8(const std::string& str) {
    std::vector<std::string> result;
    std::string              tmp;
    bool                     first = true;

    for (size_t i=0; i<=str.size(); ++i) {
        // 各バイトがutf-8の先頭かどうかをチェック
        if (first ||
                (i != str.size() && (str.at(i) & 0xC0) == 0x80)) {
            tmp += str.at(i);
            first = false;
            continue;
        }
        result.push_back(tmp);
        tmp.clear();
        if (i == str.size()) break;
        tmp += str.at(i);
    }
    return result;
};

#endif

5章は遺伝的アルゴリズムはいったん飛ばして、たぶん次は6章のニューラルネットワークのつもり

C++で「はじめての機械学習」2章, 3章

はじめての機械学習という機械学習の基本をC言語のソース付きで学べる書籍を読んでいるのだけど、しーぷらぷらーの僕としてはむず痒さを感じることもあるので、C++で実装をしてみることにする。

2章 最小二乗法

/**
  最小二乗法による計算式の決定
  y = a0 + a1*x の a0, a1を出力
 **/

#include <iostream>
using namespace std;

int main()
{
    double xi, yi;                                        // 入力データ
    double sxi=0, syi=0, sxiyi=0, sxi2=0; // 各項の計算結果
    double a0, a1;                                      // 係数
    int    n = 0;                                           // データの個数

    // データの入力
    cout << "データの組を入力:xi yi" << endl
         << "(ctrl+d で入力終了)" << endl;
    while (true){
        cin >> xi >> yi;
        if(cin.eof()) break;
        if(cin.good()==false){
            cout << "無効なデータです" << endl;
            cin.clear();
            cin.ignore(256, 'n');
        } else {
            sxi   += xi;
            syi   += yi;
            sxiyi += xi*yi;
            sxi2  += xi*xi;
            ++n;
        }
    }

    if(n<2){
        cout << "データは2組以上必要です" << endl;
        return -1;
    }

    // 係数の計算
    a0 = (sxi2*syi-sxiyi*sxi) / (n*sxi2-sxi*sxi);
    a1 = (n*sxiyi-sxi*syi) / (n*sxi2-sxi*sxi);

    cout << "y = " << a1 << "x + " << a0 << endl;

    return 0;
}

3章 n-gram

utf-8テキストからn-gramを生成
/**
  ngramを作成するプログラム(utf-8)
  入力は標準入力から与え、出力は標準出力に出力します
  使い方:
    $./ngram (nの値) < (入力ファイル名) > (出力ファイル名)
  入力ファイルには、テキストファイルを指定します
  出力ファイルには、ngramを出力します
 **/

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;

/**utf-8のstringを一文字ずつ分割する**/
vector<string> split_utf8(const string& str) {
    vector<string> result;
    string         tmp;
    bool           first = true;

    for (size_t i=0; i<=str.size(); ++i) {
        // 各バイトがutf-8の先頭かどうかをチェック
        if (first ||
                (i != str.size() && (str.at(i) & 0xC0) == 0x80)) {
            tmp += str.at(i);
            first = false;
            continue;
        }
        result.push_back(tmp);
        tmp.clear();
        if (i == str.size()) break;
        tmp += str.at(i);
    }
    return result;
}

/**ngramの出力**/
void printNgram(int n, const vector<string> &data)
{
    // 各文字についてその(n-1)文字後までbufferに追加
    for(int i=0; i<data.size()-n; ++i){
        string buffer;
        for(int j=i; j<i+n; ++j){
            buffer += data[j];
        }
        cout << buffer << endl;
    }
    cout << endl;
}

int main(int argc, char *argv[])
{
    int            n;       // ngramの長さ
    string         line;    // 行を格納
    vector<string> data;    // 全文章を一文字ずつ格納

    // 引数のチェック
    if(argc != 2){
        cerr << "使い方 $./ngram (nの値) "
            << "< (入力ファイル名) > (出力ファイル名)" << endl;
        return -1;
    }
    if((n=atoi(argv[1])) < 1){
        cerr << "nの値が不適切です" << endl;
        return -1;
    }

    // 一行ずつ取り出して各文字に分割
    while(getline(cin,  line)){
        vector<string> buffer = split_utf8(line);
        for(int i=0; i<buffer.size(); ++i){
            data.push_back(buffer[i]);
        }
    }

    // ngrmを生成
    printNgram(n,  data);

    return 0;
}
n-gramを集計
/**
  ngramの頻度分布を作成します
  標準入力から与え、出力は標準出力に出力します
  使い方:
    $./ranking < (入力ファイル名) > (出力ファイル名)
  入力ファイルには、ngramのファイルを指定します
  出力ファイルには、頻度分布を出力します
 **/

#include <iostream>
#include <cstdlib>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

string intToString(int num)
{
    stringstream ss;
    ss << num;
    return ss.str();
}

/**重複するngramを数えてresultに書き込む**/
map<int, string> countNgrams(const vector<string> &ngrams)
{
    map<int, string> result;                // <重複数, ngram>
    string           lastNgram = ngrams[0];
    int              numDuplicated = 1;

    // 辞書順にngramがソートされているので、
    // 一つ前のngramと同じなら重複数をインクリメントし、
    // 違えば一つ前のngramをresultに追加する
    for(int i=1; i<ngrams.size(); ++i){
        if(ngrams[i] == lastNgram) ++numDuplicated;
        else {
            // write result
            result.insert( map<int, string>::value_type(numDuplicated,  lastNgram) );
            lastNgram = ngrams[i];
            numDuplicated = 1;
        }
    }
    // write result(the last)
    result.insert( map<int, string>::value_type(numDuplicated,  lastNgram) );

    return result;
}

int main()
{
    vector<string>   ngrams;
    map<int, string> result; // <重複数, ngram>
    string           line;

    // read ngram
    while(getline(cin, line)) ngrams.push_back(line);

    sort(ngrams.begin(), ngrams.end());
    result = countNgrams(ngrams);

    // 降順で出力
    map<int, string>::iterator it = result.end();
    while(it != result.begin()){
        --it;
        cout << (*it).first << "t" << (*it).second << endl;
    }

    return 0;
}

 

ngramとかは結構おもしろい
続きはまた今度

※10月27日追記:n-gramの集計はmapだと回数が同じやつが許されないのでmultimapでやるべきでした。multimapバージョンは↓

/**
  ngramの頻度分布を作成します
  標準入力から与え、出力は標準出力に出力します
  使い方:
    $./ranking < (入力ファイル名) > (出力ファイル名)
  入力ファイルには、ngramのファイルを指定します
  出力ファイルには、頻度分布を出力します
 **/

#include <iostream>
#include <cstdlib>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

string intToString(int num)
{
    stringstream ss;
    ss << num;
    return ss.str();
}

/**重複するngramを数えてresultに書き込む**/
multimap<int, string> countNgrams(const vector<string> &ngrams)
{
    multimap<int, string> result;                // <重複数, ngram>
    string           lastNgram = ngrams[0];
    int              numDuplicated = 1;

    // 辞書順にngramがソートされているので、
    // 一つ前のngramと同じなら重複数をインクリメントし、
    // 違えば一つ前のngramをresultに追加する
    for(int i=1; i<ngrams.size(); ++i){
        if(ngrams[i] == lastNgram) ++numDuplicated;
        else {
            // write result
            result.insert( map<int, string>::value_type(numDuplicated,  lastNgram) );
            lastNgram = ngrams[i];
            numDuplicated = 1;
        }
    }
    // write result(the last)
    result.insert( map<int, string>::value_type(numDuplicated,  lastNgram) );

    return result;
}

int main()
{
    vector<string>   ngrams;
    multimap<int, string> result; // <重複数, ngram>
    string           line;

    // read ngram
    while(getline(cin, line)) ngrams.push_back(line);

    sort(ngrams.begin(), ngrams.end());
    result = countNgrams(ngrams);

    // 降順で出力
    map<int, string>::iterator it = result.end();
    while(it != result.begin()){
        --it;
        cout << (*it).first << "t" << (*it).second << endl;
    }

    return 0;
}