2019-08-25

JSC2019予選 D - Classified (600)

競プロ競プロ-AtCoder アルゴリズムアルゴリズム-グラフプログラミング言語プログラミング言語-C++

問題

頂点の完全グラフの全ての辺に以下を満たすように正の整数値(=レベル)を割り当てる
- 頂点 $i$ からレベルが等しい通路のみをいくつか通って $i$ に帰ってくるとき、その経路長は必ず偶数になる
上のような割り当て方のうち、レベルの最大値を最小化するものを出力せよ
$2 \leq N \leq 500$

考察

出発した頂点に戻るような全ての経路の長さが偶数、ということはすなわち奇数長の閉路がないということになる。「奇数長の閉路がない」 $\Leftrightarrow$ 「二部グラフである」ということに気づくと、二部グラフをいくつか組み合わせて完全グラフを作る問題に読み替えられる。

ここで少し悩んだので一旦実験してみることにした。

$N=5$ でとりあえず $A:[1, 2, 3$ ]と $B:[4, 5$ ]の二部に分け、その二部グラフに含めることができる全ての辺(=完全二部グラフの辺)をレベル1(赤色)とした(左図)。あとは残った辺についてレベル2以上の値を割り振っていきたいわけだが、ここで今レベルの決まった辺を削除してみると...(右図)

なんということでしょう！残っているのは頂点集合 $A, B$ それぞれの完全グラフではありませんか！！！考えてみると二部グラフの辺は $A$ の一頂点と $B$ の一頂点を結ぶものであるから、 $A$ 同士や $B$ 同士を結ぶ辺は全て残ってしまう(つまり完全)のでそれはそうという感じ。

ということで、二部グラフの辺のレベルを確定させたあとは再帰が使えそうだ。(この場合は $N=|A|=3$ と $N=|B|=2$ の時に再帰)

では $N$ が与えられた時に、頂点集合 $A, B$ はどのように分ければいいのか？これは直感通り半々に分けることが最適であると示せる。

まず頂点数 $N$ について題意の割り当て方によるレベル数の最小値を $L(N)$ とすれば、 $N=k$ の完全グラフは $N=k+1$ の完全グラフに丸ごと含まれることから、 $L(k) \leq L(k+1)$ が言えて、これにより $L(N)$ が広義単調増加であることがわかる。

このとき $N$ 個の頂点を $A, B$ のように分けた場合、レベル数は $\max (\; L(|A|),\;L(|B|) \; )$ であり、 $L$ が広義単調増加であることからこれは $L( \; \max( |A|, |B| ) \; )$ に等しい。よって $\max( |A|, |B| )$ を最小にする分け方が最適であり、これは $A, B$ を半分ずつ分けるということに他ならない。

以上から、

$1 \sim N$ を半数ずつ $A, B$ に振り分ける
$A, B$ 間の辺のレベルを1とする
$A, B$ それぞれについて再帰を適用する

という流れで実装すれば良さそう！

実装

あとは書くだけ！こういう考察さえすれば実装は軽い問題、結構好き。

using namespace std;

#define MAX_N 600

int a[MAX_N][MAX_N];  // a[i][j] = 辺i-jのレベル

// s <= i < e を満たす全ての頂点iからなる完全グラフについて、レベルを割り振る
void set_levels(int s, int e) {
    if (e - s < 3) return; // 頂点数3未満の場合、完全グラフ==二部グラフ
    int now = a[s][s], // 今のレベル
        m = (s + e) / 2;
    for (int i=s; i<m; i++)
        for (int j=s; j<m; j++)
            a[i][j] = now+1;
    for (int i=m; i<e; i++)
        for (int j=m; j<e; j++)
            a[i][j] = now+1;

    // 前半と後半に分けて再帰
    set_levels(s, m);
    set_levels(m, e);
}


int main() {
    int n;
    cin >> n;
    fill(a[0], a[n], 1); // 一旦全部1で埋める
    set_levels(0, n);
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            cout << a[i][j] << (j == n-1 ? '\n' : ' ');
        }
    }
    return 0;
}

atcoder.jp

2019-08-21

