Page List

Search on the blog

2016年9月18日日曜日

木の半径、直径、中心、重心

最近よく見聞きする木の用語を整理しておく。

離心数(eccentricity)
節点vから最も離れた節点をwとする。
このときパス(v, w)の長さをvの離心数と呼ぶ。
記号で表すときは、ε(v)と書く。

木の半径(radius)
離心数の最小値。つまりmin_(v ∈ V) ε(v)。
木の中心から最も遠い節点までの距離とも言える。

木の直径(diameter)
離心数の最大値。つまりmax_(v ∈ V) ε(v)。
最も遠い2点間の距離と言える。

木の中心(center)
離心数が最小の節点。
最も離れたところにある節点までの距離が最小の節点なので、なんとなくグラフの中心にありそうなイメージと合致する。

木の重心(centroid)
節点vを根とした木を考える。
vの直接の子以下の最大部分木の節点数が最小となる場合、vを木の重心と呼ぶ。
木を再帰的に分割して何か処理をしたい場合、木の重心で分割すると偏りが少ないため再帰の深さが浅くなるというメリットがある。

以下に木のサンプル図を示す。
節点の中の数字は離心数を表す。木の半径 = 2、直径は4である。
また中心は1つ、重心は2つ存在する。


2016年8月28日日曜日

信頼区間付きの線形回帰予測

 pythonで線形回帰の信頼区間付きpredictionをしたかったけど、sklearnには該当する機能が無かった。Gradient Boosting Regressionだと出来るのだけど[2]、単純なLeast Squareでやりたかったのでどうやるのか調べていたら、stasmodelsを使えばいい[1]らしい。

サンプルソース

import numpy as np
import statsmodels.api as sm
from statsmodels.sandbox.regression.predstd import wls_prediction_std
import matplotlib.pyplot as plt

np.random.seed(1234)
nsample = 30
x1 = np.linspace(0, 20, nsample)
x = np.column_stack((x1, x1**0.5))
x = sm.add_constant(x)
beta = [1, 0.5, 0.5]
y = np.dot(x, beta) + np.random.normal(size=nsample)
res = sm.OLS(y, x).fit()
prstd, iv_l, iv_u = wls_prediction_std(res)

plt.plot(x1, y, 'o', label="Data")
plt.plot(x1, res.fittedvalues, 'r--')
plt.plot(x1, iv_u, 'r--', label="Ordinary Least Squares")
plt.plot(x1, iv_l, 'r--')
plt.legend(loc="best");
plt.show()

wls_prediction_stdは、学習データに対する予測値の有意水準5%信頼区間を返してくれる。有意水準は引数alphaで自由に設定できる。また、学習データ以外のデータに対する予測を行いたい場合は、引数exogにデータを渡せばよい[3]。

結果

参考
[1] https://www.reddit.com/r/MachineLearning/comments/3raivl/code_to_calculate_confidence_interval_for_linear/
[2] http://scikit-learn.org/stable/auto_examples/ensemble/plot_gradient_boosting_quantile.html
[3] https://github.com/statsmodels/statsmodels/blob/master/statsmodels/sandbox/regression/predstd.py

2016年8月22日月曜日

INETドメインとUNIXドメイン

ソケットには、INETドメインソケットとUNIXドメインソケットが存在する。

INETドメイン
異なるマシンで動作しているプロセス間の通信を行うためのソケット。

UNIXドメイン
同じマシン内で動作しているプロセス間の通信を行うためのソケット。
INETドメインソケットでもループバックアドレスを利用することで同一マシン内の通信はできるが、UNIXドメインソケットの方が高速である。

INETドメインソケットのサンプル

inet_server.py

bindするときにIP、PORTを指定する。

import socket

IP = '127.0.0.1'
PORT = 5005
BUFFER_SIZE = 1024

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind((IP, PORT))
s.listen(1)
conn, addr = s.accept()
while 1:
 data = conn.recv(BUFFER_SIZE)
 if not data:
  break
 msg = data.decode('utf-8')
 msg = msg[::-1]
 conn.send(msg.encode('utf-8'))
conn.close() 

inet_client.py

import socket

