メモ

自分に向けて書いたメモを取り扱っています.

Why does the loss function of discriminator use softplus on GAN

GANで使われる Discriminator の損失計算の実装を見てみると,softplus関数を使っていることがあります.
これは,sigmoid関数でcross entropyを計算することと同じことをしています.

Softplus

$$\text{softplus}(x)=\log{(1+\exp{x})}$$

Sigmoid

$$f(x)=\frac{1}{1 + \exp{(-x)} }$$

Binary cross entropy

$$g(y, t)= - t \log{y} - (1-t) \log{(1-y)}$$

t=0とt=1のときのg(f(x), t)の挙動

\begin{align}
g(f(x), t=0)&=\log{(1-f(x))} \\
&= - \log{ \left( 1 - \frac{1}{1 + \exp{(-x)} } \right) } \\
&= - \log{ \left( \frac{ 1 + \exp{(-x)} - 1 }{ 1 + \exp{(-x)} } \right) }\\
&= - \log{ \left( \frac{ \exp{(-x)} }{ 1 + \exp{(-x)} } \right) } \\
&= - \log{ \left( \frac{1}{ \exp{x} + 1} \right) } \\
&= \log{ \left( \frac{1}{ \exp{x} + 1} \right)^{-1}} \\
&= \log{ \left( 1 + \exp{(x)} \right)} = \text{softplus}(x) \\
g(f(x), t=1)&= - \log{(f(x))} \\
&= - \log{ \left( \frac{1}{1 + \exp{(-x)} } \right) } \\
&= \log{ \left( \frac{1}{ 1+ \exp{(-x)} } \right)^{-1}} \\
&= \log{ \left( 1 + \exp{(-x)} \right)} = \text{softplus}(-x)
\end{align}

Discriminatorの学習は X_real に対しては1を, X_fake に対しては0になるようにします.
確かに https://github.com/chainer/chainer/blob/master/examples/dcgan/updater.py#L13-L19
ソースコードを見ると,

    def loss_dis(self, dis, y_fake, y_real):
        batchsize = len(y_fake)
        L1 = F.sum(F.softplus(-y_real)) / batchsize
        L2 = F.sum(F.softplus(y_fake)) / batchsize
        loss = L1 + L2
        chainer.report({'loss': loss}, dis)
        return loss

X_realに対してはsoftplus(-x)を,X_fakeに関してはsoftplus(x)を使用して損失を計算していることが分かります.

Generatorの学習は,生成した画像に対してラベルが1(本物)になるようにしたいので softplus(-x) を使用して学習します.
直感的に考えると生成した画像は活性化関数を通っているとはいえ,ある種の正規化されたピクセルを持っているわけで,各ピクセルが1になるようにするということは,つまり画像を真っ白にすることなのでヤバそうなのですが,Discriminatorの学習もあるので結局良い感じにパラメータが学習されるのかな,と自分は解釈しています. かなり馬鹿なことを書いてました.ちゃんとソースコードを読むと,generatorで生成したxに対してdiscriminatorを通して損失を計算しているので,画像を真っ白にするとかそんなことはやっていないです.)

プログラムレベルでの wifi 接続方法

モチベーション

GUIからwifiなどの接続設定を行っているが,プログラムでそれを行いたいというのが私のモチベーションである.

調査

github.com

python で良さそうなライブラリがあり,コードを流して読むと大体何をやっているのか分かった.

  1. _detectDriverメソッドを呼び出す
    • このときに各OSのWireless Driverをwhich コマンドから検索して見つかったものを選択するようにしている.
  2. 接続処理も各OSのWireless Driverに従ってコマンドを実行する.

Linux系だとnmcliが使われるのかと思い,nmcliの内部実装に興味が湧いたので少し読んでみた.

そもそもでnmcliNetworkManagerのクライアントのコマンドラインで内部処理はNetworkManagerを読めば良さそうだということが分かった.

NetworkManagerについては

github.com

ここを見れば良さそうだ.これを読み解いていくのは流石に骨が折れるので,読み進めて知見を得ることができたらまたメモする.

Leetcode : 629. K Inverse Pairs Array

leetcode.com

問題概要

長さ n の順列を考える.反転数が k となる数列を数えなさい.

考察

一番愚直だと思われる解法は n! 通りの数列の反転数を計算し,kとなるものを数え上げるというものである. この計算量は O(nlogn*n!) であるがこれは明らかにTLEする.

部分問題に切り分けることを考える.1 から n-1 までの数字を用いて作る数列に n を追加することを考えると漸化式を立てれそうな気がする.

dp[n][k] := 数列の長さが n で 1 ~ n の数字で構成される数列において反転数が k となる数

とすると

dp[n][k] += sum_{i=0}^{n} dp[n-1][k-i]

となる.

これでは O(n3) となるが,まだTLEする.そこで上のdpを高速に計算する方法を考える.

遷移を見ると,規則性が見えて累積和を取ることによって O(n2) に落ちる.

ソースコード

コメントの部分が O(n3) の解法です.