マスタリングTCP/IP 入門編読書メモ【第1章後半】

ネットワーク読書メモ

今回は1.6節から1章の終わりまで行きます。

元書籍→マスタリングTCP/IP

前回の記事→

shugo256.hatenablog.com

通信方式
アドレス
- 唯一性
- 階層性
ネットワークの構成要素

通信方式

コネクション型とコネクションレス型

コネクション型ではデータの送受信をする前に両ホスト間で回線を"接続"する
- 通信できない場合に無駄なデータを送らなくて良い
- 通信の前後にコネクションの確立と切断の処理が必要
- 二人ともグローブをはめていて、お互い準備できたか確認した上でキャッチボールを始めるイメージ
コネクションレス型ではコネクションの確立や切断の処理がなく、いつでもデータを送れるし、いつデータが来るかわからない
- 通信できない場合にも無駄にデータを送信しようとする
- コネクション処理がなくなることで負荷が軽減される
- 相手の状態にかかわらず突然ボールを投げつけるイメージ

回線交換とパケット交換

回線交換
- 一度コネクションを確立したら切断するまで回線を占有し続ける(コネクション型)
- 同時に使用できるのは回線の数だけのユーザーのみであり、それ以上は増やせない(図1.31)
- 回線を占有するので、一定のスピードで転送が行われる
パケット交換
- コンピュータが送信するデータ複数の小包にわけて転送待ちqueueに追加していって順番に転送していくスタイル
- 1つの回線を複数のユーザが共有して利用できる
- ネットワークの混雑度によってはパケットの回線速度が遅くなったりする

通信相手の数による分類

Unicast : 1対1 (ex. 電話)
Broadcast : 1対不特定多数 (ex. テレビ放送)
Multicast : 1対特定の多数 (ex. ビデオ会議)
Anycast : 1→特定の多数に情報を発信した後、多数の中から最適なホストが1つ選ばれ、以降はUnicastでやるらしい
- 飛行機での「この中にお医者様はいらっしゃいますでしょうか」っていうやつ
- これだけ正直よくわからないが、5.2や5.8.2で登場するらしい

アドレス

TCP/IPではMACアドレス、IPアドレス、ポート番号などがある

唯一性

アドレスから通信相手を特定できる
BroadcastやMulticastみたいに複数の相手に同じアドレスを割り当てる場合もユニークと言える (「1年1組の皆さん」は複数人を指すがユニーク)

階層性

地球上の場所を示す方のアドレス(国名/都道府県名/市区町村名/番地)と同様にアドレスの一部を組織、プロバイダ、地域などに対応させることでアドレスを探しやすくする
IPアドレスはネットワーク部とホスト部から構成され、同じ組織、グループのアドレスは共通のネットワーク部を持つ
MACアドレスは階層性を持たない

ネットワークの構成要素

全体像は図1.37

データリンクと伝送速度

直接接続された機器間の通信に用いるプロトコルやネットワークのことをデータリンクという
この2つの機器間を流れるデータの物理的な速さを伝送速度という
- 媒体中を流れる信号(光、電子など)の速さは一定であるから、伝送速度を決めるのは帯域(道路で言うところの車線)である
データリンクの伝送速度(帯域)のみならずホストCPUの能力、ネットワークの混雑度などを加味した通信速度の指標として、スループットがある

ネットワークインターフェース

コンピュータをネットワークに接続するための装置
最近では内蔵しているコンピュータが多いらしい

リピーター

物理層でネットワークを延長する装置
伝播の過程で減衰した波形を復元する
- 通信路を流れる信号の0,1をはっきりさせるだけなので、伝送速度やデータリンク層レベルでのエラーなどには口出しできない
電気->光のように通信媒体を変換するリピーターもある

ブリッジ(レイヤ2スイッチ)

ブリッジはデータリンク層でネットワーク同士を接続する装置
- 第2層(データリンク層)における機能であるから、レイヤ2スイッチとも呼ばれる
データリンクのフレームを理解して一旦メモリに蓄積してから送り出す
- データリンクのフレーム内のFCS(Frame Check Sequence)と呼ばれるフィールドをチェックし、壊れているフレームを検出して他のセグメント(=ネットワーク)に送らないようにしてくれる
図1.42のように「宛先が〇〇ならこっちのネットワークには流さなくていいね」みたいな判断をしてくれるものもある(ラーニングブリッジ)
- この際用いるのは物理アドレス(MACアドレス)

