shonen.hateblo.jp

やったこと,しらべたことを書く.

多層ニューラルネットワークのフルスクラッチ実装(コードと検証のみ)

概要

非線形分類器も学習可能な多層ニューラルネットワークフルスクラッチで実装した.

役に立たないだとか車輪の再発明だとか言われがちですが,やっぱり面白いですよね.

自分が持っていた誤解

各ノード(ニューロン)が学習パラメータを保持していると思っていた.

次に記述する構造体の通り,各エッジに学習パラメータを保持させる方が自然だと感じた. *1

構造体

以下のコードはDAGを満たしていないニューラルネットワークは学習できない(無限再帰が発生する).

大まかなアルゴリズムについては解説しないので,参考資料を読んでください.

実装に関する解説・使い方はコードの下でします.

コード

pythonで書こうと思っていましたが,行列演算がそれほど無かったのでC++にしました.

using namespace std;

struct Perceptrons {

    static inline double sigmoid(double x) { return 1.0 / (1.0 + exp(-x)); }

    struct Edge {
        int src, dest;
        double weight;
        Edge(int src, int dest, double w = 0) :src(src), dest(dest), weight(w) { }
    };

    struct Node {
        vector<int> edges_in, edges_out;
        double last_output;
    };

    vector<Edge> edges;
    vector<Node> nodes;
    vector<int> inputids, outputids, oneids;

    Perceptrons(int nodesize = 0) {
        nodes.resize(nodesize);
    }

    inline void connect(int begin, int end, double weight = 0) {
        int i = edges.size();
        edges.emplace_back(begin, end, weight);
        nodes[begin].edges_out.push_back(i);
        nodes[end].edges_in.push_back(i);
    }

    // todo: set method: inputids, outputids

    vector<double> predict(const vector<double>& input) {

        vector<int> visited(nodes.size(), false);

        // dfs
        function<double(int)> dfs = [&](int idx) {
            Node& node = nodes[idx];
            if (visited[idx])
                return node.last_output;
            double val = 0.0;
            for (int i : node.edges_in)
                val += edges[i].weight*dfs(edges[i].src);
            visited[idx] = true;
            return node.last_output = sigmoid(val);
        };

        // initialize(input)
        for (int i = 0; i < input.size(); ++i) {
            Node& node = nodes[inputids[i]];
            node.last_output = input[i];
            visited[inputids[i]] = true;
        }
        for (int id : oneids) {
            visited[id] = true;
            nodes[id].last_output = 1.0;
        }

        // solve
        vector<double> output(outputids.size());
        for (int i = 0; i < outputids.size(); ++i)
            output[i] = dfs(outputids[i]);
        
        return output;
    }

    void train(const vector<double>& output) {

        vector<int> visited(nodes.size(), false);
        vector<double> carry(nodes.size());

        // dfs
        function<double(int)> dfs = [&](int idx) {
            Node& node = nodes[idx];
            if (visited[idx])
                return carry[idx];

            double val = 0.0;
            for (int i : node.edges_out)
                val += edges[i].weight*dfs(edges[i].dest);
            val *= (1.0 - node.last_output)*node.last_output;

            visited[idx] = true;
            return carry[idx] = val;
        };

        // initialize(solved output)
        for (int i = 0; i < outputids.size(); ++i) {
            int id = outputids[i];
            visited[id] = true;
            carry[id] = (nodes[id].last_output - output[i]);
        }

        // calculate
        for (int id : inputids)
            dfs(id);
        for (int id : oneids)
            dfs(id);

        // update
        for (auto& edge : edges)
            edge.weight -= nodes[edge.src].last_output*carry[edge.dest];
    }
};

簡単な実装に関する解説

この構造体を使う手順

  1. ノード数を指定して構築.
  2. 入力用・出力用・定数項として使うノードを指定.
  3. 辺を張る.
  4. 学習パート(次のブロックを必要回数繰り返す)
    1. 学習用データをpredictする.
    2. 直前のデータに対応する正解データを提示して,trainする.
  5. 完成!

Edge, Node

  • 上でも説明した通り,学習に関する重み付けのパラメータは辺が持つ.
  • 学習パートでは,各ノードが出力した値を使うので,node.last_outputで保持する.

predict, train

  • 情報がinputからoutputへ流れるか,outputからinputへ流れるかの違い.ほとんど似た実装になっている.
  • メモ化再帰動的計画法を用いた実装.
    • あるノードの出力を得たいとする.
    • 出力が計算済みであれば,再び計算することなくその結果を返す(メモ化).
    • 出力を計算するためには,前段階のノードの出力が必要
    • 前段階のノードの出力を問い合わせて(再帰),計算して返す.

単一ニューロンによる線形分類器

線形分類器であれば,ニューロンがたった1つでも実現可能.まずはこれを構築してみる.

テストデータは二次元で,それぞれの要素は[0.0,1.0]の範囲の一様分布乱数.

正解となる分類関数は(v[0] + v[1] > 1.0) ? 1 : 0とした.線形.

構築するニューラルネットワークは,次の図のような構造である.

f:id:m_buyoh:20180419231924p:plain:w300

