TIM Labs

2017年1月アーカイブ

せっかくChainerについて書いているのだが、微分とか、まるで数学の基礎を説明していると読んでいて飽きるだろう。早くChainerでの Deep Learning の方法が知りたいであろう。

ということで、突然ではあるが、紹介した『Chainerによる実践深層学習』は、書籍中のプログラムも公開されているので、それを利用しながら話を進めようと思う。

最初に行う Deep Learning は、どこへ行ってもIrisの種の分類だ。
Python からとても簡単に使えるようになっているので、Chainerに限らず、多数の書籍の最初のDLのデータがIrisになっている。
だから、ここでも、そのままIrisのデータを用い、3種のIrisの種の分類をやってみる。

プログラム全体はここでは示さない。 『Chainerによる実践深層学習』
から、プログラムのアーカイブをダウンロードして見て欲しい。
今回は、その中から、 iris0.py という短い簡単なプログラムについて説明する。

以下に、そのプログラムの、初期化、学習ループ、学習結果の評価の部分だけを掲載する。
なお、適当に変更しているので、オリジナルとは若干違う。
また、Python 3で動くように、printのところは変更している。

# 学習モデルの初期化

model = IrisChain()
optimizer = optimizers.SGD()
optimizer.setup(model)

# 学習ループ

for i in range(10000):
    x = Variable(xtrain)
    y = Variable(ytrain)
    model.zerograds()
    loss = model(x,y)		# lossを求める (forward)
    loss.backward()		# 微分(backward)
    optimizer.update()		# 調整

# Testデータで学習成果を確認する

xt = Variable(xtest, volatile='on')	# 学習不要
yy = model.fwd(xt)

ans = yy.data
nrow, ncol = ans.shape
ok = sum([np.argmax(ans[i,:])==yans[i] for i in range(nrow)])
print( ok, "/", nrow, " = ", (ok * 1.0)/nrow )		# 正解率

実行してみよう。
Chainer$ python iris0.py
72 / 75  =  0.96
Chainer$ python iris0.py
68 / 75  =  0.906666666667
Chainer$ python iris0.py
70 / 75  =  0.933333333333
Chainer$ 
>>> 

こんな感じで、プログラムを走らせる度に、学習成果(テストデータの正解率)が異なった。 といっても、いずれも90%を超える正解率になっているので、かなり良い正解率といえるのではないだろうか。

今回は、Deep Learningでよく見る階層に分かれ、層間を多数の線で結んだ図を良く見るであろうが、それに対応するモデルの部分は示さなかった。
プログラムの意味を解説するよりも、プログラムを勝手に変更したり、別のデータを入れるとどんなことになるかなど、真面目に勉強したい人はさっさと書籍を読むであろうから、興味の向くまま勝手な実験を進め、紹介しようと思っている。
cossinx_1.pngどうやら微分ができることが分かった。
といっても、公式として覚えておくべきような簡単なものであった。
今回は、もうちょっと複雑なのをやって、本当に微分できているか確かめよう。
疑い深いのは重要なことである。

難しい式を急に用意しようと思っても、思いつかない。
そういう時は、何かの本のを利用しよう。
と思って背面の本箱を見たら、何とマセマの『微分積分』があった。マセマについては、そのうち紹介しよう。
p77の実践問題9の(2)の微分をしてみよう。
y = cos(sin(x))
以下、前回と同じで、式の部分が異なる。
まず、[-π,π] のの区間を20等分してxに入れる。
以下、前回と同じで、式の部分が異なる。
>>> x = Variable(np.array(np.linspace(-np.pi, np.pi, 21), dtype=np.float16))
>>> y = F.cos(F.sin(x))
>>> y.data
array([ 1.        ,  0.95263672,  0.83251953,  0.68994141,  0.58056641,
        0.54052734,  0.58056641,  0.68994141,  0.83203125,  0.95263672,
        1.        ,  0.95263672,  0.83203125,  0.68994141,  0.58056641,
        0.54052734,  0.58056641,  0.68994141,  0.83251953,  0.95263672,  1.        ], dtype=float16)