ルーター(レイヤ3スイッチ)

ネットワーク層でパケットの中継を行う装置
- ネットワーク層のアドレス(IPアドレス)を用いて宛先へのルートを決定し、配送する
異なるデータリンク同士も相互に接続可能

レイヤ4-7スイッチ

トランスポート層〜アプリケーション層での情報に基づいた配送処理を行う
例えばたくさん閲覧されるWebサーバーでは1つのURLに対して複数のサーバーで負荷を分散したい
- この方法の一つがWebサーバーの手前へのレイヤ4-7スイッチ(ロードバランサー)の設置
他にもアプリケーション固有の処理みたいなのは色々あるらしい

ゲートウェイ

レイヤ4-7スイッチと同様にトランスポート層以上の階層での処理を行う
ゲートウェイには互換性のないプロトコル間を翻訳により中継するという役割がある(ex. 携帯メールとインターネットメールの交換)
WWWにおいてサーバーとクライアントが直接通信せずに代理サーバー(Proxy Server 図1.48)を用いて制御を行う場合、代理サーバー=アプリケーションゲートウェイ
- クライアントは代理サーバーと接続を確立し、代理サーバーがインターネットのサーバーとの接続を確立する

先人たち、ようここまで頑張ったなあというお気持ち

次回→

shugo256.hatenablog.com

最初の記事→

shugo256.hatenablog.com

2019-08-18

マスタリングTCP/IP 入門編読書メモ【第1章前半】

ネットワーク読書メモ

学科のネットワークの講義がう◯ちだったので自分で勉強してみようということになりました。だいたい節ごとで気になったところ/勉強になったところを列挙していくスタイルでいきます。今回は第1章ですが、この章は長めなので1.5節までを一区切りとして分けたいと思います。

元書籍→マスタリングTCP/IP

↓ここに各章のリンクを貼っていく(1章は長すぎるので二つに分けます)

第1章後半
第2章
第3章(Coming soon...)

導入
プロトコルとは
プロトコルの階層化
OSI参照モデル

導入

もともとコンピュータは単体で独立に使われていた(スタンドアロン)が、ネットワークで繋げてみんなで色々共有したほうがよくね？という話
ネットワークの規模に応じてWAN,LANなどの呼称がある
- WAN(Wide Area Network) : 地理的に離れた広範囲に及ぶネットワーク
- LAN(Local Area Network) : フロア内、1つの建物、キャンパス内など比較的狭い範囲内でのネットワーク

プロトコルとは

コンピュータ同士が通信する時に必要な約束事で、これによって異なるCPU、OSを持つコンピュータ間でもプロトコルが同じなら通信ができるというもの
様々なプロトコルを体系的にまとめたものをネットワークアーキテクチャといい、本書のタイトルにもあるTCP/IPはその一種らしい (知らんかった...)
大きなデータは小さなパケット(小包)ごとに分けて送信するというのが一般的だが、そのヘッダ(荷札)部分の情報がプロトコルによって書き込まれ、処理される (p17図1.14参照)
昔はメーカーごとに互換性のないプロトコルが使用されていたが、今では標準化され、TCP/IPは業界標準となっているらしい

プロトコルの階層化

通信に必要な機能を複数の階層に分け、ネットワークプロトコルの単純化を図る
異なる階層同士のやり取りの規則をインターフェース、通信相手の階層とのやり取りの規則をプロトコルという(p20図1.16参照)
利点としてある一つの階層を変更してもシステム全体には影響を及ぼさないので、拡張性、柔軟性が生まれる点(ソフトウェアでいうモジュールみたいなイメージ)
欠点としてはモジュール化をやりすぎると重くなったり、処理が被る層が出てくるという点
- 要するにやりすぎはダメ！
p20の会話の例がわかりやすいかもしれない

