kakts-log

programming について調べたことを整理していきます

ソフトマックス関数についてのまとめ

前回の記事でニューラルネットワークの出力に対する活性化関数にシグモイド関数を使うことを紹介しました。 今回では、分類問題をニューラルネットワークをつかって解く際に、活性化関数としてよく使われるソフトマックス関数についてまとめます。

ソフトマックス関数とは

数式で表すと以下のとおりになります。

 {\large y_k = \frac {exp(a_k)} {\sum_{i=0}^n exp(a_i)}}

ソフトマックス関数の利点と特徴

ソフトマックス関数の特徴としては、大きく2つにわけられます。
- 出力の各要素の値域が  0 \leq y_i  \leq 1 となる
- 出力の総和が1となる

この2つのうち、2番目がニューラルネットワークで使う上で重要となります。 なぜならば、出力値の各要素の総和が1になるので、出力層の各ユニットの値を確率として解釈することができます。
これにより、問題に対して確率的アプローチを取れるようになります。

ソフトマックス関数の注意点

上記のように、ニューラルネットワークでソフトマックス関数を使うことで、出力層の各ユニットの値を確率として表現でき、統計的アプローチが取れる様になるのですが、
コンピュータ上でソフトマックス関数を使う際に注意点があります。
注意点は、ソフトマックス関数で  exp(a_i)を使うのですが、指数関数は入力値が増えると、出力の増加率も大きいので、値によっては桁数がたりずにオーバーフローしてしまいます。

どう解決するか

上記のオーバーフローの問題を解決するために、ソフトマックス関数の数式を、logと指数の性質を利用して変形していきます。

 {\large y_k = \frac {exp(a_k)} {\sum_{i=0}^n exp(a_i)}} (1)

分母と分子に定数Cをかけて
 {\large = \frac {Cexp(a_k)} {C \sum_{i=0}^n exp(a_i)}} (2)

 Cexp(x) = exp(x + logC) なので

 {\large = \frac {exp(a_k + logC)} {\sum_{i=0}^n exp(a_i + logC)}} (3)

 logC = C1として、さらに別の定数を用いて
 {\large = \frac {exp(a_k + C1)} {\sum_{i=0}^n exp(a_i + C1)}} (4)

と表すことができる。 ニューラルネットワークにおいては、上記の C1は入力信号の中で最大の値を用いるのが一般的です。
正負のどちらでも問題ないので、最大値を取得した上で、それを引くことでオーバーフローを回避できます。

import numpy as np
a = np.array([0.3, 2.9, 4.0])

def softmax_imp(a):
    # 入力値の中で最大値を取得
    c = np.max(a)
    # オーバーフロー対策として、最大値cを引く。こうすることで値が小さくなる
    exp_a = np.exp(a - c);
    sum_exp_a = np.sum(exp_a)

    y = exp_a / sum_exp_a
    return y

print(softmax_imp(a))

numpyを使えば、配列に対して最大値を求めたり、各要素に対して同じ処理を行うことが容易にできるので、かなり楽にかけます。

php mysql でコネクションプールを貼る

phpからmysqlを使う際に、拡張モジュールであるmysqliを使って mysqlサーバとの接続、クエリ実行を行う場合 コネクションプールを貼る事ができます。 公式ドキュメントによると、phpでのコネクションプールはphp5.3から対応されています。

PHP: mysqli 拡張モジュールでの持続的接続 - Manual

コネクションプールを貼ることによって、クライアント接続毎に新たにコネクションを張り直す必要がなく、再利用することができます。