>>> y.grad = np.ones((21),dtype=np.float16)
>>> y.backward()
>>> x.grad
array([ -9.67502594e-04,  -2.88574219e-01,  -4.48486328e-01,
        -4.25537109e-01,  -2.51464844e-01,   4.06980515e-04,
         2.51464844e-01,   4.25537109e-01,   4.48730469e-01,
         2.89306641e-01,  -0.00000000e+00,  -2.89306641e-01,
        -4.48730469e-01,  -4.25537109e-01,  -2.51464844e-01,
        -4.06980515e-04,   2.51464844e-01,   4.25537109e-01,
         4.48486328e-01,   2.88574219e-01,   9.67502594e-04], dtype=float16)
これで、ちゃんと微分ができているような気がする。

それでは確認だ。
cos(sin(x))の微分を計算してみよう。
・・・ん、どうすれば良いのだろう。 微分を忘れた。
そういう時のために、ネットがある。
例えば、WolframAlphaを使えば、式だけ与えれば、微分だけでなく積分もしてくれる。

WolframAlphaによると、
cossinx_2.gif となる。 これ以外にも、ネット上にはこんな便利なモノがいっぱい転がっている。

これを元に、検算をしてみた。
>>> dy = - F.cos(x) * F.sin(F.sin(x))
>>> dy.data
array([ -9.67502594e-04,  -2.88574219e-01,  -4.48486328e-01,
        -4.25537109e-01,  -2.51464844e-01,   4.06980515e-04,
         2.51464844e-01,   4.25537109e-01,   4.48730469e-01,
         2.89306641e-01,  -0.00000000e+00,  -2.89306641e-01,
        -4.48730469e-01,  -4.25537109e-01,  -2.51464844e-01,
        -4.06980515e-04,   2.51464844e-01,   4.25537109e-01,
         4.48486328e-01,   2.88574219e-01,   9.67502594e-04], dtype=float16)
>>> x.grad - dy.data
array([ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,
        0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.], dtype=float16)
>>> np.max(np.abs(x.grad - dy.data))
0.0
複雑なのでもできるようだ。
この微分で重要なことは、普通のPythonの関数を使うのではなく、chainerで用意されている関数を使わないといけない。そのために、どの関数も F. となっている。

1変数関数をやってきたが、DLは多変数関数というか、超多変数関数を偏微分しないといけないのだ。
次は、そういうことをしようか、でもどうなるかは気分次第。
前回、変数を配列にしたらエラーがでてしまった。

それで、やはりマニュアル、イントロなどを読まねばと非常にまともなことを考えて読み始めた。

Introduction to Chainerの中のForward/Backward Computationに、配列を与えた場合の微分の例が見つかった。

こういうときは、初期勾配(全要素が1.0)を用意してからbackward()をやらないといけないらしい。
それで、このように変更してみた。
>>> y = F.sin(x)
>>> y.grad = np.ones(21,dtype=np.float16)     # 追加, 勾配の初期化
>>> y.backward()
>>> x.grad
array([ -1.00000000e+00,  -9.51171875e-01,  -8.09082031e-01,
        -5.87890625e-01,  -3.08837891e-01,   4.83751297e-04,
         3.08837891e-01,   5.87890625e-01,   8.09082031e-01,
         9.51171875e-01,   1.00000000e+00,   9.51171875e-01,
         8.09082031e-01,   5.87890625e-01,   3.08837891e-01,
         4.83751297e-04,  -3.08837891e-01,  -5.87890625e-01,
        -8.09082031e-01,  -9.51171875e-01,  -1.00000000e+00], dtype=float16)
これで、配列xの各値に対するsin(x)の微分係数が求まっているはず。
もちろん、sin(x)の微分はcos(x)なので確認しよう。

>>> dy = F.cos(x)
>>> dy.data
array([ -1.00000000e+00,  -9.51171875e-01,  -8.09082031e-01,
        -5.87890625e-01,  -3.08837891e-01,   4.83751297e-04,
         3.08837891e-01,   5.87890625e-01,   8.09082031e-01,
         9.51171875e-01,   1.00000000e+00,   9.51171875e-01,
         8.09082031e-01,   5.87890625e-01,   3.08837891e-01,
         4.83751297e-04,  -3.08837891e-01,  -5.87890625e-01,
        -8.09082031e-01,  -9.51171875e-01,  -1.00000000e+00], dtype=float16)