OSI参照モデル

パケット通信における階層を7つに分け、各層のおおよその役割を定めるモデル
多くの通信プロトコルはこれに当てはめて考えることができる
基本的にデータの流れは送信側の上位層->下位層->受信側の下位層->上位層のようになっている(p26図1.20)

アプリケーション層

用いるアプリケーションの中で通信に関係する部分を定めている(ファイル転送, メール, 遠隔ログイン, etc...)
- つまりアプリケーションに特化
電子メールで言えば、送信側では電子メールの本文に宛先などの情報を含むヘッダをつけて発送し、受信側ではその情報を解析してメールの内容を主記憶に保存するなどする
- メールの保存領域が足りない時などといったアプリケーション固有のエラー処理もここが担う

プレゼンテーション層

ハード固有のデータのフォーマットと、ネットワーク全体で共通のデータのフォーマットとを相互に変換する
電子メールで言えば、文字列をネットワークで統一されたフォーマット(ex: UTF-8, Shift_JS, etc..)に符号化した上で送り出し、受け取る側はそれを受け取る側のハード固有のフォーマットを用いて保存するなり表示するなりする
- メールの文字化けはこのプレゼンテーション層の設定がミスっているという原因が考えられる

セッション層

コネクションをいつ何個確立するか、切断するかや、データをどのような順番で送れば良いかなどといったことを定める
- ここでデータの送信手順に関するタグやヘッダがつけられる
電子メールで言えば、メールをどういう順番で、いくつコネクションを使ってお届けするかということ

トランスポート層

データが抜けることなく確実に相手に届いていることを保証する
- 通信の両端でデータがきちんと届いたかの確認をし、届いていない場合は再送する
セッション層で決めたコネクションの確立/切断のタイミングで実際にそれらを行う
電子メールの場合例えば「こんにちは」のうち「こん」しか届いてない場合、「足りなくね？」と問い合わせて「にちは」も送らせる
- あくまで予想だが、この層でヘッダにデータの順番通りにidをふっておいて抜けがあったらわかるようにしている？

ネットワーク層

宛先のアドレスを元に到達経路を選択し、配達する
- 上位層から渡されたデータにアドレスや経路の情報を付加してデータリンク層に渡す
送受信ホスト間が直接つながっていない場合、間にルータを介して通信することになるが、その場合もこの層はエンドツーエンドで全体を司る
直下の層であるデータリンク層が一つ先のルータまでの通信を実現する
トランスポート層がデータの到達性を保証してくれるので、ここではそれを気にしなくて良い(階層化のうまみ)

データリンク層

物理層で直接的につながっているノード間での通信を可能にする
- つまり通信の中継点であるルータもデータリンク層を持つ
データフレーム(ビット列の意味のある塊)の生成、識別

物理層

ビット列と物理現象(電圧のhigh/low, 光のパルス, etc...)の相互変換を行い、物理的通信媒体に流し込んだり受け取ったりする

次回→

shugo256.hatenablog.com

2019-08-12

Whispered-to-voiced Conversion with GAN 論文まとめ

DeepLearning DeepLearning-GAN 論文読み DeepLearning-音声処理

前置き

前回に引き続きGANの論文を読んでいこうと思います。(元論文はここ) ざっくり言うと機械の発する声を自然にしようという研究で、研究自体は地味に思えますが声質変換などに応用が効くかもしれません。

モチベーション

失声症患者の声を復元する手法の多くは、whispered(声帯が振動しない話し方)やmonotoneな音声を生成する。しかしwhisperedでは内容は伝わっても声の強弱による表現力に欠けるため、whisperedをvoised(声帯を振動させるいわゆる普通の喋り方)に変換するモデルが必要だ！
従来の手法では発話音声から音響の特徴量を統計的に推定した上で、それらの特徴量をvocoderに与えて出力を合成すると言う間接的な手法が取られてきた。入力音声から直接出力音声が得られるように学習した手法の方がより正確な、あるいは自然な出力が得られるのではないか？
ってことでSEGAN(GANによるノイズ除去)の発展系として作りたい！

事前知識

speaker-dependent