IP = '127.0.0.1'
PORT = 5005
BUFFER_SIZE = 1024

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((IP, PORT))
msg = "ABCDEFG"
s.send(msg.encode('utf-8'))
data = s.recv(BUFFER_SIZE)
print (data.decode('utf-8'))
s.close()

プロセスIDからINETドメインソケットを調べる。
$ ps -ef | grep python
  501  9165  2011   0 11:51PM ttys000    0:00.04 python inet_server.py
$ lsof -n -i -P | grep 9165
python3.5  9165 kenjih    3u  IPv4 0xf27949601620cf2b      0t0  TCP 127.0.0.1:5005 (LISTEN)

UNIXドメインソケットのサンプル

unix_server.py

bindするときにファイル名を指定する。
UNIXドメインソケットでは、アドレス・名前空間としてファイルシステムを使用する。

import socket
import os

PATH = '/tmp/sample.sock'
BUFFER_SIZE = 1024

s = socket.socket(socket.AF_UNIX, socket.SOCK_STREAM)
os.unlink(PATH)
s.bind(PATH)
s.listen(1)
conn, addr = s.accept()
while 1:
 data = conn.recv(BUFFER_SIZE)
 if not data:
  break
 msg = data.decode('utf-8')
 msg = msg[::-1]
 conn.send(msg.encode('utf-8'))
conn.close() 

unix_client.py

import socket

PATH = '/tmp/sample.sock'
BUFFER_SIZE = 1024

s = socket.socket(socket.AF_UNIX, socket.SOCK_STREAM)
s.connect(PATH)
msg = "ABCDEFG"
s.send(msg.encode('utf-8'))
data = s.recv(BUFFER_SIZE)
print (data.decode('utf-8'))
s.close()

プロセスIDからUNIXドメインソケットを調べる。
$ ps -ef | grep python     
  501 11543  2011   0 12:02AM ttys000    0:00.04 python unix_server.py
$ lsof -n -P -U | grep 11543
python3.5 11543 kenjih    3u  unix 0xf279496017547fcb      0t0      /tmp/sample.sock

2016年8月17日水曜日

httpbinでテストする

Pythonのurllib3のRetry、Timeoutの動作確認をするためにテスト用のサーバを書こうかどうか迷っていたところ、httpbinという便利なサイトを見つけた。
これは便利。

指定したステータスコードを返す
https://httpbin.org/status/:code
をたたくと、指定した:codeをステータスコードとして返してくれます。

urllib3でステータスコードが400、500番台の場合はバックオフしてリトライするコードをhttpbinで動作確認。
from urllib3.util import Retry
from urllib3 import PoolManager

http = PoolManager(retries=Retry(total=4, backoff_factor=1.0, status_forcelist=range(400, 600)))

response = http.request('GET', 'https://httpbin.org/status/500')
print ("status code=%s." % response.status)

指定した秒だけ待ってレスポンスを返す
https://httpbin.org/delay/:n
をたたくと、min(n, 10)秒間待ってレスポンスを返してくれます。

urllib3のTimeoutの動作確認用ソースです。5秒たつとtimeoutエラーが発生します。
from urllib3.util import Retry, Timeout
from urllib3 import PoolManager

http = PoolManager(timeout=Timeout(5))

response = http.request('GET', 'https://httpbin.org/delay/8', retries=False)
print ("status code=%s." % response.status)

timeoutしても頑張るバージョン。
from urllib3.util import Retry, Timeout
from urllib3 import PoolManager

timeout = Timeout(5)
retries = Retry(total=4, backoff_factor=1.0, status_forcelist=range(400, 600))

http = PoolManager(timeout=timeout, retries=retries) 
response = http.request('GET', 'https://httpbin.org/delay/8')
print ("status code=%s." % response.status)
この場合は、4回リトライしtimeoutエラーになります。

2016年8月15日月曜日

多項ロジットの理論と実装

問題設定
訓練データ(xn, yn), xn ∈ R D, yn ∈ {1,2,...C}, n=1,2,...,Nを使って、マルチクラス識別問題を解くモデルを考えます。

多項ロジットのモデル
多項ロジットでは以下のモデルを使います。


分子は訓練データxの特徴量の線形結合をロジスティック関数に入れたものです。
分子は非負の値を取ります。

