Posts

ニューラルネットワークノート - 誤差逆伝播の計算

誤差逆伝播法の数式の説明なんて世の中にたくさんあると思うが、理解のために自分でもまとめる。特に添字などのミスがあると思うので、見つけ次第修正する。誤差逆伝播の計算 (1) 問題設定入力を第 $0$ 層、出力を第 $L$ 層とする。ニューラルネットワークはよく次のようなグラフで描かれる。円がノードを表す。ノードに入っていく矢印が入力、出ていく矢印が出力を表す。第 $l$ 層 $j$ 番目のノードの出力を $y_j^l$ とおく (注意: この記事では $y_j^{l}$ の $l$ は添字を表すものとする。累乗ではない。これから現れる変数についても同様)。これはある関数 $f_l$ を用いて以下の式で表される。$f_l$ は活性化関数と呼ばれる。ただし、$u_j^{l}$ は前の層の出力を用いて計算される線形和で、以下のように定義される。このような、線形和を取って $f$ を適用するという流れは次のようなグラフで描かれる。この $\sum | f$ のノードがたくさん集まって第 $l$ 層を形成している。損失関数 $E$ は、重み$w_{ij}^{l}$ についての関数である。これは出力値 $y_i^{L}$ と教師データ $\tilde{y}_i$ との違いを測る尺度であるから、$y_i^{L}$ の関数でもある。例えば、以下の二乗誤差は損失関数の一種である。定義中に $w_{ij}^{l}$ が含まれていないじゃないか、と思うかもしれないが、$y_i^{L}$ の定義中に $w_{ij}^{L}$ が含まれている。さらにその中の $y_i^{L-1}$ 中に $w_{ij}^{L-1}$ が含まれている。以下同様にして $w_{ij}^l$ は $E$ の中に含まれている。 ...

PureScriptでパーサーコンビネータを触る (2) テキストファイル

前回の記事と合わせて1つの記事にする予定だったが、前回があまりに長くなってしまったので分割した。ある書式に従ったテキストファイルをパースすることを考える。パースしたデータを整形し、HTML文書として出力するところまでやる。前回インポートした関数で今回使うものは、(漏れが無ければ)以下の通り。 1 2 3 4 import Control.Alt ((<|>)) import Control.Lazy (defer) import Text.Parsing.Parser (Parser, fail) import Text.Parsing.Parser.String (char) テキストの仕様テキストファイルは、複数のentryで構成される。 1つのentryはタイトルtitleと中身bodyで構成される。 titleは[と]でくくられる。 titleとbodyの間、bodyと次のentryのtitleの間には、1つの改行と、0個以上の空行があり得る。それらはbodyには含まない。空行とは、0個以上のスペースだけから構成される行のことである。 BNF風に書くと次のようになるだろう。 1 2 3 4 5 6 <entries> = (0個以上の<entry>) <entry> = <title> "\n" <empty lines> <body> "\n" <empty lines> <title> = "[" (文字列) "]" <body> = (先頭、末尾が<empty lines>でないような文字列) <empty lines> = (0個以上の<empty line>) <empty line> = (0個以上のスペース) "\n" 例えば、以下のファイルがあったとする。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 [Title1] line1 line2 line3 line4 [Title2] line1 line2 [Title3] line1 line2 line3 これは次のようにパースされる。 ...

PureScriptでパーサーコンビネータを触る (1) 四則演算のパース

