線形回帰を勾配降下法を使って解いてみたメモ。 問題設定 $\bm{y} = (y^{(1)}, y^{(2)}, \ldots, y^{(N)})^T,\ \bm{x}_i = (1, x_1^{(i)}, x_2^{(i)}, \ldots, x_D^{(i)})^T$ とおく。$(\bm{x}_i, y_i),\ i = 1, 2, \ldots, N$ がデータとして与えられている。このとき、入力と出力の間に $$ \begin{aligned} y &= h_{\bm{w}}(\bm{x})\\ &:= w_0 + w_1x_1 + w_2x_2 + \cdots + w_Dx_D\\ &= \bm{w}^T\bm{x} \end{aligned} $$ が成り立つと仮定し、これに適する$\bm{w}$を見つけたい。「適する」とは具体的に何なのかというと、ここでは予測とデータとの二乗誤差の和 $$ J(\bm{w}) = \frac{1}{2} \sum_{i=1}^{N} (h_{\bm{w}}(\bm{x}_i) - y^{(i)})^2 $$ が最小となる $\bm{w}$ を求める。この $J$ については呼び名がいくつかあるが、ここではコスト関数と呼ぶ。 係数 $1/2$ は微分した時に出てくる $2$ を消し去るための便宜的なものであり、つける必然はない。 コスト関数の勾配 $w_j$に関する偏微分を計算すると、 $$ \frac{\partial J(\bm{w})}{\partial w_j} = \sum_{i=1}^{N} (h_{\bm{w}}(\bm{x}_i) - y^{(i)})x_j^{(i)},\ j = 0, 1, \ldots, D $$ ...

学校の授業で勉強はしたが、自分で考えてまとめたことはなかったのでここに記しておく。 問題設定(1) $\bm{y} = (y^{(1)}, y^{(2)}, \ldots, y^{(N)})^T,\ \bm{x}_i = (1, x_1^{(i)}, x_2^{(i)}, \ldots, x_D^{(i)})^T$ とおく。$(\bm{x}_i, y_i),\ i = 1, 2, \ldots, N$ がデータとして与えられている。このとき、入力と出力の間に $$ \begin{aligned} y &= h_{\bm{w}}(\bm{x})\\ &:= w_0 + w_1x_1 + w_2x_2 + \cdots + w_Dx_D\\ &= \bm{w}^T\bm{x} \end{aligned} $$ が成り立つと仮定し、これに適する$\bm{w}$を見つけたい。「適する」とは具体的に何なのかというと、ここでは予測とデータとの二乗誤差の和 $$ J(\bm{w}) = \frac{1}{2} \sum_{i=1}^{N} (h_{\bm{w}}(\bm{x}_i) - y^{(i)})^2 $$ が最小となる $\bm{w}$ を求める。この $J$ については呼び名がいくつかあるが、ここではコスト関数と呼ぶ。 係数 $1/2$ は微分した時に出てくる $2$ を消し去るための便宜的なものであり、つける必然はない。 コスト関数の最小値を求める(1) コスト関数の行列表現 まず $J$ を行列だけで表現してみる。 $$ \begin{aligned} J(\bm{w}) &= \frac{1}{2} \sum_{i=1}^{N} (\bm{w}^T\bm{x}_i - y^{(i)})^2\\ &= \frac{1}{2} \sum_{i=1}^{N} (\bm{x}_i^T\bm{w} - y^{(i)})^2\\ &= \frac{1}{2} \begin{pmatrix} \bm{x}_1^T\bm{w} - y^{(1)}\\ \bm{x}_2^T\bm{w} - y^{(2)}\\ \vdots\\ \bm{x}_N^T\bm{w} - y^{(N)}\\ \end{pmatrix}^T \begin{pmatrix} \bm{x}_1^T\bm{w} - y^{(1)}\\ \bm{x}_2^T\bm{w} - y^{(2)}\\ \vdots\\ \bm{x}_N^T\bm{w} - y^{(N)}\\ \end{pmatrix}\\ &= \frac{1}{2} \left( \begin{pmatrix} \bm{x}_1^T\bm{w}\\ \bm{x}_2^T\bm{w}\\ \vdots\\ \bm{x}_N^T\bm{w}\\ \end{pmatrix} - \bm{y} \right)^T \left( \begin{pmatrix} \bm{x}_1^T\bm{w}\\ \bm{x}_2^T\bm{w}\\ \vdots\\ \bm{x}_N^T\bm{w}\\ \end{pmatrix} - \bm{y} \right) \end{aligned} $$ ここで、 ...