システムを使う人のみに適応するモデル。使う人の声で学習するので、誰にでも使えるspeaker-independentなモデルよりも性能がいいらしい。今回のモデルはこれのようだ。iOSデバイスを買うと最初のセットアップで”Hey, Siri”と何回か言わされるが、これもその一種なのだろうか。

deconvolution

convolution層では基本的に特徴マップのサイズは縮小される。この性質は観測対象から大事な情報だけを抽出した表現を得たい場合(今回で言うGeneratorのEncoder)にはうってつけだが、その表現から新しくデータを生成したい時(今回で言うDecoder)にはむしろサイズを大きくしたい。deconvolutionでは入力をpaddingによって十分に拡大してからconvolution層に通すことにより、出力のサイズが入力のそれを上回るようにした層である。これはconvolution層の誤差逆伝播の過程でも登場する。

アーキテクチャ

まずはSEGANについて

f:id:shugo256:20190804015532p:plain — SEGAN

SEGANはノイズ除去タスクにGANを適用したものであり、G(enerator)とD(iscriminator)から成る。
GはEncoderとDecoderからなっており、元のデータセットにノイズを加えたものを入力とし、出力が元の音源に近くなるよう訓練されることでノイズ除去を実現する。一次元convolution層からなるEncoderにより音声の圧縮表現cを得て、これを潜在変数(乱数)zと連結した後、deconvolution層からなるDecoderによって音声に戻す。ちなみにDecoderの各レイヤでは残渣接続みたいなノリで同じサイズのEncoderの途中のレイヤの出力をチャネル方向に連結している。(上図)
Dには元のデータセットそのままの音声(real)と元のデータセットの音源にノイズを乗せ、それをGに通してノイズ除去したもの(fake)を入力として与え、realを見分けるよう訓練する。この時real,fakeともに元音源にノイズを付加したものも入力として与える。realの場合は元の音声とそれにノイズを付加したもの、fakeの場合はGの出力と入力の組がDに与えられる。ちなみにDの内部はほとんどGのEncoderと同じで、activationがLeekyReLUだったり最後に全結合層があるという程度の違いのようだ。
普通のGANと同様、GとDの損失関数はDの出力(Gではその反転を用いる)の交差エントロピーにより与えられるが、SEGANではGの損失関数にノイズ付加前のデータとGの出力の距離指標としてL1正規化項を加えている。これによってGのノイズ除去性能を直接最適化する項が追加されたことになる。元音源をdata、ノイズ付加処理をN(x)、Gに通す処理をG(x)と表せば、realは(data, N(data))、fakeは (G(N(data)), N(data))となり、fakeをrealに近づけると言うことが、G(x)をN(x)の逆関数(つまりノイズ除去)に近づけることに対応していることがわかる。
通常のGANとの相違点として、普通は潜在変数のzがGの唯一の入力であり、これがGによって直接観測データ(例えば音声)に変換されるわけだが、今回はGにもう一つ別の音声(ノイズあり音声)が入力されていることから、zは直接音声データに変換されるのではなく、イメージとしてはノイズ除去ベクトルのようなものに変換され、それが入力ノイズあり音声に作用する結果としてノイズなし音声が出力されているのではないかということが考えられる。

SEGANとの相違点、改善点

下図は今回のモデルにおけるGの図であり、上のSEGANの図と見比べることでSEGANのGと少し違うことがわかる。

f:id:shugo256:20190804015657p:plain — WSEGAN