class Solution {
    
public:
    int kInversePairs(int n, int k) {
        static long long dp[1024][1024];
        static long long conv[1024];
        
        for(int i = 0; i < 1024; i++) {
            for(int j = 0; j < 1024; j++) {
                dp[i][j] = 0;
            }
        }
        
        // 長さ1の数列で反転数=0の数
        dp[1][0] = 1;
        
        // 右からiを挿入したときの反転数.
        for(int i = 0; i < 1024; i++) {
            conv[i] = (i*(i+1)/2);
        }
        
        long long mod = 1e9 + 7LL; 
        
        // i: 長さiの数列
        for(int i = 1; i <= n; i++) {
            // a: 今の反転数(上限はk)
            /*
            for(int a = 0; a < min(conv[i], 1001LL); a++) {
                // j: 右からj番目に(i+1)を挿入する
                // 例) 
                // [1 2 3 4]
                // j = 0: [1 2 3 4 5], j = 1 : [1 2 3 5 4], ...
                for(int j = 0; j <= i; j++) {
                    if(a+j > k) break;
                    //printf("[i=%d] : next: %d: j= %d, conv[j] = %d, dp[i][a=%d] = %d\n", i, a+conv[j], j, conv[j], a, dp[i][a]);
                    
                    dp[i+1][a+j] += dp[i][a];
                    dp[i+1][a+j] %= mod;
                    
                }
            }
            */
            long long cnt = 0LL;
            for(int j = 0; j < min(conv[i], 1001LL); j++) {
                cnt += dp[i-1][j];
                if(j-i >= 0) {
                    cnt -= dp[i-1][j-i];
                }
                //printf("[i=%d] : j=%d, conv[j] = %d, cnt = %d\n", i, j, conv[j], cnt);

                dp[i][j] += cnt;
                dp[i][j] %= mod;
            }
        }

        return dp[n][k];
    }
};

所感

こういう問題をバグなく高速に通せるようにしておきたい.

第12回 JOI 本選 : Tower of JOIOI

概要

長さ N の 'J' 'O' 'I'の文字しか含まれない文字列 S が与えられる.

i < j < k において

  • s[i] = 'J' and S[j] = 'O' and S[k] = 'I' または
  • s[i] = 'I' and S[j] = 'O' and S[k] = 'I'

を満たす (i, j, k) の数の最大を求める.ただし,一度使った i, j, k は使うことができない.

考察

制約から O(nlogn) か?となる.

サンプルを試しながら性質を分析する.

  • IOIJOIにおいて,Oは共通の用途(真ん中)で使われることが分かる.
  • Iは左か右かの2通りの用途がある.
  • Jは左の用途しかない.

最初はdpっぽく解けるのかなぁと思ったけど部分問題に落とし込むことができなくなってこれは違うなと思った.

サンプルを試すと JO の次の Iに関して注意して考えると良さそうな気がしてくる.いろんな例で試してもあまり自明に思えないので,これは間違いっぽいということが分かる.

今は前から見ることばかり考えてたけど,後ろから I と O を決定すると,それより前のJを貪欲に使っていけそうなことが分かる.

ここまで考えて行き詰ったので解説を見る.

なるほど二分探索で右側のIの数を固定するのか,となって終了した.

ソースコード

http://joi2013ho.contest.atcoder.jp/submissions/1440781

所感

考察は良さそうなところまでいってる気はするけど,最後の詰めが出来ない. 最初の制約から計算量を推測するところで二分探索の可能性を頭の中に残しておくべきだった.

あと実装力が全然足りてないので,変な実装をして O(N2) になってたのも残念すぎる.

問題文からはそう見えないけど解答がクエリっぽいなと思った(今見ている添字の前の状態しか見る必要が無いので).

ABC 067

abc067.contest.atcoder.jp

久しぶりに参加した.

順位は 21th で早解きが苦手になっていると感じた.

残念なことにレーティングの更新対象ではないレーティングを持っているということすら忘れていた.

所感

A問題

A, B, A+Bに対してmod 3取ってやれば良い.

B問題

ソートする.

C問題

累積和.

D問題

与えられているグラフが木なので,フェネックとすぬけくんを結ぶパスは一つだけ存在する.

最適な行動とは書いているが,塗る頂点を最大化するように各自行動するので,フェネックとすぬけくんの間のパスに関してどれだけ多く塗ることができるかを考えれば良い.

これは幅優先探索フェネックとすぬけくん交互に塗ることができるマスを広げていけば良い.

この問題で,一般グラフが与えられた時はどうすればいいんだろうかと思った.

橋となるような辺を潰していくようにすれば,連結成分の頂点を得ることができるが,その連結成分への橋がいくつあるかにもよるし一意に定まらない気がする.

chainer 利用時のハマりどころ

chainerという機械学習フレームワークを使っていて,いくつか引っかかったところがあったのでメモしておく. 基本はエラーメッセージさえ読んだら解決する.

カスタム訓練・テストデータを用意する時

chainer.datasets.tuple_dataset.TupleDataset を使って画像データとラベルデータを紐付けるまでは良かったが trainer.run() で以下のようなエラーメッセージが出る.

    return xp.concatenate([array[None] for array in arrays])
TypeError: string indices must be integers

文字列の添字には整数を使用しなければいけないというエラーメッセージだが,最初どこが悪いのか良くわからなかった.

デバッグすると,ラベルの連結処理で死んでるということが分かった.

結局,ラベルをファイルから読み込んでリストに追加するという前処理をしていたのだが,そのときにラベルを string のままリストにしたのが悪く,np.int32で キャストすると上手く動いた.

配列の扱い

trainer.run() の時には特別意識する必要は無いが,学習済みのモデルに対してある入力に対する出力が欲しい時にひっかかった.

ValueError: numpy and cupy must not be used together
type(W): <class 'cupy.core.core.ndarray'>, type(x): <class 'numpy.ndarray'>, type(b): <class 'cupy.core.core.ndarray'>

numpycupy を同時に使うなというエラーメッセージで,gpu使っているのに numpy.ndarray を使おうとした時に遭遇する. これは注意していればそこまで問題ではない.

ubuntu上でisoファイルを書き込む

検索ワードが悪いのもあるが,あまり引っかからなかったためメモ.

環境

手順

  1. 標準で入っている Disk (gnome-disk-utility) を起動
  2. 認識されている USB のタブに移り
  3. パーティションイメージのリストアをクリック
  4. リストアするイメージに iso ファイルを選択
  5. リストアを開始