PureScriptのパーサーコンビネータにpurescript-parsingがある。これはHaskellのParsecが基になっているので、使い方はParsecとほとんど同じだと思われる(とはいえ、Parsecを使ったことはあまりない)。これを用いて四則演算のパーサーを実装してみたが、うまく動かず詰まる点がいくつかあった。その備忘録。パーサーコンビネータの準備 % spago install parsing 後々使うので以下のパッケージもインストール。 % spago install either integers maybe strings arrays lists src/Main.pursに以下の記述を追加。 1 2 3 4 import Text.Parsing.Parser (Parser) parser :: Parser String String parser = pure "Hello" REPLを起動して、動くか確認する。どんな文字列を食わせても"Hello"としか結果を返さないパーサーの完成。 > import Main > import Text.Parsing.Parser (runParser) > runParser "hoge" parser (Right "Hello") REPLでMain.pursをリロードする場合は:rをREPLで実行する。数字のパース 1文字取得 1文字の数字を読み取りたいなら、Text.Parsing.Parser.Tokenにdigitがあるのでそれを使う。 1 2 3 4 5 import Text.Parsing.Parser.Token (digit) parser :: Parser String Char parser = digit > runParser "12345" parser (Right '1') 1文字以上取得 1文字以上を取得したいなら、Data.Array.Someを使う。 1 2 3 4 5 import Data.Array as Array parser :: Parser String (Array Char) parser = Array.some digit > runParser "12345" parser (Right ['1','2','3','4','5']) 0文字以上の場合はData.Array.manyを使えば良い。ただし、この関数は実装で(:)を使っている。この計算量は O(配列の長さ) のため(参考)、もし効率を重視したいのであればData.List.manyもしくはData.List.someを使えば良い。 ...

モンテカルロ法による積分

今年の7月くらいに書き始め、存在をすっかり忘れていた記事をUP。モンテカルロ法でどうやって積分計算をするのか、重点サンプリングとはどのようなものなのかついて勉強したので、そのメモ。一般論 $$ \begin{aligned} \int_{\Omega_0} f(x) dx &= \int_{\Omega_0} \frac{f(x)}{p(x)}p(x)dx\\ &= \mathbb{E}\left[\frac{f(x)}{p(x)}\right] \end{aligned} $$ ここで、$p$ は確率密度関数。上の $\mathbb{E}$ が期待値であるためには、 $$ \int_{\Omega_0} p(x) dx = 1 $$ である必要がある。大数の法則より、確率分布 $p$ に従う標本 $x_n\ (n = 1, 2, \ldots, N)$ に対して、$N$ が十分大きければ、 $$ \mathbb{E}\left[\frac{f(x)}{p(x)}\right] \simeq \frac{1}{N} \sum_{n=1}^{N} \frac{f(x_n)}{p(x_n)} $$ となるから、結局、 $$ \begin{aligned} \int_{\Omega} f(x) dx \simeq \frac{1}{N} \sum_{n=1}^{N} \frac{f(x_n)}{p(x_n)} \end{aligned} $$ と近似できる。ちなみに、$p(x_n) = 0$ なる $x_n$ が選ばれることは絶対に無い(確率0だから)。よって分母が0になることを心配する必要はない。定義域を広げる $p$ の定義域をもう少し広げられる。$\Omega \supset \Omega_0$ であれば、集合$A$に関する指示関数を $\bm{1}_A$ と書くことにして、 ...

Neovimのプラグインを初めて作る - REPLの操作