mt19937_64 randdev(8901016);
template<typename T> inline T rand(T l, T h) { return uniform_int_distribution<T>(l, h)(randdev); }
template<> inline double rand<double>(double l, double h) { return uniform_real_distribution<double>(l, h)(randdev); }
template<> inline float rand<float>(float l, float h) { return uniform_real_distribution<float>(l, h)(randdev); }

int main() {

    // 学習用データの作成
    const int N = 100;
    vector<vector<double>> dataset;
    auto teacher = [](const vector<double>& v)->int {return v[0] + v[1] > 1.0; }; // 正解となる分類関数

    dataset.reserve(N);
    for (int i = 0; i < N; ++i)
        dataset.push_back({ rand(0.0, 1.0), rand(0.0, 1.0) });


    // ニューラルネットワーク
    Perceptrons perc(4);

    // 単細胞ニューラルネットワーク
    perc.inputids = { 0,1 };
    perc.oneids = { 2 };
    perc.outputids = { 3 };
    perc.connect(0, 3);
    perc.connect(1, 3);
    perc.connect(2, 3);


    // 学習
    for (int loopcnt = 0; loopcnt < 50; ++loopcnt) {
        for (const auto& data : dataset) {
            perc.predict(data);
            perc.train(vector<double>{(double)teacher(data)});
        }
    }

    // 検証
    const int M = 100;
    int correct = 0;
    for (int i = 0; i < M; ++i) {
        vector<double> data = { rand(0.0,1.0), rand(0.0, 1.0) };
        correct += ((perc.predict(data)[0] >= 0.5) == teacher(data));
    }

    cout << "correct:" << correct << endl;

    string pause; cin >> pause;

    return 0;
}

上のコードを実行すると正解数が出力されるが,良い正答率が得られるはず.

中間層を含むニューラルネットワークによる分類器実装

正解となる分類関数をabs(v[0] + v[1] - 1) < 0.5 ? 1 : 0とする.この分類関数は非線形であり,単一ニューロンでは近似出来ない.

そこで,次のような中間層を含むニューラルネットワークを構築する.

f:id:m_buyoh:20180419231908p:plain:w400

また,ニューラルネットワークを構築する際,辺の重みを乱数で初期化するようにした.*2

int main() {

    const int N = 200;
    vector<vector<double>> dataset;
    // auto teacher = [](const vector<double>& v)->int {return abs(v[0] - 0.5) + abs(v[1] - 0.5) > 0.5; };
    auto teacher = [](const vector<double>& v)->int {return abs(v[0] + v[1] - 1) < 0.5; };

    dataset.reserve(N);
    for (int i = 0; i < N; ++i)
        dataset.push_back({ rand(0.0, 1.0), rand(0.0, 1.0) });


    Perceptrons perc(9);

    // 単細胞パーセプトロン
    perc.inputids = { 0,1 };
    perc.oneids = { 2, 7 };
    perc.outputids = { 8 };
    perc.connect(0, 3, rand(0.0, 1.0));
    perc.connect(1, 3, rand(0.0, 1.0));
    perc.connect(2, 3, rand(0.0, 1.0));
    perc.connect(0, 4, rand(0.0, 1.0));
    perc.connect(1, 4, rand(0.0, 1.0));
    perc.connect(2, 4, rand(0.0, 1.0));
    perc.connect(0, 5, rand(0.0, 1.0));
    perc.connect(1, 5, rand(0.0, 1.0));
    perc.connect(2, 5, rand(0.0, 1.0));
    perc.connect(0, 6, rand(0.0, 1.0));
    perc.connect(1, 6, rand(0.0, 1.0));
    perc.connect(2, 6, rand(0.0, 1.0));
    perc.connect(3, 8, rand(0.0, 1.0));
    perc.connect(4, 8, rand(0.0, 1.0));
    perc.connect(5, 8, rand(0.0, 1.0));
    perc.connect(6, 8, rand(0.0, 1.0));
    perc.connect(7, 8, rand(0.0, 1.0));


    for (int loopcnt = 0; loopcnt < 50; ++loopcnt) {
        for (const auto& data : dataset) {
            perc.predict(data);
            perc.train(vector<double>{(double)teacher(data)});
        }
    }


    int const M = 100;
    int correct = 0;
    for (int i = 0; i < M; ++i) {
        vector<double> data = { rand(0.0,1.0), rand(0.0, 1.0) };
        correct += ((perc.predict(data)[0] >= 0.5) == teacher(data));
    }

    cout << "correct:" << correct << endl;

    string pause; cin >> pause;

    return 0;
}

実行してみると,良い結果が得られているのが分かると思う.

…が,正解数だけ見ても不信感しか無いので,テストデータと分類結果をプロットした.青が0,オレンジが1に分類された点である.

f:id:m_buyoh:20180419230111p:plain

分類関数はabs(v[0] + v[1] - 1) < 0.5 ? 1 : 0なので,だいたい模倣できているように見える.

#

別の分類関数でも試してみた.abs(v[0] - 0.5) + abs(v[1] - 0.5) > 0.5 ? 1 : 0とする.

実行してみると少し精度が落ちた(84/100)が,プロットしてみると模倣は出来ている様子.

f:id:m_buyoh:20180419230837p:plain

参考資料

*1:厳密には「ニューロンは1つのノードとそのノードを終点とする重み付き有向辺から構成される」という解釈が正しそう.

*2:これをしないと,複数の同一層のノード・辺が全て同じ挙動をしてしまうため.