上の式はxがクラスyに属する確率を表します。
よって、xがクラス1に属する確率、xがクラス2に属する確率、...をすべて足すと1.0になっていて欲しいです。この条件を満たすように分母の値で割って正規化を行います。

パラメータの学習
多項ロジットのパラメータは、


です。ここでCはクラスの個数、Dはデータの次元数です。
つまりクラスの数だけ重みベクトルが存在します。

これらのパラメータを学習するために、以下の対数尤度関数を最大化します。

対数尤度関数の偏微分を計算します。
まず第一項の偏微分は以下のようになります。

[]は中の条件が真のときは1、偽のときは0になるような関数です。

第二項の偏微分は以下のようになります。


よって全体の偏微分は、
となります。

偏微分が求まったので、θを適当な値に初期化して、勾配法で対数尤度関数を最適化することができます。

実装
Pythonで実装しました。

import numpy as np

class MultinomialLogit:

 def __init__(self):
  self.C = 0
  self.N = 0
  self.D = 0
  self.theta = None

 def prob(self, X, y):
  return np.dot(self.theta[y], X) / sum(np.dot(self.theta[c], X) for c in range(self.C))

 def logLiklihood(self, X, y):
  return sum(np.log(self.prob(X[n], y[n])) for n in range(self.N))
 
 def fit(self, X, y, iter=200):
  self.C = len(set(y))
  self.N = len(X)
  self.D = len(X[0])+1   # bias term is added
  self.theta = np.random.rand(self.C, self.D);

  bias = np.ones((len(X), 1))
  X = np.hstack((X, bias))

  def delta(a, b):
   return 1.0 if a == b else 0.0
  
  for i in range(iter):
   for c in range(self.C):
    gradient = sum((delta(c, y[n]) - self.prob(X[n], c)) * X[n] for n in range(self.N)) 
    self.theta[c] += gradient
   print ("i=%d %f" % (i, self.logLiklihood(X, y)))
    
 def predict(self, X):
  bias = np.ones((len(X), 1))
  X = np.hstack((X, bias))
  return [np.argmax([self.prob(x, c) for c in range(self.C)]) for x in X]

 def score(self, X, y):
  Ypred = self.predict(X)
  comp = Ypred == y
  return sum(comp) / len(comp)

Irisで実験
Irisのデータを使って実験してみました。
テスト識別率は80%後半程度です。sklearnのLogisticRegressionだと100%が出るので全然ダメな感じですが、
  • iterationごとに対数尤度関数が上昇すること
  • 対数尤度関数が上がるとテスト識別率も上がること
を確認できたのでそれっぽい実装は出来てそうです。学習率を設定したり、 ヘッセ行列を計算してニュートン法系の最適化を行ったり、確率的勾配法を使ったりなど改善の余地はたくさんありそうです。

if __name__ == '__main__':
 from sklearn import datasets
 from sklearn import cross_validation
 
 iris = datasets.load_iris()
 X = iris.data
 y = iris.target

 Xtrain, Xtest, Ytrain, Ytest = cross_validation.train_test_split(X, y, test_size=0.3)
 logit = MultinomialLogit()
 logit.fit(Xtrain, Ytrain, iter=1000)
 print (logit.score(Xtest, Ytest))


2016年8月14日日曜日

SRM 507 Div1 500 CubePacking

問題
辺の長さが1の立方体がNs個、辺の長さがLの立方体がNb個ある。
これらの立方体を出来るだけ体積が小さい直方体に格納したい。
直方体の体積の最小値を求めよ。

解法
解の下限はNb*L*L*L+Nsである。
解の上限はNb*L*L*L+Ns+L*L-1である。(L*Lの底面を持つ直方体に立方体を詰め込む)
ということで、 解の候補をすべて列挙しても高々L*L程度のループをまわせばよい。

あとは、それぞれの解の候補に対して、その体積になるような直方体を全列挙すればよい。これは時間がかかりそうだが約数の個数は思ったほど多くないため十分に間に合う。

以下に整数の約数の個数がどの程度かを示す。
この結果はN周辺の数をサンプリングし、それらの約数の個数の平均値を取ったものである。
N 約数の個数
106 14.9
107 17.3
108 19.6
109 21.9