動機研究で使っているソフトウェアのREPLが少し使いづらい。というのも、制御文字がそのまま表示されてしまうため、十字キーのカーソル移動やCmd + Aの行先頭移動、Cmd + Kの行削除など効かないからだ。 rlwrap を使えばこの問題を解決できるのだが、別の解決案としてNeovimのREPL支援プラグインを作ってみようと思い立った。 Neovim のターミナル機能を使ってREPLを起動し、別バッファー上で入力した文字列をREPLに送るようなプラグインを作りたい。 GitHubで検索してみると同様の機能を実現するプラグインはいくつもあるようだが(例えば、vim-slime)、プラグインを作る勉強として、自分で作ってみる。提供する機能使用感をvlimeと似たものにしたい。キーマップは次のようにする。 <LocalLeader>ss カーソル下の行をREPLに送る。 <LocalLeader>s 選択範囲内行の文字列をREPLに送る。 <LocalLeader>i 1行入力用のバッファを表示し、そこで書いた文字列をREPLに送る。 <LocalLeader>cd Ctrl + DをREPLに送る。 <LocalLeader>cc Ctrl + CをREPLに送る。その他、以下のコマンドを定義する。 ReplOpen [cmd]: REPLを起動する。例えばReplOpen pythonならpythonのREPLが起動する。 [cmd]には任意のコマンドが入れられるため、REPL支援というよりターミナル支援プラグインという感じがするが、気にしないことにする。 ReplSend [string]: 文字列[string]をREPLに送る。補足 vlimeとキーマップが被るため、vlimeを入れている人はどうするんだという事になる。その場合、キーマップが被らないようにしたり、ftplugin下にスクリプトを書くなど色々と方法が考えられる。ここでは一番無難そうな、「ReplOpenが呼び出された時にキーマップを登録する」という方法を採用する。注意普段使っているのがVimではなくNeovimなので、Neovimを使ってプラグインを書く。Vimには無い関数/機能を使うので注意。あとVim scriptをほとんど書いたこと無いため、今回載せるコードには色々改善点があるだろう。準備適切なディレクトリにプラグインのディレクトリを作成。自分の環境では、packpathの1つに~/.config/nvimがあったので、 ~/.config/nvim/pack/plugins/start/に置く。プラグインのディレクトリは愚直にrepl.nvimとするそこにautoload、plugin、ftpluginディレクトリを作成する。 1 2 3 4 5 6 7 8 9 repl.nvim | +-- autoload/ | | | +-- repl.vim | +-- plugin/ | +-- repl.vim REPLの起動 autoload/repl.vimに色々関数を定義する。まずはREPLの起動から。ウインドウを分割し、ターミナルを起動し、コマンドcmdを実行する関数は素朴には以下のように書ける。 1 2 3 4 function! repl#open(cmd) abort vnew call termopen(a:cmd) endfunction 「a:変数名とかs:変数名って何？」と初めは思ったが、これの答えは:h internal-variablesにある。 a:は関数の引数を表し、s:はこのスクリプト内の変数を表す。 ...

Web Audio API 備忘録

Web Audio APIで色々遊んだメモ。サイン波を鳴らす HTMLファイルを作成。適当にindex.htmlとしておく。 1 2 3 4 5 6 7 8 9 <html> <head> <meta charset="utf-8"> </head> <body> <button id="play_btn">play</button> <script src="script.js"></script> </body> </html> script.jsは以下のようにしておく。 1 2 3 4 5 6 7 8 const audioContext = new AudioContext(); const oscillatorNode = audioContext.createOscillator(); oscillatorNode.connect(audioContext.destination); document.getElementById('play_btn') .addEventListener('click', function() { oscillatorNode.start(); }, false); これで、“play” ボタンを押すとサイン波が再生される(音量に注意)。説明 Web Audio APIの枠組みでは、色々な音やエフェクトをノードとして繋いでいく。最終的な出力を担うノードはAppContext.destinationである。まずAudioContextのインスタンスを作成する。このContextというのはプログラミングをやっていると色々なところで現れるが (Canvas要素に描画する際にもgetContextが出てくるし、WinAPIだとデバイスコンテキストハンドル、AndroidアプリのプログラミングでもContextがある)、自分は「Audioについて色々な情報を提供してくれるオブジェクト」くらいの理解をしている。 1 const audioContext = new AudioContext(); 続いて、音源としてOscillatorNodeを作成し、繋いでやる。 1 2 const oscillatorNode = audioContext.createOscillator(); oscillatorNode.connect(audioContext.destination); oscillatorNode.start()で実際に音源が再生される。今回はclickイベントが起こったときに再生されるようにしている。 (補足) ページ読み込み時の再生はできないという仕様 Chrome/Safariの場合、以下のようにページを開いた瞬間に音がなるようなコードを書いたとしても、実際には鳴らない。 1 2 3 4 const audioContext = new AudioContext(); const oscillatorNode = audioContext.createOscillator(); oscillatorNode.connect(audioContext.destination); oscillatorNode.start(); これは、「ボタンが押す」のような、ユーザーが明示的な操作をしない限り再生されない仕様となっているかららしい。実際 Chrome の場合、上のコードを書くと以下の警告がDevalopper Toolで表示される。 ...

