この記事は ゆゆ式 Advent Calendar 2017 - Adventar 24 日目の記事です。 はじめに joisino.hatenablog.com 前回、唯の画像を無限に生成することに（部分的に）成功した訳ですが、画像ができたら今度は声が欲しくなってきます。 そこで、 [1710.08969] Effi…

この前 Parikh の定理（パリークの定理）を知ってびっくりしたので紹介します。 形式言語界隈では常識らしいです。 三行で説明して 文脈自由言語と正規言語は、単語を記号の度数で同一視（つまり記号の順番を無視する）と、同じクラスになるというものです。…

joisino.hatenablog.com ▲昔の記事 前回の試みから二年以上経ちましたがまだゆゆ式二期は発表されません。(*1) 二期が発表されないためこの記事のタイトルものんのんびよりさんから拝借することになりました。 やはり今話題のディープラーニングでなんとかす…

大学の実験で必要になって実装したのでメモしておきます。 Convolutional LSTM の説明 名前で完全にネタバレしてる感が否めないですが、Convolutional LSTM とは、LSTM の結合を全結合から畳み込みに変更したものです。 例えば画像を RNN に食わすときに、位…

色んな人がやってそうだけど自分用に作ってみました。 リポジトリです。 github.com 使い方 リポジトリをクローンして初期設定します 神絵師のリストを twitter で作って登録します 動かします slack に神絵が流れてきます 動作例 詳しく 動作の流れは以下の…

はじめに IOI 2013 オーストラリア大会に Art Class という問題があります。 この問題は、画像データが与えられるのでその画像が 様式１（新造形主義の現代芸術） 様式２（印象派の風景画） 様式３（表現派のアクション・ペインティング) 様式４（カラーフィ…

符号付き整数を 2 冪で割るときに右算術シフトを使ってしまって痛い目にあったことのある皆さんこんにちは。僕はあなたの仲間です。 コンピュータで割り算を行うのは一般に重いので、できるだけシフト等の軽い操作で済ませたいですよね。 最近のコンパイラは…

よりも小さい時間計算量 で行列積を計算するシュトラッセンのアルゴリズムとその導出方法を紹介します。 シュトラッセンのアルゴリズム の行列積 を考えます。 まず を $$ \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} \begin{pmatrix…

ケイリーの公式の証明たちの紹介です。 ケイリーの公式とは ケイリーの公式とは 頂点のラベル付きの木の総数 が であるという公式のことです。 ここで、ラベル付きであるとは、それぞれの頂点を区別するということです。 たとえば のとき、頂点を区別しない…

時間計算量 <O(n), O(1)> の LCA(Lowest Common Ancestor) と RMQ(Range Minimum Query) を C++ で実装しました。 アルゴリズムの解説はDさんのスライド [1] LCA and RMQ ~簡潔もあるよ！~ がとても分かりやすいのでそちらを参照してください。 概要だけ説明します。 LCA</o(n),>…

IOI2017（イラン大会）に副団長として参加してきました。 ioi2017.org IOIの参加記は選手・役員の感想（まだ公開されていないようなのであとでリンクを張ります）に書いたのでそちらを参照してください。 第29回国際情報オリンピック イラン大会 速報 も面白…

ミラーラビン素数判定法について ミラーラビン素数判定法はフェルマーテストを拡張した感じです。 フェルマーテストでは が素数のとき、フェルマーの小定理より と が互いに素なとき となることを利用して、 と互いに素な整数 を取って であれば合成数と判断…

言語処理系で講義でクリーネの不動点定理をやった時にベルマンフォードの証明にも使えるなぁと思ったので紹介します。 クリーネの不動点定理 を完備半順序集合とし、 をその上のスコット連続写像とする。このとき、 は最小不動点を持つ。 ここで、完備半順序…

HashedNets [1] を chainer で実装しました。 HashedNets の説明 ニューラルネットワークのパラメータ数は非常に多く、パラメータは冗長な表現になっていることが多いです。 そこで、自由なパラメータの数を減らして、正則化と軽量化を達成するための手法の…

本質的に曖昧な文脈自由言語が存在するという事実は色んなところで何度も目にしてきたのですが、証明を見たことが無かったのでここで紹介します。 流れは大体 [1] と同じですが、補題の証明はオリジナルも混ざってます（本質的には同じだとは思います）（間…

Adam [1] を chainer で実装しました。 Adam の説明 少ない時間・空間計算量で高い性能を出すということで、深層学習の分野で最近よく使われている最適化手法です。 をパラメータに取る関数 の（期待値）最小化を考えます。 の に対する勾配を とします。 一…

大学のソフトウェア実験でMLのインタプリタを作っているのですが、テスト用にMLプログラムの自動生成プログラムを書きました。 generator.sh は一部 @basemusi 君に書いてもらってます。 github.com 型推論器のデバッグ用に作ったのでこの名前ですが、インタ…

Dilated Convolution を chainer で実装しました。 Dilated Convolution の説明 Dilated Convolution は、フィルターとの積を取る相手の間隔をあける畳み込みのことです。 例えば、以下のような画像において、 12 を中心に 3 x 3 の普通の畳み込みフィルター…

Batch Normalization [1] を chainer で実装しました。 色々な場合に適用できて、学習速度が速くなったり汎化性能が上がったりするすごいテクです。 Batch Normalization の説明 上層（出力層に近い層）の入力は、当然下層（入力層に近い側）のパラメータに…

Generative Adversarial Nets [1] を chainer で実装しました。 いわゆる GAN です。 最近いろいろ派生系が出ています。画像の生成モデルはほとんどこれの派生な気がします。 画像を生成する Generator （以下 G）と、画像が本物か G が生成したものかを識別…

SRM717 の Hard で出題されて気になったので書き留めておきます。 Chromatic Polynomial について まず、無向グラフの頂点から色への対応を彩色、隣接する頂点が同じ色にならないような彩色のことを正しい彩色ということにします。これはこの記事限定用語で…

先日、長いようで短かった実験がついに終わったので記録を残しておきます。 はじめに 京都大学情報学科の計算機科学コースでは計算機科学実験及演習（以下、実験）という必修科目が 2 回生前期 / 後期、 3 回生前期 / 後期の計 4 つあります。実験 1 はプロ…

明日、KMC の組合せ最適化読書会でやる予定なのですが、少し調べた限りでは日本語の解説が見つからなかったので書いてみます。（注：組合せ最適化本体には O(nm) のアルゴリズムしか載っていません。） こういうアルゴリズムに慣れていない人向けに書いたつ…