まずGの入力はwhisperd(声帯を使わない発話音声)、出力はvoicedとし、whisperedに対応する自然な発話音声をnaturalとする。今回の実験ではwhisperdは実際にささやきを録音したものではなく、naturalを録音中の口や下の動きからRNNのシステムによって生成されたささやき音声であるので、同じ人が同じ文章について別々にnaturalとwhisperedの音声を録った場合よりも両者の関係は強いと考えられる。この時Dの入力はSEGANの時と同様にrealが(natural, whispered)の組であり、fakeが(voiced, whispered)となるが、今回はfakeにもう一つ新しいパターンを追加する。それは(natural, random_natural)である。random_naturalはnaturalなデータセットから無作為に選んだサンプルであり、これをfakeとして加えることにより、Gの出力がどんなに自然(natural)であっても、話した内容がGの入力(whispered)と異なってしまっては困ると言う効果が望まれる。
SEGANの時と比べてEncoderとDecoderのそうの数が減っていることがわかる。これはpoolingを2->4とした効果であり、このようにしたのは事前に行ったノイズ除去タスクでの実験でその方が良い結果になったからだそうだ。(じゃあなんでSEGANの時はそうしなかった...?)
Encoder-Decoder間のskip-connectionがただの連結から重み付き和になり、learnableとなった。理由は特に書いていないが、層の数が減った分ここにパラメータを割けるようになったということだろうか。
SEGANではGの損失関数にL1正規化項が含まれていたが、二つの信号の距離指標としてのL1ノルムは信号の各要素の一対一対応を仮定しており、例えば1フレームだけずれた全く同じ信号は別物として計算されてしまうので排除した。(misalignment)これにより出力の音声信号の振幅は簡単に爆発し、tanh活性化において勾配がほぼ0になってしまうことが考えられるので、L1ノルムの代わりとしてズレに寛容なスペクトルノルムを導入した。

方法と結果

実験方法

健康なイギリス人男女6人に25分ずつCMU コーパスからランダム抽出した文章を読ませ、それを録音することでnaturalデータをえた。この際同時に口などの動きからささやき音声を生成するモデルを使用し、その出力をwhisperedとした。このwhieperedにおいてそれぞれの性別から一番明瞭で聞き取りやすい人を一人ずつ選び、この二人についてそれぞれspeaker-dependentなモデルを構築した。

結果

元音源(natural)とモデルの出力において各pitch(周波数)がどれだけ現れたかを表すヒストグラムである。(左が男、右が女)なおRNN baselineは大義名分のところで述べた従来の手法によるものである。

f:id:shugo256:20190804015929p:plain — Result

男女ともにbaselineよりもvoicedの方が幅(分散)が大きくなっており、naturalに近いものとなっていることがわかる。baselineのように分散が小さい音声はロボットのような声になってしまうようで、今回のモデルはより自然に近い声を生成できていたことがわかる。
下図は左から順にnatural, whispered, voicedの波形とスペクトログラムである。

f:id:shugo256:20190804020023p:plain — Waves

これを見ればいかにgeneratorが低周波成分を修正し、高周波なノイズを除去できているかがうかがえるらしい。(うーん...)
なんか結果を見せられても納得いかなかったが、実際の音声を使ったデモがここで公開されていて、割と綺麗な音声に復元できていることがわかった。 whisperedはささやきというより天龍源一郎であった。

まとめ

SEGANにおけるmisalignmentの問題を、L1ノルムをなくすことにより解決した上で、L1ノルムの元々の存在意義であった振幅爆発の予防策としてスペクトルノルムを導入した。
そのほかにもfakeのパターンの追加、learnableなskip-connection、poolingの変更などによってSEGANよりも一段上のwhisperd-to-voicedというタスクをクリアした。
GANがデータそのものではなくてノイズ除去という動作を生成しているという点が面白かった。
今回のモデルはあくまで失声症の人の口の動きなどからささやき音声を出力してくれる別のモデルがあってこそ役に立つものであり、End-to-endとは言いつつも実際はそうではない。
どうせなら口の動きからnaturalな音声を復元するモデルを作ればいいのにと思ったら、Conculusionsに今後の課題としてあげられていた。

参考

StyleGAN アーキテクチャのざっくりまとめ

DeepLearning DeepLearning-GAN DeepLearning-画像処理論文読み

StyleGANの論文を読んだので超ざっくりメモを残します。

StyleGANはGANによる画像処理にスタイル変換を組み合わせたもので、スケールごとにスタイルを変換できるところに目新しさがあります。

今流行りのWaifu Labsとかってこれの応用だったりするんでしょうか。

アーキテクチャ