ざっくりと高々log(N)程度と覚えておくと良さそう(あくまでも平均値であることに注意)。

ソースコード
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

vector<long long> divisor(long long n) {
  vector<long long> ret;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i != n / i)
        ret.push_back(n / i);
    }
  }
  return ret;
}

class CubePacking {
  public:
  int getMinimumVolume(int Ns, int Nb, int L) {
    int s = L*L*L*Nb+Ns;
    for (int x = s;; x++) {
      auto ds = divisor(x);
      REP (i, ds.size()) REP (j, i+1) {
        int a = ds[i];
        int b = ds[j];
        int c = x / a / b;
        if (a * b * c != x)
          continue;
        if ((a/L) * (b/L) * (c/L) >= Nb)
          return x;
      }
    }
    return -1;
  }
};

2016年8月12日金曜日

TornadoでWebSocketを使ってみた

WebSocketとは?
ウェブサーバとウェブブラウザ間で双方向通信を行うための規格。
WebSocketを使うことで、サーバ側からクライアント側にプッシュ配信を行うことができる。通信ごとにコネクションを張り替えるのではなく、すべての通信を一つのコネクションで行うことができる。

Tornadoとは?
PythonのWebフレームワーク/非同期通信のライブラリ。
数万単位のコネクションにスケールすることができ、WebSocketのようにユーザごとに長期のコネクションを構築しておきたい場合に有用。

サンプル
チャットアプリを作ってみた。

サーバ側のコード。
tornado.websocket.WebSocketHandlerクラスを継承して、必要なイベントハンドラメソッドをオーバーライドすればよい。

import tornado.ioloop
import tornado.web
import tornado.websocket

class ChatHandler(tornado.websocket.WebSocketHandler):
 clients = []

 def open(self):
  if self not in ChatHandler.clients:
   ChatHandler.clients.append(self)

 def on_message(self, message):
  for c in ChatHandler.clients:
   c.write_message(message)

 def on_close(self):
  if self in ChatHandler.clients:
   ChatHandler.clients.remove(self)

class MainHandler(tornado.web.RequestHandler):
 def get(self):
  self.render('main.html')

if __name__ == "__main__":
 application = tornado.web.Application([
  (r"/chat/main.html", MainHandler),
  (r"/chat/websocket", ChatHandler),
 ])
 application.listen(8888)
 tornado.ioloop.IOLoop.current().start()

クライアント側のコード。WebSocketクラスを使って接続、メッセージ送信、メッセージ受信時の処理を行う。
<!DOCTYPE html>
<html>
  <head>
    <title>websocket chat</title>
    <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.12.4/jquery.min.js"></script>
    <link rel="stylesheet" href="//maxcdn.bootstrapcdn.com/bootstrap/3.3.2/css/bootstrap.min.css" />
    <script src="//maxcdn.bootstrapcdn.com/bootstrap/3.3.2/js/bootstrap.min.js"></script>
    <script>
      $(function() {
        socket = new WebSocket("ws://kenjih.com:8888/chat/websocket");
        socket.onopen = function() {};
        socket.onmessage = function(e) {
          $("#msgbox").append($('<p>'+e.data+'</p>'));
        };
        $('#send').click(function(){
          socket.send($('#msg').val());
          $('#msg').val('');
        });
        $('#msg').keydown(function(e) {
          if (e.keyCode == 13) {
            socket.send($('#msg').val());
            $('#msg').val('');
          }
        });
      });
    </script>
  </head>
  <body>
    <div class="container">
      <div class="row">
      <h1>Websocket Chat Room</h1>
      </div>
      <div class="row">
        <div class="col-xs-5">
          <div class="input-group">
            <input id="msg" type="text" class="form-control" placeholder="put your message...">
            <span class="input-group-btn">
              <button id="send" class="btn btn-primary" type="button">Send</button>
            </span>
          </div>
        </div>
        <div class="col-xs-7">
          <div class="panel panel-primary">
            <div class="panel-heading">
              <h3 class="panel-title">Messages</h3>
            </div>
            <div id="msgbox" class="panel-body"></div>
          </div>
        </div>
      </div>
    </div>
  </body>
</html>