パーセプトロンの収束に学習率は関係ない件
(2012-06-20追記) ただし，重みベクトルの初期値が0のときだけということの記述忘れ．これについて以下の記事参照 (パーセプトロンの収束に学習率が関係ないのは初期値が0のときだけ)
前回の記事に @shuyo さんから以下のコメントを頂いた．前半部分を引用する．
「学習率を適当な値に設定すると経験的には収束が速くなる」とありますが、本当にそうでしょうか？
重みの初期値は０ですから、更新式よりη倍した解が求まるだけで、収束性に影響があるように思えません。
はい，そのとおりです．重みベクトルは定数倍しても分離超平面は変化しない．
そのため，学習率がいくつになろうと，@shuyo さんのおっしゃるようにη倍した重みベクトルが得られるだけで，収束に影響しない．というわけで「経験的には適当な学習率を設定した方が収束が速い」というのは誤り．お詫びして訂正します．そして @shuyo さんありがとうございます．
検証
というわけで検証するまでもないのだけれど，体験してみることが大切な気がするので線形分離可能なデータセットを作成し，異なる学習率を設定したパーセプトロンで収束までの誤り回数と最終的な重みベクトルを表示するプログラムを書いて実行してみた．(実験に用いたコードは末尾に記載)
結果は以下のとおり．上から学習率が100, 10, 1, 0.1, 0.01, 0.001．
% python gen_data.py > toy.txt % python perceptron.py toy.txt Converged. Error count=56621 [3441900.0, -356.84360002073299, -19582.371400038977] Converged. Error count=56621 [344190.0, -35.68436000034535, -1958.2371400047396] Converged. Error count=56621 [34419.0, -3.5684360000869333, -195.82371400042496] Converged. Error count=56621 [3441.8999999979651, -0.356843600001298, -19.582371400016243] Converged. Error count=56621 [344.18999999983197, -0.035684359999769488, -1.9582371400026064] Converged. Error count=56621 [34.419000000010485, -0.0035684360000880627, -0.19582371400070708]
結果などみなくてもわかるとおり，全て同じ誤り回数で収束していることがわかる．
ただし，学習率が大きいと重みベクトルの大きさが激しいことになっている．正則化の観点からすると，ノルムは小さい方がよい．また，線形分離可能でないときには偉いことになっている重みベクトルを得ることがあるので，実用上は学習率は小さめに設定しておいた方がよいと思うのだけれど，それは正則化についてきちんと頭の整理がついてから，また別の機会に書くことにする．
コメントされて気が付いたときは布団の上で暴れるほど恥ずかしくて死にそうだったけれど，大恥をかく前に知ることができてよかったと思う．@shuyo さんに改めて感謝．
利用したコード
- gen_date.py
# -*- coding:utf-8 -*- import random import math def box_muller (): x = random.random() y = random.random() z1 = math.sqrt( - 2.0 * math.log(x) ) * math.cos( 2.0 * math.pi * y ) z2 = math.sqrt( - 2.0 * math.log(x) ) * math.sin( 2.0 * math.pi * y ) return (z1, z2) def gauss_rand_2d (mu1, sigma1, mu2, sigma2): pair = box_muller() return ( (sigma1 * pair[ 0 ]) + mu1, (sigma2 * pair[ 1 ]) + mu2 ) def gen_data (settings): pos_num = settings['pos_num'] pos_xmu = settings['pos_xmu'] pos_xsigma = settings['pos_xsigma'] pos_ymu = settings['pos_ymu'] pos_ysigma = settings['pos_ysigma'] neg_num = settings['neg_num'] neg_xmu = settings['neg_xmu'] neg_xsigma = settings['neg_xsigma'] neg_ymu = settings['neg_ymu'] neg_ysigma = settings['neg_ysigma'] for i in range(0, pos_num): xy_pair = gauss_rand_2d( pos_xmu, pos_xsigma, pos_ymu, pos_ysigma ) print "1 1:%f 2:%f" % (xy_pair[0], xy_pair[1]) for i in range(0, neg_num): xy_pair = gauss_rand_2d( neg_xmu, neg_xsigma, neg_ymu, neg_ysigma ) print "-1 1:%f 2:%f" % (xy_pair[0], xy_pair[1]) if __name__ == '__main__': settings = {'pos_num':50, 'pos_xmu':50, 'pos_xsigma':50, 'pos_ymu':50, 'pos_ysigma':50, 'neg_num':50, 'neg_xmu':300, 'neg_xsigma':50, 'neg_ymu':300, 'neg_ysigma':50} gen_data( settings )
- perceptron.py
# -*- coding: utf-8 -*- import sys import random class Instance: def __init__ (self, line): self.label = 0 self.fvec = [] self.parse_line( line ) def parse_line (self, line): pair_list = line.split(' ') label = int( pair_list.pop( 0 ) ) if label != -1 and label != 1: print "Label must be +1 or -1" sys.exit(1) self.label = label for pair in pair_list: if pair.find(':') < 0: continue fid, fval = pair.split(':') self.fvec.append( (int(fid), float(fval)) ) def get_max_fid (self): return self.fvec[ -1 ][ 0 ] class Instances: def __init__ (self, filename): self.ins_list = [] self.load_file( filename ) def load_file (self, filename): max_fid = -1 for line in open( filename, 'r' ): ins = Instance( line ) cur_max_fid = ins.get_max_fid() if cur_max_fid > max_fid: max_fid = cur_max_fid self.ins_list.append( ins ) self.max_fid = cur_max_fid def get_random_instance (self): idx = random.randint(0, len(self.ins_list) - 1) return self.ins_list[ idx ] class Perceptron: def __init__ (self, inss, iternum = 1000, eta = 0.01): self.instances = inss self.wvec_size = self.instances.max_fid + 1 # Consider bias term self.wvec = [ 0.0 ] * self.wvec_size self.iternum = iternum self.eta = eta def check_convergence (self, iternum, eta): # Initialize weight vector and eta value self.wvec = [ 0.0 ] * self.wvec_size self.eta = eta convergence_flag = True error_count = 0 for i in range(0, iternum): convergence_flag = True for ins in self.instances.ins_list: wx = self.inner_prod( ins ) if ins.label * wx <= 0: # Error self.update_weight( ins ) error_count += 1 convergence_flag = False if convergence_flag: break if convergence_flag: print "Converged." else: print "Failed to converge." print "Error count=%d" % (error_count) print self.wvec def train (self): for i in range(0, self.iternum): ins = self.instances.get_random_instance() wx = self.inner_prod( ins ) if ins.label * wx <= 0: self.update_weight( ins ) def predict (self, instance): return 1 if self.inner_prod( instance ) >= 0 else -1 def inner_prod (self, instance): fx = self.wvec[ 0 ] # bias term for pair in instance.fvec: fx += self.wvec[ pair[ 0 ] ] * pair[ 1 ] return fx def update_weight (self, instance): self.wvec[ 0 ] += self.eta * instance.label for pair in instance.fvec: self.wvec[ pair[ 0 ] ] += self.eta * instance.label * pair[ 1 ] if __name__ == '__main__': argv = sys.argv argc = len( sys.argv ) if (argc < 2): print "Input filename" quit() inss = Instances( argv[ 1 ] ) p = Perceptron( inss ) p.check_convergence( 100000, 100 ) p.check_convergence( 100000, 10 ) p.check_convergence( 100000, 1 ) p.check_convergence( 100000, 0.1 ) p.check_convergence( 100000, 0.01 ) p.check_convergence( 100000, 0.001 )