Pythonを使った(静的)ページの画像のURL取得

Webページの画像だけを手っ取り早く取得したい場合にどうすれば良いのかを考えた。これを行うプログラムをPythonで取得する。この記事で作成したプログラムはGitHubのRepositoryに公開した。前提 Pythonのバージョンは3.10を想定。この記事では外部ライブラリとして Requests 2.26.0 Beautiful Soup 4.10.0 tqdm 4.62.3 w3lib 1.22.0 を使う。この記事のコードを動かす場合はpipコマンドなどでインストールしておく。方針やることは案外単純である。 WebページのHTMLデータを取ってくる。 img要素を探して、そのsrc属性を取ってくる。 scheme、netlocが無かったらそれを付加して、完全なURLにする。 1はRequests、2はBeautiful Soupを使えば良いだろう。 3は思ったより複雑である。src属性に入っているパスには、 URL: http://foo.org/bar/hoge.png スキームが省略されている: //foo.org/bar/hoge.png 絶対パス: /bar/hoge.png 相対パス: ../bar/hoge.png データURL: data:image/png;base64,... など色々ある。これらのフォーマットを統一して完全なURLにするのは面倒であるが、幸運にもurllib.parse.urljoinという関数があったのでこれを使う (余談: 初め、urljoinの存在を知らずに自前でURLの変換機能を実装してしまった。学びにはなったが時間を費やした…)。ついでの機能として、「特定の要素の中に含まれているimg要素のURLを取得する」ことも考える。これはCSSセレクタとして指定できるようにする。まとめると、画像のURLを取得する関数は以下のようなインターフェースとなる。 1 2 def get_img_urls(url: str, selector: Optional[str]=None) -> list[str]: pass # これから実装する URLとセレクタを引数にとり、img要素のURLのリストを返す関数である。ついでに画像ダウンロードのためのCLIや、画像を閲覧するWebアプリなどが作れたら良い。プロジェクトの構造 Pythonでモジュールを作ったことがないため、正しい作り方が分からないが、とりあえず以下のような構成にしてみる。細かいディレクトリの構成は各節で述べる。 1 2 3 4 5 6 7 8 9 10 11 12 /project | +--+ getimg/ | +--+ commandline/ | +--+ viewer/ | +--+ tests/ +-- __init__.py +-- test_getimg.py +-- test_commandline.py CLI CLIの書式は以下のようにする。取得したい画像のあるページのURL、及び画像のダウンロード先を指定する。 ...

neovimのプラグインがうまく動かなかったので原因を探した話

(2021/12/25追記) この記事で話題にした問題は最新のddc-nvim-lspで修正されている。こちらのissue及びこちらのcommitを参照。もっとも、この記事を書いてから大分経ったため、ddc_nvim_lsp.luaのソースコードも今では大分変わっている。以下の文章のまとめバージョン違いには注意する ddc-nvim-lspは2021/10/1時点では、neovim 0.5.0を想定して作られているプラグインである。しかし自分はneovim 0.5.1を使ってしまっていた。neovim 0.5.1からlsp handlerの引数に破壊的変更があったため、LSPの補完が効かなかった。究明に当たってDockerを触ったり、Luaを触ったり、ドキュメントを漁ったりして色々糧にはなったので、記録しておく。何が起きたのかまず、プラグインの管理にはShougo/dein.vimを使った。 neovimのbuildin LSPを使ってLSPが使える環境を構築した。設定に当たって以下のプラグインを導入した。 neovim/nvim-lspconfig 入力補完はShougo/ddc.vimを使った。それにあたって以下のプラグインを導入した。 vim-denops/denops.vim: ddc.vimがDenoの機能を使うため必要。 Shougo/ddc-matcher_head Shougo/ddc-sorter_rank Shougo/ddc-around Shougo/ddc-nvim-lsp 最後のddc-nvim-lspがうまく動かなかった． Language Serverとしてpyrightを導入したのだが、実際にPythonのファイルで入力補完を試したところ，ddc-aroundの補完は反応するが，ddc-nvim-lspの補完候補が現れなかった。 Dockerを使って再現性を検証するまず、何か他のプラグインが邪魔しているのではないか Macという環境だから問題なのだろうかという仮説を立てた。そのためには、何も無い素のneovimの環境を作る必要があると考えた。そこで、環境をDockerで構築しようと考えた。 Docker環境の構築適当なディレクトリを作って、そこにDockerfileとdocker-compose.ymlを作成する。 Dockerfileを以下のようにする。ベースイメージはanatolelucet/neovimにした。この時点でdeinを導入する。コマンドはdeinのQuick startを参照した。deinのインストールにあたってcurl、gitコマンドが必要なので、ここで導入する。 1 2 3 FROM anatolelucet/neovim:stable-ubuntu RUN apt-get update && apt-get install -y curl git RUN curl https://raw.githubusercontent.com/Shougo/dein.vim/master/bin/installer.sh > installer.sh && sh ./installer.sh ~/.cache/dein neovimの設定ファイルはコンテナ外で編集できるようにしておく。同ディレクトリにディレクトリ.config/nvim/を作成し、その上で、docker-compose.ymlを以下のようにする。 1 2 3 4 5 6 7 8 version: '3' services: nvim: build: . volumes: - .config:/root/.config entrypoint: 'bash' working_dir: /root .config/nvim/の中にinit.vim、dein.toml'、'dein_lazy.tomlを作成。init.vimは以下の通り。 ...