英語だと “bouncing ball programming” とか検索すると出てくるやつ。 単にボールが弾むだけなのだが、思ったより勉強になったので書き残す。 実際のプログラムの動作はGitHub Pagesを参照。 プロジェクトの初期化 適当なディレクトリを作って、その中でプロジェクトを作成。 % spago init % spago build 今回は、追加のパッケージは必要なときにspago installコマンドで入れることにする。 Canvas入門 src/Main.pursを以下のようにする。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 module Main where import Prelude import Data.Maybe (Maybe(..)) import Effect (Effect) import Effect.Console (log) import Graphics.Canvas (CanvasElement, Dimensions) import Graphics.Canvas as Canvas import Math as Math canvasDimen :: Dimensions canvasDimen = { width: 600.0 , height: 600.0 } initCanvas :: CanvasElement -> Effect Unit initCanvas canvas = Canvas.setCanvasDimensions canvas canvasDimen main :: Effect Unit main = Canvas.getCanvasElementById "canvas" >>= case _ of Just canvas -> do initCanvas canvas ctx <- Canvas.getContext2D canvas Canvas.fillPath ctx $ Canvas.arc ctx { x: canvasDimen.width / 2.0 , y: canvasDimen.height / 2.0 , start: 0.0 , end: Math.tau , radius: 10.0 } Nothing -> log "Error on getCanvasElementById." ビルドに当たって，必要な以下の3つのパッケージをインストールする。 ...

シンプルなToDoリストのWeb APIを作る。 今までWSGIの仕様のみ、Werkzeug の2通りで実装したが、今回はFlaskといくつかのライブラリを使う。使うのは以下の通り。 Flask: WSGIアプリフレームワーク。 peewee: ORMライブラリ。 marshmallow: データの変換やvalidationをするためのライブラリ。 Flaskとは WSGIのWebアプリを作るためのフレームワーク。 フレームワークであるため、Flaskが用意した作法に従ってコードを書くことで比較的手軽にWebアプリが作成できる。 前回との比較でいうならば、例えばルーティングの仕組みをプログラマが書く必要はない。これはFlaskに備わっている。 Djangoのようなフレームワークとは違って、持っている機能は少ない。必要に応じて外部ライブラリを組み合わせる。 例えば、Djangoではデフォルトでデータベースの仕組みが内蔵されているが、Flaskにはない。その代わりに、 データベースのライブラリとしてsqlite3やSQLAlchemy、peeweeなど、好きなものを用いれば良い。 ToDoリストAPIの仕様 今回ToDoのデータは以下キーと値を持つJSONデータとする。 key value id ID content ToDoの内容 created_at 作成日時 (ISO8601) updated_at 更新日時 (ISO8601) APIの仕様は以下の通り。 URL Method 説明 返却値 /todo/ GET 全てのToDoを取得。 ToDoのデータのリスト /todo/ POST ToDoを作成。 なし (LocationヘッダにそのToDoへのURLを乗せる) /todo/<todo_id> GET todo_idのidを持つToDoを取得。 ToDoのデータ /todo/<todo_id> PUT todo_idのidを持つToDoを変更。 なし /todo/<todo_id> DELETE todo_idのidを持つToDoを削除 なし データはSQLiteで管理する。 雛形 todo_listディレクトリを作成。todo_list/__init__.pyを以下のようにする。 1 2 3 4 5 6 7 8 9 10 11 from flask import Flask def create_app(): app = Flask(__name__) @app.route('/') def hello(): return 'Hello, World' return app exportコマンドで環境変数を設定する。 ...