基本的にgeneratorを頑張る研究であり、discriminatorやloss functionなどについては一切いじらないという方針。
StyleGAN Architecture
従来のもの(a)とは異なりMapping networkとSynthesis networkに別れている
Mapping networkでは乱数として生成される潜在変数zを8層のMLPによってスタイル変換のための別の潜在空間Wへと写像される。従来の研究ではzをそのまま用いていたが、zの分布は下図(b)のように超球として固定されていて、(a)のようなデータセットの空間に対応できない。(というか無理やり歪ませて超球に押し込めていた) 例えば性別とヒゲの量の二軸からなる潜在空間を考えた時に、これが綺麗な円になることはまずないだろう(ヒゲの生えた女性はあんまりいない)。 (b)のような歪んだ空間上だと2点間を連続的に移動する時の画像の変化が途中で不自然になることがあるらしい。
StyleGAN_LatentSpace
こうして得られた $w$ はAffine変換Aによって2*channel次元ベクトルyに変換され、チャネルごとに下式のように平均 $\mu$ と分散 $s$ をいじることでスタイル変換を施す。これによりAdaINの直後のCNNではこのスタイル変換が直接効くが、その次のAdaINによってまた統計的性質は変わってしまうので、層ごとのスタイル変換が可能らしい。

\begin{align} AdaIN(x_i, y) = y_{s, i} \frac{x_i - \mu(x_i)}{ s (x_i) } + y_{b, i} \end{align}

冒頭の図では8x8までしか書いていないが、本当はこれが1024x1024まで続いており、各ブロックに与えるwを変えることでスケールごとのスタイル変換が可能となっているのがこの研究のミソ
```
  - Coanrse Style(4x4~8x8)
     顔の形、髪型、メガネ、姿勢など
  - Middle Style(16x16~32x32)
     顔の特徴、目など
  - Fine Style(64x64~1024x1024)
     全体の色合いなど
```
さらに各層ではAffine変換Bを施したNoiseを付加している。それぞれの層にどれだけの大きさのノイズを与えるかを調整することで、髪の流れやシワなど確率的な部分を変えられるようだ。 ~32x32のノイズは髪の大まかな流れを 64x64~のノイズは細かい髪質やシワを制御しており、ノイズを全く付加しないと絵みたいなぼやぼやっとした画像になる (=平均的)
さらにさらにwをそのまま使うのではなく、W空間における平均値とパラメータψを用いることで計算される $w' = \overline{w} + \psi(w - \overline{w})$ を用いることで、ブロックごとに平均顔からどの程度離れたスタイル変換を施すかを調整できる。
小さすぎると面白みがないけど大きすぎると乱れる場合があるというイメージこの辺の説明はyoutubeを見ると非常にわかりやすい

より詳しくは

StyleGAN解説 CVPR2019読み会@DeNA

A Style-Based Generator Architecture for Generative Adversarial Networks を読んだ - Qiita

StyleGAN: A Style-Based Generator Architecture for Generative Adversarial Networks - 機械学習奮闘記

2019-08-02

牛ゲーが何故グラフの最短経路に帰着できるのか

競プロアルゴリズムアルゴリズム-グラフ競プロ-蟻本

前置き

夏休みだ〜！！ということで気合いを入れて蟻本を読み進めていたら、2章のグラフのところで牛ゲーと呼ばれる問題と出会いました。

牛ゲーとは数列 $d_i$ について

\begin{align} d_j - d_i \leq c_{ij}(const) \tag{1} \end{align}

という形でのみ表される条件がたくさんあるとき、ある $g, s$ について $d_g - d_s$ の最小値を求めようみたいな問題のようです。蟻本に載っているPOJ3169が牛の問題だからこの名前がついてるっぽいですね。例えばこういうやつです。

蟻本ではこの問題を、上のような条件を持つ各 $i, j$ について辺 $i \to j$ の重みを $c_{ij}$ とした有向グラフを考えた時に、頂点 $s$ から頂点 $g$ に向かう最短距離を求める、というものに帰着していました。確かにそう最短路に帰着できそうとは思いつつも、なんとなく腑に落ちなかったので少し自分なりに考えてみました。

証明(?)