Elmでテトリスを作った話

Elmでテトリスを作った。この記事では実装にあたって考えたポイントをメモしておく。コードは説明のために断片的に載せる。製作物ここで遊べる． Repositryはこちら。実装しなければいけない処理大まかに作らなければいけないのは以下の処理．ボード・テトリミノのデータ構造テトリミノの出現・回転・落下・固定テトリミノの衝突判定ラインがそろった時に消滅する処理ゲームオーバー処理キー操作画面描画この中からいくつかの項目について説明する。ボードのデータ構造ボードの落とす場は10x20のブロックで構成されている。壁をボードに含めるかどうか、上部にマージンを設けるかどうかで、実際のボードサイズは変わる。まず、ボードのブロックをセルと呼ぶことにする。セルを次のように定義する。Colorは適当に定義しておく。 1 2 3 type Cell = Block Color | Empty このセルを使ってボードを定義したいが、悩ましい選択が現れる。セルを要素に持つList。セルの座標はリストの添字で判断する。 (座標, セル)を要素に持つList。キーを座標、値をセルとしたDict。 ListをArrayにした実装も考えられる。参考までに、3つは以下のように定義できる。 1 2 3 4 5 6 7 8 type alias Board = List Cell type alias Board = List { pos : Vec Int , cell : Cell } type alias Board = Dict (Vec Int) Cell ボードのデータ構造によって諸々の関数の実装方法が大きく変わってくるので、どれを選ぶか慎重になる必要がある。 2つ目と3つ目のデータ構造はelm-gamesのRepositoryに載っているテトリスのコードから発見した。それらのコードを見つけた時にはすでに1番目で作ってしまっていたので、現状の自分の実装は1番目のものである。 TEAのView関数としての扱いやすさを考えるなら、2番目の実装が一番良いと思う。例えばセルの描画関数をviewCellとして、viewBoardは次のように書ける。 1 2 3 4 5 6 7 import Svg viewBoard : Board -> Svg Msg viewBoard board = Svg.g [] (List.map viewCell board) 他のデータ構造で実装する場合でも、viewBoardに渡す前に一旦{ pos, cell }のデータ構造に変換しておいた方が書きやすい。 ...

線形回帰メモ正則化

問題設定 $\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$ を消し去るための便宜的なものであり、つける必然はない。 L1正則化とL2正則化コスト関数に $\bm{w}_i$ のL1ノルム(の1乗)の項を付けることをL1正則化という。 $$ J_1(\bm{w}) = J(\bm{w}) + \lambda \|\bm{w}\|_1 $$ ...