シンプルなToDoリストのWeb APIを作る。 前回はWSGIの仕様のみを参考にして作ったが、 今回はWerkzeugというライブラリを利用する。 Werkzeugとは Werkzeugのドキュメントの “Werkzeug is a comprehensive WSGI web application library.“という文面にもある通り、 これはWSGIのWebアプリを作るためのライブラリである。 あくまでフレームワークではなく、ライブラリであることに注意する。 Webアプリを作るうえで、便利なクラスや関数が用意された「道具箱」のようなイメージを持つとよいかもしれない (そもそも"werkzeug"という単語はドイツ語で「道具」という意味)。 あくまで道具があるだけなので、どういう設計を行うかなどを考える余地がある。 ToDoリストAPIの仕様 前回と同じだが、再掲する。 簡単のため、今回ToDoのデータはidと内容のみ持つデータとし、{ id: 0, "content": "やること" }というJSON形式とする。 APIの仕様は以下の通り。 URL Method 説明 返却値 /todo/ GET 全てのToDoを取得。 ToDoのデータのリスト /todo/ POST ToDoを作成。 なし (LocationヘッダにそのToDoへのURLを乗せる) /todo/<todo_id> GET todo_idのidを持つToDoを取得。 ToDoのデータ /todo/<todo_id> PUT todo_idのidを持つToDoを変更。 なし /todo/<todo_id> DELETE todo_idのidを持つToDoを削除 なし データは最終的にはSQLiteで管理する。 雛形 app.pyを以下のようにする。 1 2 3 4 5 6 7 8 9 10 11 from werkzeug.wrappers import Response def app(env, start_response): response = Response('Hello, World') return response(env, start_response) if __name__ == '__main__': from werkzeug.serving import run_simple run_simple('127.0.0.1', 5000, app, use_debugger=True, use_reloader=True) 以降、サーバーを起動する際はpython3 app.pyを実行する。 ...

シンプルなToDoリストを作る。 今回は勉強のため、Webアプリケーションフレームワークは使わずに、 敢えてWSGIの仕様のみ参考にして書く． WSGIとは WSGIとは、WebサーバーとWebアプリとの間の標準的なインターフェース。 WSGIの仕様に沿ってWebアプリを作れば、 WSGI対応のどんなWebサーバーとも連携することができる。 WSGIの仕様はPEP3333に書かれている． ToDoリストAPIの仕様 簡単のため、今回ToDoのデータはidと内容のみ持つデータとし、{ id: 0, "content": "やること" }というJSON形式とする。 APIの仕様は以下の通り。 URL Method 説明 返却値 /todo/ GET 全てのToDoを取得。 ToDoのデータのリスト /todo/ POST ToDoを作成。 なし (LocationヘッダにそのToDoへのURLを乗せる) /todo/<todo_id> GET todo_idのidを持つToDoを取得。 ToDoのデータ /todo/<todo_id> PUT todo_idのidを持つToDoを変更。 なし /todo/<todo_id> DELETE todo_idのidを持つToDoを削除 なし データは最終的にはSQLiteで保存するが、最初は単純にlistで扱う。 雛形 まずはサーバーを作る。この時点ではルーティング処理を書いていない。 どのようなリクエストをしてもHello, Worldをレスポンスとして返す。 1 2 3 4 5 6 7 8 9 10 11 from wsgiref.simple_server import make_server def app(env, start_response): start_response('200 OK', [('Content-type', 'text/plain; charset=utf-8')]) return [b'Hello, World.'] if __name__ == '__main__': httpd = make_server('', 5000, app) httpd.serve_forever() 以降、サーバーを起動する際はpython3 app.pyを実行する。 ...