実際には、mysqliのインスタンス生成時のホスト名の先頭に 「p:」をつければ自動的にやってくれるようです。

  $mysqli = new mysqli('p:127.0.0.1, 'mysql_user', 'mysql_pass', 'mysql_db_name');

Node.js clusterモジュールについて

シングルスレッドで動作するNode.jsにおいて、マルチコアCPUを持っているマシンの能力を最大限引き出すために、
複数のワーカープロセスを起動して処理を分散させたいといったニーズがあると思います。
そのときに重要なclusterモジュールについて、いつも業務で使っていますが、さらなる理解のため、整理してみます。
この記事は、Node.jsバージョンv6.x系を前提とした話となります。

clusterモジュール

clusterモジュールについて、大まかな処理の流れは、ドキュメントやNode.jsユーザグループのブログ(Node.js v0.6時のもので古いです)が非常に参考になります。
blog.nodejs.jp

clusterモジュールによるプロセス間通信には2つの方法があり、それぞれ紹介していきます。

マスタープロセスによるロードバランシング

この方法では、マスタープロセスは指定したポートで待ち受けて、新たなコネクションを受け付けます。
リクエストがあるたびに、マスタープロセスはラウンドロビン方式でワーカープロセスに処理を委譲します。
この方法の場合、リクエストが来るたびにマスタープロセスがロードバランサーとして仕事をするために、同時アクセス数が増加したときに、サーバ全体のスループットが、
マスタープロセスの上限に依存します。
この方法は、上記の問題から、webサーバにおいてあまり利用されることがなく、複数マシン間で処理を分散する場合のリバースプロキシとして用いられることが多いです。

カーネルによるロードバランシング (v0.11.2以降デフォルト)

マスタープロセスからソケットを作成し、ワーカプロセスに接続済みソケットを渡してクライアントとワーカプロセス間で接続を行う方法です。
このアプローチはNode.js v0.11.2からUnix系プラットフォーム(windows以外のこと)でデフォルトになりました。 理論的には、この方法が最も良いパフォーマンスを提供します。

clusterモジュールを実際に使ってみる

実際にclusterモジュールを使って動かしてみるのが理解しやすいので、公式ドキュメントのサンプルを参考にwebサーバを作ってみました。

// clusterテスト用
// master workerプロセス共に、このプログラムの上から処理が走る

"use strict";

const cluster = require('cluster');
const http = require('http');

if (cluster.isMaster) {
  // masterプロセスの場合の処理

  // Keep track of http requests
  var numReqs = 0;
  setInterval(() => {
    console.log('numReqs =', numReqs);
  }, 1000);

  // Count requests
  function messageHandler(msg) {
    if (msg.cmd && msg.cmd == 'notifyRequest') {
      numReqs += 1;
    }
  }

  // Start workers and listen for messages containing notifyRequest
  // cpu数を取得し、cpu数分だけ、ワーカープロセスをforkする
  const numCPUs = require('os').cpus().length;
  for (var i = 0; i < numCPUs; i++) {
    cluster.fork();
  }

  Object.keys(cluster.workers).forEach((id) => {
    // クラスター毎にメッセージハンドラー(リクエスト数カウント処理)を設定する
    // messageイベントを受信したときに発火する
    cluster.workers[id].on('message', messageHandler);
  });

  cluster.on('exit', (worker, code, signal) => {
    console.log('worker %d died (%s). restarting...', worker.process.pid, signal || code);
  });
} else {
  // workerプロセスの処理

  // Worker processes have a http server
  http.Server((req, res) => {
    console.error('---Request header.', req.headers)
    res.writeHead(200);
    res.end('hello world \n');

    // notify master about the requests
    process.send({
      cmd: 'notifyRequest'
    });
  }).listen(8000);
}

マスタープロセスでの処理

マスター・ワーカープロセスともに上記のコードを上から実行していくのですが、それぞれのプロセスにおいて cluster.isMasterという値を持っており、 この値でマスター・ワーカープロセスを判断しています。

マスタープロセスの場合、CPUコア数分のワーカープロセスをforkする処理をおこなっており、それぞれのワーカープロセスに対して、
プロセス間メッセージを受信したときのmessageイベントと、ワーカープロセスが死んだときのexitイベントに対するハンドラ関数をそれぞれセットしています。

  // masterプロセスの場合の処理

  // Keep track of http requests
  var numReqs = 0;
  setInterval(() => {
    console.log('numReqs =', numReqs);
  }, 1000);

  // Count requests
  function messageHandler(msg) {
    if (msg.cmd && msg.cmd == 'notifyRequest') {
      numReqs += 1;
    }
  }

  // Start workers and listen for messages containing notifyRequest
  // cpu数を取得し、cpu数分だけ、ワーカープロセスをforkする
  const numCPUs = require('os').cpus().length;
  for (var i = 0; i < numCPUs; i++) {
    cluster.fork();
  }

  Object.keys(cluster.workers).forEach((id) => {
    // クラスター毎にメッセージハンドラー(リクエスト数カウント処理)を設定する
    // messageイベントを受信したときに発火する
    cluster.workers[id].on('message', messageHandler);
  });

  cluster.on('exit', (worker, code, signal) => {
    console.log('worker %d died (%s). restarting...', worker.process.pid, signal || code);
  });

ワーカープロセスでの処理

ワーカープロセスでは、8000番ポートでhttpリクエストを受付、hello worldを返すhttpサーバの処理を行っています。 このプログラムでは、リクエストを受け付けた際に、 process.sendで、マスタープロセスに対してリクエストを受け付けたことを通知しています。
マスタープロセスでは、このnotifyRequestコマンドを受け取ると、リクエストカウントをインクリメントして、1000ミリ秒毎にリクエストカウントを表示させています。

  // workerプロセスの処理

  // Worker processes have a http server
  http.Server((req, res) => {
    console.error('---Request header.', req.headers)
    res.writeHead(200);
    res.end('hello world \n');

    // notify master about the requests
    process.send({
      cmd: 'notifyRequest'
    });
  }).listen(8000);

サーバの起動

実際にサーバを起動してみて、挙動を確認します。
先程書いたプログラムを/Users/testuser/Documents/nodejs-sandbox配下のcluster-test.jsに作成し、ターミナルで実行します。

$ node cluster-test.js
numReqs = 0     // 1000ミリ秒毎にリクエストカウント表示
numReqs = 0

これでlocalhostの8000番ポートでリクエストを待ち受けている状態になりました。 ためしに、起動されているnodeプロセスを確認すると、しっかりとCPUコア数分(8コア)ワーカープロセスが立ち上がっていることが確認できます。

testuser     81767   0.0  0.1  3050252  21320 s003  S+    2:31AM   0:00.15 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81766   0.0  0.1  3068684  21408 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81765   0.0  0.1  3041036  20876 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81764   0.0  0.1  3068684  21580 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81763   0.0  0.1  3049228  20980 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81762   0.0  0.1  3068684  21652 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81761   0.0  0.1  3068684  21604 s003  S+    2:31AM   0:00.15 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81760   0.0  0.1  3068684  21464 s003  S+    2:31AM   0:00.16 /Users/testuser/.nodebrew/node/v6.9.2/bin/node /Users/testuser/Documents/nodejs-sandbox/cluster-test.js
testuser     81759   0.0  0.1  3059468  21468 s003  S+    2:31AM   0:00.13 node cluster-test.js

この状態のまま、クライアント用にターミナルをもう1つ立ち上げ、curlでhttpリクエストを送るとレスポンスが返ってくるのを確認できます。

$ curl localhost:8000
hello world 

さらに、先程から起動していたサーバ側のターミナルには、リクエストカウントが1増えていることが確認できます。

numReqs = 0
---Request header. { 'user-agent': 'curl/7.37.0',
  host: 'localhost:8000',
  accept: '*/*' }
numReqs = 1

以上のように、clusterモジュールを使って、複数プロセスでwebサーバを立ち上げることができました。
clusterはNode.jsにおける負荷分散で欠かせないものなのでしっかりと理解することが重要かと思います。

シェルソートについて

シェルソートは前回紹介した挿入ソートの改良版アルゴリズムです。
挿入ソートは一般的に、配列がほとんどソートされた状態で効率的に機能するもので、それ以外の場合では大きくパフォーマンスが落ちるのですが
シェルソートではその欠点を補う仕組みになっています。

計算量は以下の通りです。
- 最悪時計算量 アルゴリズムの間隔関数に依存するが、  O(nlog^2n)
- 最良時計算量  O(n)
- 空間計算量  O(1)

アルゴリズムpythonで書いてみると、以下の通りになります。

import sys

# シェルソート
def shellSort(aList):
    subListCount = len(aList) // 2
    while subListCount > 0:
        for pos in range(subListCount):
            doGapInsertionSort(aList, pos, subListCount)

        print("After increments of size", subListCount);
        print("The list is", aList);

        subListCount = subListCount // 2

# 挿入ソート ギャップあり版
def doGapInsertionSort(aList, startPos, gap):
    for i in range(startPos + gap, len(aList), gap):
        currentVal = aList[i]
        position = i
        while position >= gap and aList[position - gap] > currentVal:
            aList[position] = aList[position - gap]
            position = position - gap

        aList[position] = currentVal

a = [int(a_temp) for a_temp in input().strip().split(' ')]

#シェルソート実行
shellSort(a)
print(a)

シェルソートと挿入ソートの違い

挿入ソートでは、隣接要素間で比較を行い、2つの要素が逆順になっていたら値を交換していく処理になります。
それと違って、シェルソートでは、離れた要素間の比較と交換を実行できるようにし、アルゴリズムの最終ステップまで隣接要素を比較しないようになります。
挿入ソートでは1だけ離れたものを比較し、シェルソートではhだけ離れた要素を比較します。 それによって、ある程度値にばらつきのある配列をソートする際に、並び替え回数が減らせるため処理速度が改善します。

シェルソート分析

一般的にシェルソートは大規模なリストに対しては最適でなく、1000〜10000までの中規模なアルゴリズムにおいて最も効率が良いと言われています。  O(n^2)アルゴリズムのなかでは最も高速となります。

シェルソートの欠点

欠点としては、アルゴリズムが複雑であり、マージソートヒープソートクイックソートと比べたときに効率的でない点があげられます。

挿入ソートについて

先月、Javascript advent calendarで、v8の配列ソートアルゴリズムにおいて、
配列の要素数に応じて挿入ソートとクイックソートを使い分けているという記事を書きました。
v8における配列ソートについて - kakts-log

今回は、挿入ソートについてまとめてみたいと思います。

挿入ソート

挿入ソートとは、ソートアルゴリズムの一種で、ある値をソート済み配列に追加するときに有効な手法です。
in-placeで、配列を書き換えながら行うので、空間計算量は O(1)ですむためメモリ効率がよく、実装が簡単です。 計算量は以下の通りになっています。

最悪計算時間 О(n^2)
最良計算時間 O(n)
平均計算時間 О(n^2)

pythonで書いてみると、以下の通りになります。

import sys

# スペース区切りで配列要素を入力
a = [int(a_temp) for a_temp in input().strip().split(' ')]

for pos in range(1, len(a)):
    # 交換対象の値を保持
    value = a[pos]
    # 配列の要素数 - 1 だけinsertがはしる
    i = pos - 1
    while i >= 0 and a[i] > value:
        # 前方の要素のほうが大きい場合は1つ後ろに値をずらしていく
        a[i + 1] = a[i]
        i = i - 1

    #チェックが終わったら 値を適切な位置に代入する
    a[i + 1] = value

print(a)

使うべき状況

  • 配列の要素数が少ない時(20以下くらい) どれくらいの値をもって”少ない”とするかはマシンスペックやプログラミング言語によって異なりますが、だいたい20以下が望ましいようです。
    Javascript エンジンのv8においては10以下のときに挿入ソートを採用しています。
  • 配列がほぼソートされている状態の時 配列の要素が、ほぼソートされていて、後ろの数要素だけソートされていない状態の場合、挿入ソートのパフォーマンスは非常に良くなります。
    理由としては、配列の前方のほうがソートされているため、比較回数を劇的に減らせるためです。
  • 重複する要素が存在する場合
    重複する要素がある場合、データスワッピングの回数が減るため、計算量が減ります。

挿入ソートの利点

  • ソート時に用いるメモリ量が少ない ソートにおいて、与えられた配列を直接書き換えていく仕組みなので、配列の要素以外にメモリを使う必要がありません。

計算量の分析

ベストケースの場合、n要素数の配列の場合計算量は O(n)と、線形時間でソートを行うことができます。
しかし、この状況の配列をソートする可能性はほぼないため、インパクトとしては小さいですが、挿入ソートは、
comparison-basedなソートアルゴリズムの中で、唯一、ベストケースの振る舞いを持つソートアルゴリズムとなります。
そして、ソートする配列が重複なしで、ランダムに要素が並べられている場合は計算量が最悪になります。

平均、最悪な場合の計算量は、どちらも O(n^2)となります。

他のソートアルゴリズムとの比較

素数が少ない、またはほぼソート済みの配列の場合、クイックソートマージソートよりも勝るので、 要素数が少ないときは挿入ソート、それ以外の場合はクイックソートマージソートを使うケースが多い。
また、挿入ソートの改良版としてシェルソートというものがある。

パーセプトロンとニューラルネットワークの違い

正月休みを利用して Deep Learningに関して勉強をしています。
以前、パターン認識系の本を読んでいたのですが、実装をせずに理論だけ学んでいて、いまいち自分の中で理解が進まず挫折していました。 下記に紹介する「ゼロから作るDeep Learning ――Pythonで学ぶディープラーニングの理論と実装」では、python3系を用いてパーセプトロンから丁寧に実装して理解をすすめることができて
非常に面白いです。
現在勉強中のパーセプトロンニューラルネットワークについて、箇条書きですが簡単にまとめていきます。

パーセプトロンニューラルネットワークの違い

パーセプトロン

f:id:kakts:20170102000614p:plain
ある入力 x_1 x_2があり、それぞれの入力に対する重みと、バイアスbによって出力yが変わる。

パーセプトロンを数式で表すと以下の通りになる
f:id:kakts:20170102005157p:plain
バイアスとは、ニューロンの発火のしやすさをコントロールし、各ノードの重みは、ノードの重要性をコントロールする.
yは入力信号 b,  x_1,  x_2 の総和 h(x) = b + w_1 * b_1 + w_2 * b_2の値で決まる.
この総和関数 h(x)は一般的にステップ関数と呼ばれ、x = 0の点で非連続な関数である。

ニューラルネットワーク

パーセプトロンの考え方を応用したもので、入力層から来たデータが中間層を通過し、最後に出力層で求める出力を表現する。
中間層に関しては、実装に応じて複数の層にまたがる場合がある。
f:id:kakts:20161231163712p:plain

出力層の値は、下記で表されるシグモイド関数(Sigmoid Function)*1できまる。
 h(x) = \frac {1} {1 + exp(-x)}
f:id:kakts:20170102011637p:plain

シグモイド関数は最大が1,最小が0に収束していき、ステップ関数とは違って連続関数である。

パーセプトロンニューラルネットワークの違い

パーセプトロンニューラルネットワークの違いは、
入力に対して最終的な出力を行う際の関数(Activation-Functionと呼ばれる)が異なることである。

ステップ関数とシグモイド関数の違い

パーセプトロンにおいてはx = 0において非連続なステップ関数で0か1の2値しか返さない。
それに対してニューラルネットワークにおいては連続関数であるシグモイド関数を用いている。 シグモイド関数は入力に対して連続的に出力が変化し、この特徴がニューラルネットワークにおいて重要な意味を持つ。

ステップ関数とシグモイド関数の共通点

両者の共通点は、どちらも出力の値を 0から1の間の範囲で表せること、そしてどちらも非線形関数であることが共通点。 そしてニューラルネットワークにおいては、活性化関数に非線型関数を使う必要がある。

ニューラルネットワークの活性化関数に非線型関数を使う理由

活性化関数に、線形な関数を使った場合、中間層の無いネットワークで表現できてしまうので、層を深くすることの意味がなくなってしまう。
たとえば 3層のネットワークを構築したとして、 活性化関数を  h(x) = a * xとすると、  y(x) = h(h(h(x))) → y(x) = a * a * a * x となり、
中間層のないネットワークで表現できてしまうためである。

ニューラルネットワークは何を解決するか

パーセプトロンの重み設定(期待する入力と出力をみたすための重みを決める作業)を自動化する 従来のパーセプトロンは、入力に対して望みの出力を得るために、重みを設定する必要があり、非常に手間のかかる作業だった。
ニューラルネットワークは、与えられたデータから自動で学習し、パラメータを自動的に設定できる。

ニューラルネットワークでどういう問題を解くか

ニューラルネットワークは、主に2つの問題に対して有効である - 分類問題
与えられたデータがどのクラスに属するか判定する - 回帰問題 ある入力データから、(連続的な)数値の予測を行う

上記2種類の問題では、それぞれ、ニューラルネットワークの出力層で用いる活性化関数が異なる。
回帰問題では恒等関数、分類問題ではソフトマックス関数が一般的に使われている。
恒等関数とは、与えられた入力をそのまま出力するもので、出力に変化はない。
一方、ソフトマックス関数は、以下の数式で表すことができる。
f:id:kakts:20170102174343p:plain

出力層が全部でn個ある場合に、k番目の出力 y_kを表す式である。

C socket accept時に accept: Socket operation on non-socket が出るときの対処法

最近、tcpソケットまわりの知識を身につけたいとおもい、
ネットワークプログラミングに関する技術書を購入して勉強をはじめました。

Linuxネットワークプログラミングバイブル

Linuxネットワークプログラミングバイブル

この本の内容を参考に、socketサーバをC言語で書いているのですが、socketのaccept時でエラーが出ていてかなりハマってしまった。

// accept loop
// 並列処理を行っていないので、受け付けた後、1つのクライアントの送受信処理が終わるまで他の受付ができない。
void accept_loop(int soc) {
  char hbuf[NI_MAXHOST], sbuf[NI_MAXSERV];
  struct sockaddr_storage from;
  int acc;
  socklen_t len;


  for (;;) {
    len = (socklen_t) sizeof(from);

    // waiting connection
    // 1つも待ちがない状態だとaccept()実行でブロックする

    // ここでsocが0になっている
    acc = accept(soc, (struct sockaddr *) &from, &len);
    // 以下略...
    }
  }
}

クライアントからのソケット接続を待ち受ける箇所で accept()を呼んでいる箇所で
accept: Socket operation on non-socket
エラーが出ていてクライアントからのtelnetでのポート接続ができるがメッセージのやりとりができない状態となっていました。 エラーコードを確認すると38 になっていて、accept()の第1引数で渡すint socの値がソケットでない場合に起きるものです。

ENOTSOCK 38  ※Socket operation on non-socket   ソケットではない

socの値を確認してみると、soc が0になっていたので、socの値を代入している箇所をチェック。
代入箇所で細かいバグがあったので直したら解決した。

まとめ

ソケットサーバ起動時に accept: Socket operation on non-socket エラーが出たとき

accept*1の第1引数のsocketディスクリプタの値が異常値になっているため、 socketディスクリプタの作成*2に失敗している可能性がある