どうやら一致しているようだが、目視確認なんて面倒くさい。

ということで、こうやって確認した。
>>> x.grad-dy.data
array([ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,
        0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.], dtype=float16)
Lazyはプログラマの最大の美徳であることを忘れてはいけない。
Lazyな確認方法により信頼性が一気に向上した。

これで、どうやらsin(x)の微分はできているみたいだが、こんな簡単な微分ができたから、Chainerの微分がちゃんと動作していると考えるのは甘いだろう。
次からは、もっと複雑な関数を微分してみよう。

ChainerDeepLearning.gif Chainerによる実践深層学習

親納 浩幸 著 (著書一覧

A5版、192ページ
2016/9/24 発行
2400円(本体)
オーム社
ISBN-13: 978-4-274-21934-4

本書のプログラムとデータ



Deep Learning のフレームワークはいろいろあるのだが、日本発のフレームワーク Chainer の書籍があるので紹介する。

といっても、まだ一部しか試していない状況なので、とりあえず概要を書いておく。

まず、なんといっても、薄い。全体で192ページしかなく、最初の方はDeep Learning の基本と、Chainerの基本的な使い方が示されているだけで50ページほどが終る。
といっても、これだけのことを50ページで書いているので、かなりハイペースである。

第2章のタイトルが「ニューラルネットのおさらい」であり、ニューラルネットのプログラミングに関してある程度の知識があることが前提になっていることが伺える。

だから、他書で Deep Learing の知識をある程度身につけていないと厳しいと思われる。
そういう場合、たとえば、以前紹介した『ゼロから作る Deep Learning』などをまず読むと良いだろう。

本書のプログラムは公開されており、とても便利である。
ただし、python3 対応ではないので、pyton3 上で動かすときには、print などの変更が必要になるが、エラーを頼りに修正すれば簡単に済む範囲だ。といっても、まだ一部のプログラムを確かめただけだが。

Deep Learning のプログラムは、突然本格的なものを見せられると訳がわからなくなると思うが、本書には比較的簡単な例があり、自分で確かめることが容易である。

ページ数が少ないので、道草をあまりしていない本になっている。
プログラミングの実力をつけるためには、勝手にプログラムをあれこれ変更してみる必要があるのだが、そのベースとして使うにはとても都合が良さそうだ。

最後は、ChainerからGPUを利用する方法の説明もある。
CuPyの説明があり、これだけ使って、PythonからGPUを使えるようになると便利かも知れない。

この技術者ブログでは、本書のプログラムも大いに参考にし、勝手に大幅にいじって、どんなことになってしまうか、紹介しようと思っている。
でも、保証はしない。
要するに、本書は、この技術者ブログのネタ本の1つである。
なので、本書をさっと読まれると、ちょっと困る(笑)
前回、特定の値に対する微分係数を求めた。
式で書けば, 関数 f(x) に 対して x=a のときの微分係数 f'(a) を求めた。
そのとき、
x = Variable(np.array([5.0],dtype=np.float16))
として変数xを用意したのだが、np.array([5.0])で、スカラーを要素数1個の配列でわざわざ与えた。
ということは、配列に対しても、そのまま動くのではないだろうか。

ということで、 sin(x) を -np.pi <= x <= np.pi の区間内の複数の点に対して一気に計算してみよう。

まず、配列の生成を確認。
>>> np.array(np.linspace(-np.pi, np.pi, 21))
array([-3.14159265, -2.82743339, -2.51327412, -2.19911486, -1.88495559,
       -1.57079633, -1.25663706, -0.9424778 , -0.62831853, -0.31415927,
        0.        ,  0.31415927,  0.62831853,  0.9424778 ,  1.25663706,
        1.57079633,  1.88495559,  2.19911486,  2.51327412,  2.82743339,
        3.14159265])
この配列を与えて、chainerの変数xを配列で作ってしまおう。
>>> x = Variable(np.array(np.linspace(-np.pi, np.pi, 21), dtype=np.float16))
>>> x.data
array([-3.140625  , -2.828125  , -2.51367188, -2.19921875, -1.88476562,
       -1.5703125 , -1.25683594, -0.94238281, -0.62841797, -0.31420898,
        0.        ,  0.31420898,  0.62841797,  0.94238281,  1.25683594,
        1.5703125 ,  1.88476562,  2.19921875,  2.51367188,  2.828125  ,
        3.140625  ], dtype=float16)
値が少々違うが、これはnp.float16としたため、精度が落ちているのでやむを得ないだろう。

F.sin(x)にて配列xの各値に対して、まとめてsin(x)が求まるはずである。
>>> y = F.sin(x)
>>> y.data
array([ -9.67502594e-04,  -3.08349609e-01,  -5.87402344e-01,
        -8.09082031e-01,  -9.51171875e-01,  -1.00000000e+00,
        -9.51171875e-01,  -8.09082031e-01,  -5.87890625e-01,
        -3.09082031e-01,   0.00000000e+00,   3.09082031e-01,
         5.87890625e-01,   8.09082031e-01,   9.51171875e-01,
         1.00000000e+00,   9.51171875e-01,   8.09082031e-01,
         5.87402344e-01,   3.08349609e-01,   9.67502594e-04], dtype=float16)
yの値は、 -1 <= sin(x) <= 1 に収まっているようだ。


次に、y.backward() で微分してみよう。
>>> y.backward()
Traceback (most recent call last):
  File "", line 1, in 
  File "/home/fuji/anaconda3/lib/python3.5/site-packages/chainer/variable.py", line 388, in backward
    gxs = func.backward(in_data, out_grad)
  File "/home/fuji/anaconda3/lib/python3.5/site-packages/chainer/function.py", line 382, in backward
    return self.backward_cpu(inputs, grad_outputs)
  File "/home/fuji/anaconda3/lib/python3.5/site-packages/chainer/functions/math/trigonometric.py", line 25, in backward_cpu
    gx *= gy[0]
TypeError: ufunc 'multiply' output (typecode 'O') could not be coerced to provided output parameter (typecode 'e') according to the casting rule ''same_kind'
>>>
ということで、backward()したとたんに叱られた。
要素数1だと大丈夫だったのだが、複数個に対してはダメなんだ。
何か悪いことをしたらしい。
 
次回までに原因を考えることにし、今日はここまで。
DLするためには、微分して勾配を求める必要がある。
ということで、まず、簡単な微分をしてみよう。

Chainerを動かすためには、まず最初に色々なものをimportしなければならない。
とりあえず、「おまじない」だと思って、プログラムの最初に書いておこう。

# おまじない
import numpy as np
import chainer
from chainer import cuda, Function, gradient_check, Variable 
from chainer import optimizers, serializers, utils
from chainer import Link, Chain, ChainList
import chainer.functions as F
import chainer.links as L
微分するためには、まず変数を作らないといけない。
それも、Pythonの変数ではなく、Chainerの変数として作らないといけない。
そのために、ちゃんとVariableをimportしているので、さっそくやってみよう。

>>> x = Variable( 5.0 )
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/fuji/anaconda3/lib/python3.5/site-packages/chainer/variable.py", line 95, in __init__
    raise TypeError(msg)
TypeError: numpy.ndarray or cuda.ndarray are expected.
Actual: <class 'float'>
>>>
エラーメッセージから、Variableに直接5.0を与えてはだめで、型がnumpy.ndarrayかcuda.ndarrayになっていないとダメらしい。
ということで、要素数1個だけの配列にして、変数xを作って、y=x**2-2x+1 を与え微分してみた。
微分は、y.backward()にて行われている。
>>> x = Variable(np.array([5.0]))
>>> y = x**2 - 2 * x + 1
>>> y.data
array([ 16.])
>>> y.backward()
>>> x.grad
array([ 8.])
x=5のときのy=f(x)の値は、
y = x**2 - 2 * x + 1 にてforward処理が行われ、y.dataに値が求まっていて、f(5)=16が確認できる。

微分はy.backward()で行われ、結果は x.gradに入り、yのメンバーの何かに入るのではない。
今回は、yに含まれる変数がxただ1つだったが、DLでは多変数の微分(偏微分)が行われ、それぞれの変数の.gradに偏微分(微分係数)が入る。

y = x**2 - 2 * x + 1 をxで微分すると、dy/dx = 2*x - 2 なのだが、x=5のときの微分係数が求まるだけである。
x=5のときの微分係数が8であることは、次のようにしても確かめられる。

>>> dy = 2 * x - 2
>>> dy.data
array([ 8.])

何も指定しなかったので、
>>> type(x.data[0])
&lr;class 'numpy.float64'>
>>> type(y.data[0])
<class 'numpy.float64'&l\gt;
>>> type(x.grad[0])
<class 'numpy.float64'>
という風に、全部float64になってしまった。
DLでは精度はそれほど要らないので、とりあえずfloat32と思ったが、float16も用意されているので、使ってみた。
>>> x = Variable(np.array([5.0],dtype=np.float16))
>>> y = x**2 - 2 * x + 1
>>> y.backward()
>>> x.grad[0]
8.0
>>> type(x.grad[0])
<class 'numpy.float16'>

今回は簡単過ぎる微分だったので、次はもうちょっと高度な微分をやらせてみよう。
新年を迎えたので、何か新しいことをしようということで選んでみたのがChainerである。

去年の春、AlphaGoから人工知能の狂乱ブームが始まり、猫も杓子も Deep Learning を勉強しているようで、オライリージャパンの『ゼロからはじめるDeep Learing』がやたらに売れている。
もう4万部を突破しているようだが、あの本を4万人もの人が読んで理解できるなら、日本のIT技術者の層は予想より遥かに厚かったことになるが、実際には人工知能ブームに流されて買っただけで積読状態ではないかと思っている。

Deep Learning(以下DL)でよく利用されている言語がPythonである。といっても、Pythonの基本部分ではなく、NumPyを始めとする拡張部分を使いまくってDLを実現している。つまり、Pythonの基本部分を使いこなすだけでDLのコードが書けるわけではない。

ちょっと勉強し、拡張機能を使えば、かなり簡単にDLを実現できるが、もっともっと安直に横着に怠惰に使いたいという人間の本性を満たすために、さまざまなフレームワークが提供されている。

Googleが開発し公開したTensorFlowが一番有名で、日本語でも書籍が複数冊出ているようだ。
ネット上でも、色々な情報が出ているようだ。
ということで、TensorFlowは避けることにした(笑)

それで、何か別のものはないかと探して見つかったのがChainerというDLのフレームワークである。

とりあえず、本家(http://chainer.org/)を知っておくべきだ。
Chainerは、東大や京大出身者が集まって作ったベンチャー企業であるPreferred Infrastructure社からさらにスピンアウトしたPreferred Networksが作っている。
スピンアウトといっても、役員が一緒なので、ベンチャーの企業内ベンチャーみたいなものだろうか。

たとえば、深層学習フレームワーク Chainer の開発と今後の展開 という62ページのプレゼン資料もある。
著者の得居誠也氏は、現役の東大の情報科学専攻の大学院生である。
その他にもいろいろ資料がネット上にあるので、そのうち紹介しようと思う。

DLでは海外のソフトが圧倒的に強いのだが、そういうのは避けて、日本発のを弄ることにした。

まず、インストールしなければいけないのだが、pipで簡単にインストールできる。
 
pip install chainer

そして、Pythonを起動して、import して、バージョンを確認してみた。
>>> import chainer
>>> chainer.__version__
'1.19.0'
>>> 
これで、とりあえず動いているらしいことが分かった。 勉強開始だ!

去年からAIブームが続いているが、同時に「データサイエンス」さらには「データサイエンティスト」という言葉もよく聞く。

そして、データサイエンスを学習するための本として、以前は統計学などの本が紹介されていたのだが、最近はタイトルに「データサイエンス」が直接入ることが多くなった。

データサイエンスの本というと、やはり以下の、岩波書店の「岩波データサイエンス」を思い出す。

iwaDS1 (280x400).jpg       iwaDS2 (281x400).jpg


iwaDS3 (281x400).jpg       iwaDS4 (279x400).jpg

全6巻の予定で刊行中であり、今までに4巻出ており、4ヶ月に1冊のペースで毎回データサイエンスにちなんだ特集を組んでいる。

各冊、144ページが標準で、税込み1500円と、岩波書店にしては珍しいページ数であり、価格なのだ。

データサイエンスをきっちり順番に勉強していくための学習書というより、データサイエンスとはどんなもので、どんな利用のされ方をしているかを紹介しているような、ちょっと雑誌的な構成になっている。
だから、毎回、異なるメンバーが、様々なトピックを紹介している。

でも、いきなりトピックを始めると難度が高くなり過ぎるので、最初に2,3本くらいの記事は、特集分野についての概説やら入門やらになっていて、この部分はかなり読みやすいことが多い。

執筆者は、最先端の現場で働いているデータサイエンティストが多く、実例の紹介が並んでいる。こまかい説明が無かったりして、この本だけで理解するのは困難なことが多かったり、統計学の基礎ができていないと落ちこぼれたりすることもあるが、さまざまな情報源の紹介などもあるので、目を通すだけでも相当有益ではないかと思う。

岩波データサイエンス刊行委員会があり、統計数理研究所をはじめとして、多くの研究機関、大学、企業の研究者などが協力して多様な分野をカバーしている。
さらに、毎回出版記念トークショーを行い、多数の来場者が参加している。参加者の中には、本物のデータサイエンティストも多く、トークショーに参加することで、データサイエンスの現状、雰囲気を味わうことができる。
トークショーはニコニコ動画で配信され、また過去の動画や、関連情報は「岩波データサイエンス・サポートページ」で見ることができる。

ということで、とても書評といえるような解説ではないが、内容が広範過ぎて、しっかり読んで書評を書くというのは最初からあきらめた。

関係者の末席に傍観者としてトークショーを聞きに行くくらいなのだ。
あ、忘れるところだった。弊社からも、毎回寄稿している。普段は2ページなのだが、第2巻では長いのを寄稿していた。

本シリーズの内容のレベルの高さ、質などを考えると、なぜ増刷を重ねるほど売れてしまったのか、これが一番の謎である。
たぶん、データサイエンティストを目指している人がとても多いのではないか推察している。
実際、データサイエンスがらみのショーに行くと、データサイエンティストという人がいて、いろいろコンサルしますという場面に去年くらいから出くわすことが多くなった。

次号、Vol.5 は、特集「スパースモデリングと多変量データ解析」で、2月中旬に発売のはずだ。
前回、Boardクラスの説明をしたが、実はそれでほんとんど準備は済んでいる。

前回のBoardクラスを利用することで、問題を解くのがSolverクラスで、初期化と解くクラスのたった2つのメソッドがあるだけ。とても簡単である。

まず、コンストラクタについて。

class Solver:
    def __init__(self,board):
        self.board = board
        self.searchorder = self.board.makeblanklist()
問題が入った状態のBoardオブジェクトを与えて初期化が行われる。
このとき、問題の空きマスのリストをsearchorderに入れる。
searchorderは、名前の通り、マスをどの順番で調べるか(埋めていくか)の情報が入っている。

で、次に、問題を実際に解くメソッド solveである。

    def solve(self,idx):
        if idx == len(self.searchorder):
            self.board.print()       # 解けた! 解のプリント
            return
        x,y = self.searchorder[idx]
        possibles = self.board.possibles(x,y)
        for c in possibles:          # 可能な数字を順番に試す
            self.board.setnum(x,y,c)
            self.solve(idx+1)
            self.board.rmnum(x,y,c)       
solveには引数idxがあるが、このidxは最初に作った空きマスリスト(searchorder)の何番目の要素(空きマス)を次に調べるかを伝えている。
メインからは、
    Solver(bd).solve(0)
と呼ばれていたが、solve(0)で、searchorderの最初のマスを試すことになる。
もし、searchorderを全部使いきっていたら全部埋まっているはずなので解が出来上がっているはずなのでプリントする。
そうでなければ、次に数字を試すマス(x,y)を求め、マス(x,y)に入れることができる数字のリストをpossiblesとし、可能な数字すべてについてforループで調べる。
forループの中は、ます(x,y)に調べている数字cを置いて、次の空きマスを指示するためにidx+1を引数にして再帰呼出しをする。
戻ってきたら、元の状態に戻すために、マス(x,y)からcを取り除く。

これだけで、ちゃんと動く。
再帰を使えば、簡単である。

次の盤面は途中の状態をプリントしたものである。
4 1 7 8 5 2 6 3 9 
5 2 8 9 6 3 7 4 1 
6 3 9 1 7 4 8 5 2 
1 7 4 2 8 5 3 9 6 
2 8 5 3 9 6 4 1 7 
3 9 6 4 1 7 5 2 8 
7 4 1 5 2 8 9 6 3 
9 5 2 6 3 1 _ 7 _ 
_ _ _ 7 _ _ _ 8 _ 
最初の空きマス(_)は、(7,6)のマスであるが、ここには1〜9のいずれも入れられないので、再帰はこの先に進まず、戻っていく。
ということで、ナンプレを解くプログラムの説明は終える。

なお、実際にナンプレを解くプログラムを作る場合、このような再帰呼出しで虱潰しはしない。
これでは難易度が分からないし、それに遅い。
また、各マス、各グループ(タテ列、ヨコ列、ブロック)に何が入っているかを集合で実現したが、もちろん集合は遅いので使わないのが普通だ。
実際のナンプレ関連のプログラムでは、ビット演算を多用し高速化を実現する。
また、使った数字を集合に入れていたが、実際は使える数字(まだ使っていない数字=候補)を管理することで解いていく。

9x9のナンプレを解くのはとても簡単で、プログラミング初歩の練習問題である。
もうちょっと頑張ってみたい場合は、16x16、25x25の問題を解くプログラムを作ってみよう。
あるいは、ナンプレを自動生成するプログラムを作ってみよう。

正月も終わったので、この正月特集もこれで終わる(完)
盤面をクラスとして書く部分を今日は紹介する。
 クラス名はわかりやすく、Boardとした。
そして、最初に5つのメンバー変数を用意した。
class Board():
    board = {}                             # ナンプレ問題盤面 (x,y):n
    hconst = [set() for i in range(9)]     # ヨコ制約
    vconst = [set() for i in range(9)]     # タテ制約
    bconst = [set() for i in range(9)]     # ブロック制約
    numbers = {1,2,3,4,5,6,7,8,9}          # 利用可能数字
boardは辞書で、(x,y)に数字nが入っていることを、(x,y):n で示す。
hconstのconstは定数ではなく制約constraintの省略形である。
ヨコの制約が9組、タテの制約が9組、ブロックの制約が9組あるのを、集合のリストで表現し、使われている数字を集合に入れる。
1から9までの数字の集合があった方が便利そうなので、numbers を作った。

あとは、メソッドを色々用意した。

Boardの初期化は、最初から数字のあるところをリストでもらい、setnumで順番にその数字を盤面にセットしていく。これで、初期化を終えることにする。

問題を解くために、数字の入っていないマスをリストで持っておき、そのリストを見ながら数字を埋めたり剥いだりするとよい。そのために数字の入っていないマスのリストを作るのがmakeblanklistメソッド。

xy2bは、(x,y)のマスが属するブロックの番号を返す。
 
isusedは、(x,y)に数字nを入れられるかどうかを調べる。

    def __init__(self,hint):
        for x,y,n in hint:
            self.setnum(x,y,n)

    def makeblanklist(self):
        return [(x,y) for y in range(9) for x in range(9) if (x,y) not in self.board]

    def xy2b(self,x,y):  return  x//3*3+y//3
        
    def isused(self,x,y,n):
        return (n in hconst[x]) or (n in vconst[y]) or (n in bconst[xy2b(x,y)])
setnumは、(x,y)に数字nをセットする。盤面boardの(x,y)にnを入れる。

さらに、タテ、ヨコ、ブロックの制約にもnを追加しておく。

 rmnumは、setnumの逆操作を行う。

    def setnum(self,x,y,n):
        self.board[(x,y)] = n
        self.vconst[x].add(n)
        self.hconst[y].add(n)
        self.bconst[self.xy2b(x,y)].add(n)

    def rmnum(self,x,y,n):
        self.board.pop((x,y))
        self.vconst[x].remove(n)
        self.hconst[y].remove(n)
        self.bconst[self.xy2b(x,y)].remove(n)
possiblesは、(x,y)に入れられる数字の集合を返す。

 getは、盤面のboard[(x,y)]に入っている数字を返すのだが、存在しないとエラーになるので、存在チェックが行われている。
    def possibles(self,x,y):
        return  self.numbers - (self.vconst[x]|self.hconst[y]|self.bconst[self.xy2b(x,y)])

    def get(self,x,y):  
        return self.board[(x,y)] if (x,y) in self.board else 0
盤面をプリントするメソッドがprintである。説明の必要はないであろう。
    def print(self):
        for y in range(9):
            print()
            for x in range(9):
                n = self.get(x,y) 
                print((str(n) if n!=0 else '_')+' ',end='')
        print()
これだけ道具を用意し、あとは次回、解くためのクラスSolverを説明する。
新年明けましておめでとうございます

本年も技術的に尖ったこと、変なこと、色々紹介できればと思っております。

DSCF5095 (300x400).jpg       DSCF5098 (300x400).jpg


VS人工知能難問ナンプレ.jpg正月休みということで、変なプログラミング三昧のエンジニアも多いかと思いますが、
ちょっとプログラミングの話はお休みにして、プログラムを使って作っているものを紹介します。

右の写真は、この12月16日に発売になったばかりの『VS人工知能難問ナンプレ』です。
このナンプレ問題集は、タイトルにもあるように実際に人工知能、要するにプログラムを使って自動生成して作りました。

というより、我々というか、パズルの問題の既に多くの問題が人工知能技術により自動生成されています。将棋、囲碁が人工知能の脅威にさらされている昨今ですから、パズルの問題が人工知能によって作られていることに何の不思議もないでしょう。

パズルの問題は人間が作るから良いという人も未だにいますが、もう遠い過去の思い出になってしまいました。人工知能が作った問題とパズル作家が頑張って作った問題の区別はできません。いや、凄い問題の方が人工知能で、普通のが作家という判断はかなり正しいのです。これは、囲碁や将棋で、人工知能が指す手が意味不明でプロ棋士も解説できないけれど、結局人工知能が勝ってしまうのと同様といえます。

とくに本書は、パズル作家と呼ばれる人々ではほとんど作るのが困難なような問題をできるだけ多く入れています。
問題の数字の個数(ヒント数)が少ないだけの問題集は他にもありますが、ヒント数が少ない状態で難易度をきちんと調整し、配置にも美を重視しています。

ヒント数が少ないと必ず難問になるという誤解も多いですが、そんなことはありません。難易度の調整が難しくなるだけで、本書でも、全部が難問ではなく、かなりやさしい中級レベルの問題から、本当に難しい問題まで、人工知能によりバランスよく作らせています。

今は、人工知能と言うと何でもディープラーニングという考えがありますが、パズル問題の自動生成は別のタイプの人工知能を使うのが一般的です。
人工知能は生物、人間をモデルにすることが多いのですが、超大雑把に言って、脳をモデルにしたのがディープラーニングで、生物の進化をモデルにしたのが進化的計算で、なかでも遺伝的アルゴリズムが有名です。遺伝的アルゴリズムはアルゴリズムや人工知能の授業でも普通に教えられることで、そのタイプの人工知能を利用してこの問題集も作られました。

Pythonでナンプレを解く方法を書いている最中ですが、ナンプレを作るにはナンプレを解くプログラム(ソルバー)が必要ですが、問題作成中にソルバーを延々と呼び出すので、ソルバーはできるだけ高速でないといけません。そのため、Pythonは使っておらず、JavaやC/C++を利用しています。まあ、1ミリ秒程度で問題を解けないと、良い問題集を作るのは無理でしょう。

まあ、そういう背景を知った上で、本書で正月休み、さらにはその後の暇つぶしに本書を利用していただければ嬉しいかぎりです。あるいは、お年寄りのボケ防止にもなるでしょう。とくに母親がパズル好きというパターンは非常に多くなっています。親孝行にぜひ1冊いかがでしょうか。

最初の2枚の写真は、本ができて送られてきた200冊の本をつかって、パズルタワーを作ったところです。
昔、大手書店のスーパー書店員が多数売りたい本をこんな風に積み上げていたのを思い出して、つい作ったものです。
本書を入手希望の方は、弊社入り口ロビーにこのタワーがありますので、タワーが倒れないように1冊持っていってください。
万一倒れた場合には、積み直しておいていただければ助かります。








このアーカイブについて

このページには、2017年1月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2016年12月です。

次のアーカイブは2017年2月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。