1年以上前に書いた記事 で、HTTPサーバーもどき(リクエストを読まず、ただ一方的にレスポンスを返すだけのサーバ)を書いた。 今回はもう少しだけこれを進化させる。 動機 非常にどうでもいいのだが動機を記しておく。 Land of Lispの13章でソケット通信が出てきた。 Land of Lispで扱っているCommon Lispの処理系がCLISPなのに対し、今自分が利用しているのはSBCLなので、 本文中のコードが動かない。そこで色々調べて、usocketを利用しようと思いつく。 その後なんとか書き上げる。ところがChromeやcurlでは動くのに、Safari(現バージョンは14.0.2)では動かない。ページを読み込んだ後、タイムアウトしたかのような挙動を起こす。 その理由を明らかにしたくて「そもそもLisp以外では動くのか。例えばPythonのソケット通信では動くのか」「PythonのWebアプリ、例えばFlaskの開発用サーバーで動くのはなぜか」 など色々調べた。cpythonのsocketserverやhttp.serverなどのソースコードも読んだ。 調べた結果、どうやらSafariがたまに「何も送らない通信(?)」を行うことが原因だった。 何も送ってくれないと、リクエストをrecvで受け取るときに、ブロッキングが働いてサーバー側が固まってしまう。 ただし普通のリクエストも送ってくるので、マルチスレッドなどの多重化を行なっておけば 問題なくSafariでもページが読み込まれる。なのでFlaskの開発用サーバーでは大した問題にならなかった。 Safariがなぜこんな通信をするのかはよく分からない。HTTPの仕様をちゃんと読んでいないので、何か見落としがあるのだろうか。もしくはバグか何かなのか。 何はともあれ、色々ソースコードを読んでいくうちに、リクエストヘッダの取得のやり方など参考になった。 せっかくなのて得た知見を元に再びHTTPサーバを作ってみようと思い立った。 作るもの 以下の条件を満たすHTTPサーバのようなものを作る(そもそも、どこまで実装できたらHTTPサーバと呼べるのだろうか)。 マルチスレッドにする。 HTTPリクエストのリクエストライン、ヘッダ情報をパースする。 リクエストボディは今回は考慮しない。 前回に比べてPythonについての知見が広がったため、 コードにおいてf-stringsやtype-annotation、dataclassなどの機能を使ってみている。 また処理を細かく関数に分ける。 listen用のソケットの作成 待ち受け用のソケットを作成し、それを返す関数を作成する。 bindやlistenは前回説明した通り。 動作確認を何度も行う都合上、TIME_WAIT状態のポートを待つのは面倒なので、setsockopt(...)の記述でそれを解決している。 (この辺りの詳細は"TIME_WAIT"とか"REUSEADDR"あたりのキーワードで検索すれば出てくる) 1 2 3 4 5 6 7 8 9 import socket def server_socket(port: int): soc = socket.socket(socket.AF_INET, socket.SOCK_STREAM) soc.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, True) soc.bind(('', port)) soc.listen(5) return soc 動作確認 以下のようにrun_serverを作る。 1 2 3 4 5 6 7 8 9 10 def run_server(port: int): with server_socket(port) as soc: while True: conn, addr = soc.accept() print(f'Connected: {addr}') with conn: conn.shutdown(socket.SHUT_RDWR) if __name__ == '__main__': run_server(8080) 作ったサーバーを実行し、別の端末でcurl localhost:8080とすると、サーバー側で以下のようなメッセージが出力される。 60724の部分は実行の度に異なる。 ...

平綴じ印刷ができるように、PDFの順序を入れ替えたり、空白ページを挿入するプログラムを書いた。 方法1はPython + いろんなコマンドで、方法2はPythonのPDFライブラリであるPyPDF4を利用した方法。 実装してみた結果、後者が圧倒的に簡単だった。 動機 平綴じがしたい場面が出てきたが、印刷機に専用の設定が見つからなかった。 なので平綴じになるようにPDFのページ順を1,2,3,4,5,6,7,8,…から4,1,2,3,8,5,6,7,..に変え、それをプリンタで両面刷り(短辺綴じ)・2ページ割付で印刷することを考えた。 平綴じの場合、紙に両面4ページずつ印刷されることになる。するとPDFのページ数は4の倍数でなくてはならない。よって、4の倍数でなかった場合はその分を空白ページで埋めなければならない。 PDFファイルの準備 テスト用にPDFファイルを作っておく。ここはなんでも良いのだが、とりあえず以下のLaTeXのコードから10ページのPDFファイルを作る。名前はinput.pdfとしておく。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 \documentclass{jsarticle} \begin{document} \centering \Huge 1 Page \newpage 2 Page \newpage 3 Page \newpage 4 Page \newpage 5 Page \newpage 6 Page \newpage 7 Page \newpage 8 Page \newpage 9 Page \newpage 10 Page \end{document} 方法1：Python + 諸々のコマンドの利用 方針 PDFのページ順を変えるためには、pdftkコマンドを利用すれば良い。pdftkは、Homebrewならbrew install pdftk-javaで使えるようになる)。例えば8ページのPDFファイルinput.pdfを並び替えるなら次のコマンドで可能。 ...