数列 $d_i$ が有向グラフ $G$ 上での頂点 $s$ から各頂点 $i$ への最短距離を表しているという仮定の元で、条件として新たに(1)式を追加することと、有向グラフ $G$ に $i \to j$ へと向かう重みが $c_{ij}$ の辺を書き加えることとが等価であることを示せば良さそうですね。

まず(1) の条件を追加するような辺の書き加え方を考える。 $d_i$ というのは最短距離を表すので、満たすべき関係式は

\begin{align} d_i \leq (sからiに向かう任意の経路の長さ) \end{align}

であり、この他の制約はない。

したがって(1)式、つまり

\begin{align} d_j \leq d_i + c_{ij}(const) \tag{1} \end{align}

が成立するとすれば、それは $s \to j$ へ向かう経路の中に経路長が $d_i + c_{ij}$ であるものが存在する時である。また辺の追加の過程で $d_i$ の値は変わりうるので、(1)の条件を追加する方法は $i \to j$ と向かう長さ $c_{ij}$ の経路を書き加えるという他ない。

あとは $i \to j$ と向かう長さ $c_{ij}$ の経路の中から(1)と等価な経路、つまり書き加えることで条件(1)のみが追加され、その他の余分な条件が加わらないものを見つければ良い。

$i \to j$ と向かう長さ $c_{ij}$ の経路は以下の2種類に分けられる。

(a) : $i \to j$ を長さ $c_{ij}$ の辺で直接つないだもの　　

(b) : 長さの和が $c_{ij}$ となる複数の辺でつないだもの

長さ $w$ の辺 $u \to v$ を書き加えた場合、 $s \to v$ の経路として新たに追加されるのは、 $s$ から $u$ を経由してから辺 $u \to v$ を用いて $v$ に行くという経路だけなので、制約として加わるのは

\begin{align} d_v \leq (sからuに向かう任意の経路の長さ) + w \end{align}

\begin{align} \therefore d_v \leq d_u + w \tag{2} \end{align}

という不等式のみである。

したがって(a)のように追加すれば確かに条件(1)のみが追加されると言える。

一方で(b)を追加する場合は各辺ごとに(2)のような制約が加わってしまう。例えば $i \to m \to j$ というように辺を書き加えた時、2本の辺それぞれに対して(2)が成り立つので、

\begin{align} d_m \leq d_i + c_{im} \quad かつ \quad d_j \leq d_m + c_{mj} \quad ( c_{im} + c_{mj} = c_{ij} ) \end{align}

となり、(1)よりもさらに厳しい条件となってしまっていて、等価とは言えない。

以上より $G$ 上で(a)のような辺を追加するという操作は、(1)式を制約として追加することと唯一等価な操作であることが示された。

これによって牛ゲーがグラフの最短経路問題へと帰着できる。

おわりに

正直穴のありそうな証明になってしまったが、直感的な理解にはつながったのでよしとしたいでござる。いずれこの辺も解きたいですね。

参考

牛ゲー(最短経路問題の双対問題が線形計画問題) - 数学/競プロメモ

ダイクストラとポテンシャルのはなし - niuez’s diary

2019-08-01

じこしょうかい

はじめまして。shugo256です。

情報工学の勉強をしている大学3年生で、今は趣味で競プロ、バイトでDL(GANなど)をやっているという感じです。主に情報科学系のアウトプットをしていくつもりなのでよろしくお願いしまあす！

問題

考察

実装

通信方式

コネクション型とコネクションレス型

回線交換とパケット交換

通信相手の数による分類

アドレス

唯一性

階層性

ネットワークの構成要素

データリンクと伝送速度

ネットワークインターフェース

リピーター

ブリッジ(レイヤ2スイッチ)

ルーター(レイヤ3スイッチ)

レイヤ4-7スイッチ

導入

プロトコルとは

プロトコルの階層化

アプリケーション層

プレゼンテーション層

セッション層

前置き

モチベーション

事前知識

speaker-dependent

deconvolution

まずはSEGANについて

SEGANとの相違点、改善点

方法と結果

実験方法

結果

まとめ

参考

論文

ウェブサイト

実装

より詳しくは

前置き

証明(?)

おわりに

参考