PureScriptで配列のシャッフルをしたい。型はこんな感じ。乱数は副作用を伴うため、返り値の型はEffectで包まれる。 1 shuffle :: forall a. Array a -> Effect (Array a) アルゴリズムはFisher-Yates ShuffleのModern Algorithmの項の2つ目を利用する。これをさまざまな方法で作成したところ、Functor, Applicative, Monadなどに関連する事項だったり、STモナドの使い方、FFIの使い方だったりが学べたので、備忘のために書く。 準備 適当なディレクトリでプロジェクトを作成する。今回使うパッケージをインストールする。 $ spago init $ spago install arrays $ spago install random $ spago install foldable-traversable 方法1: 素直(?)な書き方 ここでは、src/Shuffle.pursに記述する。 天下り的ではあるが、これから使う関数、型をimportしておく。 1 2 3 4 5 6 7 8 9 10 module Shuffle where import Prelude import Effect (Effect) import Data.Array (range, (!!), updateAt, length) import Data.Traversable (for) import Effect.Random (randomInt) import Data.Maybe (maybe) import Data.Foldable (foldr) まずは、「どの添字ととの添字の値を交換するか」という情報をもったデータExchangeIndexと、それを作成する関数exchangeIndiciesを作成する。 1 2 3 4 5 6 7 8 9 10 type ExchangeIndex = { i :: Int , j :: Int } exchangeIndicies :: Int -> Effect (Array ExchangeIndex) exchangeIndicies n = for (range 0 (n - 2)) \i -> do j <- randomInt i (n - 1) pure { i, j } 次に、ExchangeIndexの情報を元に配列を交換する関数exchangeを作成。配列の添字が不正だった場合(配列外参照を起こしそうなとき)は!!演算子がNothingを返すため、一連の計算はMaybeに包まれる。今回は簡単のため、交換に失敗したら元の配列をそのまま返すような実装にする。 ...

purescript-generics-repパッケージを使ってGenericなSerializer型クラスを作った。以下はそのメモ。 準備 プロジェクトを作成。 $ spago init Arrayを使うので、パッケージをインストールしてsrc/Main.pursにimport文を書き込んでいく。 本記事の本命であるgenerics-rep入れる。 $ spago install arrays $ spago install generics-rep 1 import Data.Array ((:)) REPLで色々実験するので、あらかじめ起動しておく。 $ spago repl > import Main 以降はsrc/Main.pursに色々書き足していく。REPLで:r(もしくは:reload)とコマンドを打てばモジュールが再読み込みされるので、src/Main.pursを書き換える度にこのコマンドを打つと良い。 Serializer そもそもSerializerとは何か。ここでは単に「データをビット列に変換するもの」程度の意味で捉えれば良い。 厳密にはJSONなどの階層を持つデータを，文字列などの平坦なデータに変換するという意味合いとしてシリアライズ(直列化)という言葉を使う。実際、本記事では最終的に木構造をシリアライズする。 まずビットは次のように定義する。 1 2 3 4 5 data Bit = O | I instance showBit :: Show Bit where show O = "O" show I = "I" Serializer型クラスを以下のように定義する。 1 2 class Serializer a where serialize :: a -> Array Bit 試しに適当な型をつくり、それをSerializer型クラスのインスタンスにしてみる。 1 2 3 4 5 6 data Person = Alice | Bob | Carol instance serializerUser :: Serializer Person where serialize Alice = [ I ] serialize Bob = [ O, I ] serialize Carol = [ O, O, I ] 余談。今回はデシリアライザは実装しないので、シリアライズしたデータを同じ形に戻せるかは考えない。このあたりは情報理論の授業で「一意復号化可能性」などをやった気がするけど、忘れてしまった。 REPLで実験してみる。 > serialize Alice [I] > serialize Bob [O,I] > serialize Carol [O,O,I] Tree型をSerializer型クラスのインスタンスにする(素朴な方法) 2分木のデータ構造であるTree型を作る。 ...