Deep Mutual Learning (arxiv)

[1706.00384] Deep Mutual Learning

手法

  • distillationの進化系
  • 2つのネットワークを同時に学習させる
  • 通常通りのsupervised learning lossに加え、mimicry lossを使う
  • mimicry lossとは2つのネットワークの出力を似せたい(KLダイバージェンス

実験結果

  • distillationよりも精度が上がる
  • 明確にteacher-studentではなく同じネットワークを2つ用いた場合でも精度が上がる
  • 同時に学習させるネットワークの数を2から増やしてみるともっと精度が上がる
  • 直感としては、教師にアンサンブルを使うと良くなる気がするが、実験してみるとそれよりも複数のネットワーク同士のmimic lossを使う方が良くなるらしい

ただし、小規模なデータでしか実験されていない。著者らも考察しているが、どちらかというとunderfitの場合の話ではなくoverfitの場合の話であるようだ。普通に学習させてもtrain accuracyが100%に行くようなデータを用いているため、regularizationとして働いているっぽい気がする。そうなると、underfitな小規模ニューラルネットワークのoptimization difficultyを改善しモデルのキャパシティの限界を上げるというようなdistillationの話とはちょっと違う気がする。

PyPI でバージョン番号を変えず内容を変える

PyPI では、アップロードしたファイルを消すことが出来ても、置き換えることはできない。従って、あるバージョンでアップロードしてしまった後、そこにミスが発覚した場合、再アップロードして置き換えることは不可能である。

www.reddit.com

・・・というのが常識で、例えば上の reddit での議論でも、できないのが仕様ということになっている。

しかし、実は、1度だけチャンスがある。パッケージ作成で使うアーカイブのフォーマットを変えると再アップロードできる。具体的な手順は以下。

  • PyPI の Web 上で、'Remove' ボタンを使って、再アップロードしたいバージョンを一度削除する。
  • フォーマットに zip を指定してパッケージを作成しアップロードする。
python setup.py sdist --formats zip upload

仕組みとしては、PyPI は重複判定を単純にファイルが存在するかで判定しているらしく、しかも ‘Remove’ をしてもファイルは残ったままになっている。そこで、zip を指定すると、ファイル名が被らないので再アップロードができる(デフォルトは tar.gz)。

ちなみに、ドキュメントを見ると、一見 zip, tar.gz のみならず色々な種類のアーカイブがサポートされているように見える・・・が、PyPI がサポートしているのは zip, tar.gz のみであり、他のフォーマットを使うと以下のようなエラーになる。複数回チャンスがあると誤解すると危険なので注意。

Upload failed (400): Invalid file extension.
error: Upload failed (400): Invalid file extension.

「GNU開発ツール」を読んだのでビルド工程をマニュアル操作で進めてみる

www.oversea-pub.com

書籍に従いつつ手を動かしてみた時のメモ書き。gcc のバージョンの違いに注意して進めて行きます。

$ gcc -dumpversion
4.8

プリプロセス

C 言語ソース (.c) → 前処理済み C 言語ソース (.i)

$ cat hello.c
#include <stdio.h>

int main() {
  printf("Hello world\n");
  return 0;
}

$ cpp hello.c > hello.i

$ head hello.i
# 1 "hello.c"
# 1 "<built-in>"
# 1 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 1 "<command-line>" 2
# 1 "hello.c"
# 1 "/usr/include/stdio.h" 1 3 4
# 27 "/usr/include/stdio.h" 3 4
# 1 "/usr/include/features.h" 1 3 4
# 374 "/usr/include/features.h" 3 4

$ tail hello.i

extern void funlockfile (FILE *__stream) __attribute__ ((__nothrow__ , __leaf__));
# 943 "/usr/include/stdio.h" 3 4

# 2 "hello.c" 2

int main() {
  printf("Hello world\n");
  return 0;
}

コンパイル

前処理済み C 言語ソースファイル (.i) → アセンブリ言語ソースファイル (.s)

$ `gcc -print-prog-name=cc1` hello.i
 main
Analyzing compilation unit
Performing interprocedural optimizations
 <*free_lang_data> <visibility> <early_local_cleanups> <*free_inline_summary> <whole-program>Assembling functions:
 main
Execution times (seconds)
 phase setup             :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.00 ( 0%) wall    1094 kB (74%) ggc
 phase parsing           :   0.01 (100%) usr   0.00 ( 0%) sys   0.01 (33%) wall     329 kB (22%) ggc
 phase finalize          :   0.00 ( 0%) usr   0.00 ( 0%) sys   0.01 (33%) wall       0 kB ( 0%) ggc
 preprocessing           :   0.01 (100%) usr   0.00 ( 0%) sys   0.01 (33%) wall      25 kB ( 2%) ggc
 TOTAL                 :   0.01             0.00             0.03               1472 kB

$ cat hello.s
        .file   "hello.i"
        .section        .rodata
.LC0:
        .string "Hello world"
        .text
        .globl  main
        .type   main, @function
main:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movl    $.LC0, %edi
        call    puts
        movl    $0, %eax
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   main, .-main
        .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4"
        .section        .note.GNU-stack,"",@progbits

アセンブル

アセンブリ言語ソースファイル → オブジェクトファイル

$ as -o hello.o hello.s

$ file hello.o
hello.o: ELF 64-bit LSB  relocatable, x86-64, version 1 (SYSV), not stripped

$ readelf -S hello.o
There are 13 section headers, starting at offset 0x130:

Section Headers:
  [Nr] Name              Type             Address           Offset
       Size              EntSize          Flags  Link  Info  Align
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000000000  00000040
       0000000000000015  0000000000000000  AX       0     0     1
  [ 2] .rela.text        RELA             0000000000000000  00000590
       0000000000000030  0000000000000018          11     1     8
  [ 3] .data             PROGBITS         0000000000000000  00000055
       0000000000000000  0000000000000000  WA       0     0     1
  [ 4] .bss              NOBITS           0000000000000000  00000055
       0000000000000000  0000000000000000  WA       0     0     1
  [ 5] .rodata           PROGBITS         0000000000000000  00000055
       000000000000000c  0000000000000000   A       0     0     1
  [ 6] .comment          PROGBITS         0000000000000000  00000061
       000000000000002c  0000000000000001  MS       0     0     1
  [ 7] .note.GNU-stack   PROGBITS         0000000000000000  0000008d
       0000000000000000  0000000000000000           0     0     1
  [ 8] .eh_frame         PROGBITS         0000000000000000  00000090
       0000000000000038  0000000000000000   A       0     0     8
  [ 9] .rela.eh_frame    RELA             0000000000000000  000005c0
       0000000000000018  0000000000000018          11     8     8
  [10] .shstrtab         STRTAB           0000000000000000  000000c8
       0000000000000061  0000000000000000           0     0     1
  [11] .symtab           SYMTAB           0000000000000000  00000470
       0000000000000108  0000000000000018          12     9     8
  [12] .strtab           STRTAB           0000000000000000  00000578
       0000000000000013  0000000000000000           0     0     1
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings), l (large)
  I (info), L (link order), G (group), T (TLS), E (exclude), x (unknown)
  O (extra OS processing required) o (OS specific), p (processor specific)

$ objdump -j .rodata -s hello.o

hello.o:     file format elf64-x86-64

Contents of section .rodata:
 0000 48656c6c 6f20776f 726c6400           Hello world.

$ objdump -d hello.o

hello.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <main>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   bf 00 00 00 00          mov    $0x0,%edi
   9:   e8 00 00 00 00          callq  e <main+0xe>
   e:   b8 00 00 00 00          mov    $0x0,%eax
  13:   5d                      pop    %rbp
  14:   c3                      retq

$ nm hello.o
0000000000000000 T main
                 U puts
  • nm の T は .text セクションに含まれてることを意味し、U は Undefined の略で外部参照。

静的リンク

$ gcc -print-file-name=libc.a
/usr/lib/gcc/x86_64-linux-gnu/4.8/../../../x86_64-linux-gnu/libc.a

$ ar t `gcc -print-file-name=libc.a` | head
init-first.o
libc-start.o
sysdep.o
version.o
check_fds.o
libc-tls.o
elf-init.o
dso_handle.o
errno.o
init-arch.o

$ nm `gcc -print-file-name=libc.a` 2>/dev/null | grep -C 5 "T printf$"
                 U vfprintf

printf.o:
0000000000000000 T _IO_printf
0000000000000000 T __printf
0000000000000000 T printf
                 U stdout
                 U vfprintf

snprintf.o:
                 U _IO_vsnprintf
  • .a は ar コマンドで作成されたアーカイブファイルであり複数のオブジェクトファイルを連結したもの
$ ld -o hello_static `gcc -print-file-name=crt1.o` `gcc -print-file-name=crti.o` hello.o `gcc -print-file-name=libc.a` `gcc -print-file-name=libgcc_eh.a` `gcc -print-libgcc-file-name` `gcc -print-file-name=libc.a` `gcc -print-file-name=crtn.o`

$ ./hello_static
Hello world

$ ll hello_static
-rwxrwxr-x 1 872525 Jun  3 23:59 hello_static*

$ file hello_static
hello_static: ELF 64-bit LSB  executable, x86-64, version 1 (GNU/Linux), statically linked, for GNU/Linux 2.6.24, not stripped

動的リンク

$ file /lib/x86_64-linux-gnu/libc-2.19.so
/lib/x86_64-linux-gnu/libc-2.19.so: ELF 64-bit LSB  shared object, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), BuildID[sha1]=cf699a15caae64f50311fc4655b86dc39a479789, for GNU/Linux 2.6.24, stripped

$ nm /lib/x86_64-linux-gnu/libc-2.19.so
nm: /lib/x86_64-linux-gnu/libc-2.19.so: no symbols

$ readelf -s /lib/x86_64-linux-gnu/libc-2.19.so | grep " printf@@"
   596: 0000000000054340   161 FUNC    GLOBAL DEFAULT   12 printf@@GLIBC_2.2.5
  • strip コマンドで付加情報が削除されてる(= stripped) 場合、nm コマンドでは解析できない。
$ ld -o hello_dynamic `gcc -print-file-name=crt1.o` `gcc -print-file-name=crti.o` hello.o `gcc -print-libgcc-file-name` `gcc -print-file-name=crtn.o` -lc -dynamic-linker /lib64/ld-linux-x86-64.so.2

$ ./hello_dynamic
Hello world

$ ll hello_dynamic
-rwxrwxr-x 1 4907 Jun  4 00:06 hello_dynamic*

$ file hello_dynamic
hello_dynamic: ELF 64-bit LSB  executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, not stripped

$ readelf -l hello_dynamic

Elf file type is EXEC (Executable file)
Entry point 0x4003c0
There are 7 program headers, starting at offset 64

Program Headers:
  Type           Offset             VirtAddr           PhysAddr
                 FileSiz            MemSiz              Flags  Align
  PHDR           0x0000000000000040 0x0000000000400040 0x0000000000400040
                 0x0000000000000188 0x0000000000000188  R E    8
  INTERP         0x00000000000001c8 0x00000000004001c8 0x00000000004001c8
                 0x000000000000001c 0x000000000000001c  R      1
      [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
  LOAD           0x0000000000000000 0x0000000000400000 0x0000000000400000
                 0x0000000000000580 0x0000000000000580  R E    200000
  LOAD           0x0000000000000580 0x0000000000600580 0x0000000000600580
                 0x00000000000001cc 0x00000000000001cc  RW     200000
  DYNAMIC        0x0000000000000580 0x0000000000600580 0x0000000000600580
                 0x0000000000000190 0x0000000000000190  RW     8
  NOTE           0x00000000000001e4 0x00000000004001e4 0x00000000004001e4
                 0x0000000000000020 0x0000000000000020  R      4
  GNU_STACK      0x0000000000000000 0x0000000000000000 0x0000000000000000
                 0x0000000000000000 0x0000000000000000  RW     10

 Section to Segment mapping:
  Segment Sections...
   00
   01     .interp
   02     .interp .note.ABI-tag .hash .dynsym .dynstr .gnu.version .gnu.version_r .rela.dyn .rela.plt .init .plt .text .fini .rodata .eh_frame
   03     .dynamic .got .got.plt .data
   04     .dynamic
   05     .note.ABI-tag
   06
  • 64 bit 環境なので ld-linux のファイル名が違った。
$ ls
a.out

$ ./a.out
bash: ./a.out: No such file or directory

$ ./b.out
bash: ./b.out: No such file or directory
  • ELF ローダが正しく指定されてないプログラムを起動しようとすると、ファイル自体は有るのにまるでファイルが無いかのようなメッセージが出るの、面白すぎる。

日々のデバッグに役立ちそうな情報

$ ldd /bin/pwd
        linux-vdso.so.1 =>  (0x00007ffd4b9e3000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f5376114000)
        /lib64/ld-linux-x86-64.so.2 (0x00007f53764d9000)

$ LD_DEBUG=help /bin/pwd
Valid options for the LD_DEBUG environment variable are:

  libs        display library search paths
  reloc       display relocation processing
  files       display progress for input file
  symbols     display symbol table processing
  bindings    display information about symbol binding
  versions    display version dependencies
  scopes      display scope information
  all         all previous options combined
  statistics  display relocation statistics
  unused      determined unused DSOs
  help        display this help message and exit

To direct the debugging output into a file instead of standard output
a filename can be specified using the LD_DEBUG_OUTPUT environment variable.

$ LD_DEBUG=libs /bin/pwd
...

mypy のソースコードをちょっと読んだメモ

mypy は Python の型アノテーションを元に静的な型チェックを行うライブラリ。型推論を行い返り値の型などもチェックする。

起動からアルゴリズム部分に到達するまで

  • mypy コマンドは scripts/mypy が起動される
  • main.py の main
  • mypy.build.build が呼ばれる
  • dispatch メソッドが色々やってそう

全体の流れ

  • build.py の中にアルゴリズムや設計思想がテキストで説明してある
  • dispatch は ① load_graph(source) して ② process_graph(graph) する

load_graph

  • Graph とは str->State の dict
  • State は 1 つのモジュールに対応
  • エッジは基本的に import に対応
  • 空の graph からスタートし、BFS して依存関係を全列挙する
  • State はファイル名を与えられていながら依存性を出したりしてるので中でパースしてそう
  • State の self.tree が構文木っぽい
  • mypy.fastparse.parse がパースを担当する
  • 最初に Python 公式の typed-ast を使ってパースする https://github.com/python/typed_ast
  • それを ASTConverter という輩が mypy 独自の AST にコンバートする
  • 変換後の AST は nodes.py

process_graph

  • State を依存関係で SCC に分解し末尾から順に処理していく
  • fresh: キャッシュが既に有り処理不要
  • stale: キャッシュが古いので解析が必要
  • process_stale_scc の中で SCC 内部の解析が行われるようだ

process_stale_scc

  • Semantic Analysis
    • semantic_analysis
    • semantic_analysis_pass_three
    • semanal.pyの冒頭に説明がある
  • Type Check
    • type_check_first_pass
    • type_check_second_passを更新がなくなるまで繰り返す
    • checker.py

なんとなく何をしてるかは説明でわかったけど、具体的な処理を追うのは TODO。Any 型等の噂の見どころ(?)に到達したい。

感想

  • 循環 import を何とかするための工夫がかなり多い
  • 解析を高速化するためにファイルに対するキャッシュを作るらしく、そのキャッシュがあるか無いかとか、あっても後々の解析のために読まないといけないのかとか、その辺の場合分けのコードが多い

Numba のコードをちょっと読んだメモ

Numba は LLVM を使って Python のコードを JIT するライブラリ。

ちゃんと速い。https://gist.github.com/iwiwi/9228787711a353e115ffcdee21f1a882

@jit からコンパイル部分に到達するまで

  • @jitdecorators._jit → dispatcher というものが返される
  • 適当に動かした例では、dispatcher は registry.CPUDispatcher のようだ
  • こいつにはほぼ全く実装がない
  • 基底クラスは dispatcher.Dispatcher
  • その基底クラスは _DispatcherBase
  • その基底クラスは _dispatcher.Dispatcher で C extension 内
  • __call__ 時に JIT してると思うけど、__call___dispatcher.Dispatcher のものが呼ばれているようだ
  • _dispatcher.c 内の関数 Dispatcher_call に相当
    1. 呼び出された Python 関数の引数の型を確認しコンパイルできるか等調べる
    2. コンパイルする時は関数 compile_and_invoke を呼ぶ
    3. compile_and_invokeself._compile_for_args を呼ぶ
  • (後で調べる①:どこで返り値の型を推定した? → 分かった:返り値の型はここでは推定する必要がなく引数の型だけで良い)
  • (後で調べる②:なんで C extension に入ってるんだろう? → 速度のためだろうか・・・?)
  • _compile_for_args_DispatcherBase で定義されており、self.compile を呼ぶ
  • compileDispatcher で定義されており、キャッシュ等を調べたあと self._compiler.compile を呼ぶ
  • 適当に動かした例では、_compiler_FunctionCompiler のようだ
  • _FunctionCompiler.compilecompiler.py 内の compile_extra を呼ぶ
  • compiler.compile_extracompiler.Pipeline.complile_extra を呼ぶ
  • (見逃してなければ Python の関数はまだ Python の関数オブジェクトそのまま来てる)
  • compiler.Pipeline.complile_extra この辺が重要そう。
  • こいつは Python 関数オブジェクトをバイトコード化し、それをコンパイルする
  • ここから呼び出される _compile_core を見るとコンパイルのプロセスが書かれている

コンパイルのパイプライン

以下は nopython モードでのコンパイルのパイプライン

  1. Python bytecode を取り出す
  2. Python bytecode を Numba IR に変換
  3. Numba IR の後処理をする
  4. 型を推定・アノテートする
  5. LLVM IR を生成・コンパイル

1. Python bytecode を取り出す

  • bytecode.py 内の get_code_object で、関数.__code__ で取り出す

2. Python bytecode を Numba IR に変換

  • interpreter.py 内の Interpreter クラスに op_HOGE_PIYO 関数が大量にある
  • Numba の IR は ir.py 内に定義されるもので、Interpreter はこれを生成する

3. Numba IR の後処理をする

  • postproc.py 内の PostProcessor
  • ちゃんと読んでないけどあんまり長くないのであまり重要ではないと信じて進む

4. 型を推定・アノテートする

  • typeinfer.TypeInferer が作られる
  • TypeInferer に色々な事前情報を与える(seed_ほげほげ
  • build_constraint で式等による伝搬ルールを列挙する
  • propagate で constraint による情報を伝播し型を決めていく(収束までループするアルゴリズム

5. LLVM IR を生成・コンパイル

  • Pipeine.stage_nopython_backendPipeline._backendtargetctx.codegen()
  • targetctx は多分 CPUContextCUDATargetContext
  • CPUContext.codegenJITCPUCodegen に行く
  • JITCPUCodegen の基底クラス BaseCPUCodegenLLVM が llvmlite 経由で呼ばれている
  • _engine を見ると MCJIT を使っていることが分かる

メモ

Python から LLVM 叩くならこいつ便利そう https://github.com/numba/llvmlite

LLVM Tutorial をやったメモ

LLVM Tutorial: Table of Contents — LLVM 5 documentation

まだ途中までしかやってないです。Kaleidoscopeという言語の処理系を作っていきます。非常にシンプルな言語です。対話環境で入力されたコードをJITして実行します。

  • LLVM のバージョンで結構コードが動かないので、バージョンに合わせたチュートリアルを見ると良い。
  • 本文のコードは結構間違っている上に、全部の編集箇所を紹介するわけではないので、最終コードと適宜比較しながらやる。
  • 2章末尾で最初にコンパイルするタイミングで 「clang++ -g -O3 toy.cppコンパイルしよう!」とか言ってくるけど LLVM のファイルを include してるのでもっとオプションが必要。clang++ toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core`
  • JITに入る前、IR生成して表示する時点で既に定数が畳み込まれるのが観測できる。
  • KaleidoscopeJIT.h は GitHub とかでゲットすると良い。release_39 ブランチが LLVM 3.9 に相当。自分のバージョンに合わせて落とす。 llvm/KaleidoscopeJIT.h at release_39 · llvm-mirror/llvm · GitHub
  • putchard, printd が呼べない時はコンパイル引数に -rdynamic をつけてみる。
  • SSA, φ関数は日本語Wikipediaで普通にすぐ理解できる。 静的単一代入 - Wikipedia
  • チュートリアルに従って作ったJIT処理系が(コンパイルするから当然とはいえ)再帰で書いたfib(40)を0.5秒とかで計算できるのは結構感動した。 time ./a.out <<< "def fib(x) if x < 3 then 1 else fib(x - 1) + fib(x - 2) ; fib(40)"

分散システム 7章「フォールトトレラント性」

部分的な障害の発生は単体システムでは起こらない分散システムの問題である

フォールトトレラント性の導入

基本概念

高信頼性とは:

  • 可用性 (availability)・・・ある瞬間に正常に稼働している確率
  • 信頼性 (reliability)・・・障害を起こすことなくジョブが走り続けられる確率
  • 安全性 (safety)
  • 保守性 (maintainability)

1時間に1ミリ秒ダウンするシステムは可用性は高いが信頼性は低い。1年に2週間メンテナンスするシステムは前の例より可用性は低いが信頼性は高い。

障害の種類:

  • 過渡障害 (transient fault)・・・1度だけ起こるが消滅する
  • 間欠障害 (intermittent fault)・・・一時的に障害が現れることが繰り返す
  • 永久障害 (permanent fault)

障害モデル

  • クラッシュ障害
  • 欠落障害(受信欠落・送信欠落)
  • タイミング障害・・・指定時間内に応答できない
  • 応答障害(値障害、状態遷移障害)
  • 任意障害(ビザンチン障害)・・・最も深刻な障害

冗長性による障害の隠蔽

冗長性の種類:

  • 情報的冗長性・・・誤り訂正符号など
  • 時間的冗長性・・・リトライ
  • 物理的冗長性・・・余分な装置の付加

三重モジュール (TMR; Triple Modular Redundacy) による冗長性・・・電子回路を 3 重化しゲートの直後に毎回多数決を取る。

プロセスのレジリエンス

レジリエンス=いくつかのプロセスが故障した場合に、システムの残りの部分に大きなダメージを与えないようにするための技術

設計問題

プロセスグループ・・・同じ役割を担う複数のプロセスを作っておく

  • 平坦なグループ・・・全プロセスの役割が同じ
  • 階層的なグループ・・・調整プロセスと実行プロセス

障害隠蔽とレプリケーション

Kフォールトトレラント性・・・K個のコンポーネントが故障しても動作する

  • 停止するだけなら、K+1個あれば十分
  • ビザンチン障害を保つ場合、最低でも2K+1個必要

障害システムにおける同意

  • 2 つの軍隊問題・・・5000の軍隊を持つ赤軍が谷に野営。谷を見下ろす位置に3000+3000で2つの青軍が野営。赤軍に勝てるか?→障害のないプロセスしか考えないとしても信頼性のない通信を仮定すると、2つのプロセス間で合意形成はできない。
  • ビザンチン将軍問題・・・通信は完全だがプロセスは完全でない場合。mプロセスが裏切りに対して2m+1の正しく動作するプロセスが存在すると正しく動作できるアルゴリズム

TODO:6章(レプリケーション)を読む

高信頼クライアント・サーバ間通信

  • TCPのような高信頼転送プロトコルを用いる
  • クラッシュ時には再接続するしかない

TODO: 障害がある場合の遠隔手続き呼び出し

高信頼グループ間通信

  • 高信頼マルチキャストの基本手法・・・いくつかの仮定を踏まえた簡単なシステム:受信したらACKを送り、喪失に気づいたら再要求をする
  • アトミックマルチキャスト・・・全プロセスに送信されるか、全く送信されないかのどちらか
  • 仮想同期 (virtually synchronous)・・・アトミックマルチキャストであって、メッセージが送信されないのは送信者がクラッシュした場合のみ

TODO: 高信頼マルチキャストにおけるスケーラビリティ

分散コミット

分散コミット・・・あるオペレーションはグループ内の全てのメンバによって行われるか全く行われないかのいずれか(アトミックマルチキャストは分散コミットの1例)

1相コミット (one-phase commit) ・・・コーディネーターが実行するかどうかを通知する。参加者の1つが行うことができなくなった場合に、コーディネータに伝えることができなくなって困る。

2相コミット

  1. コーディネータ:VOTEをマルチキャスト
  2. 参加者:可否をコーディネータに報告
  3. コーディネータ:全員が可能ならCOMMITをマルチキャスト
  4. 参加者:COMMITを受信したら実行

いくつかのケースでブロッキングしてしまう問題がある。解決策の1つは3相コミットである。

回復

  • 後向きエラー回復・・・エラー状態から以前の正しい状態(チェックポイント)へシステムを巻き戻す。
  • 前向きエラー回復・・・実行を継続できる新しい状態に戦意させる。発生する可能性のあるエラーを事前に知っておく必要がある。

チェックポイントづくり

  • 回復ライン (recovery line) ・・・各プロセスのチェックポイントの組み合わせであって一貫性があるもの
  • 独立チェックポイントづくり・・独立にローカルな状態を記録し続ける
  • 協調チェックポイントづくり

BLAS, LINPACK, LAPACK

BLAS とは

ベクトルと行列に関する積や和などの基本的な操作を提供するライブラリのことっぽい。機能はレベルに分類されるらしい。

  • Level 1:ベクトル演算
  • Level 2:行列ベクトル演算
  • Level 3:行列同士の演算

有名な操作として GEMM (ジェム)がある。GEMM とは General Matrix Multiplication のことで、C = αAB + βC を計算する。

精度を頭につけて識別する。例えば SGEMM は 32bit float、DGEMM は 64bit float。

LINPACK, LAPACK とは

線形方程式や固有値問題などを解くための線形代数のライブラリ。BLAS を利用している。LAPACK は LINPACK の後継。両方 Fortran で書かれている。

BLAS と同様の命名規則が採用されているようだ。 DGESV は double (D) の一般行列 (GE) の方程式の求解 (SV) である。

BLAS の実装

ありがたい情報を貰いました……感謝!!

MKL は BLAS のみならず LAPACK や FFTW と互換性のある関数群も含んでいるらしいです。

CUDA の BLAS には NVIDIA 公式の cuBLAS がある。CUDA の LAPACK には CULA と MAGMA というものがあるようだ(どちらも公式ではなさそう)。

BLAS, LAPACK の間接的な利用

C++ を Python から呼ぶ方法まとめ

空のプロジェクトを PyPI に登録するまで

プロジェクトの名前を決めたらまずは PyPI で名前を予約しましょう。

PyPI にユーザ登録する

TestPyPI というお試しサイトにも登録しよう。

~/.pypirc を作る

パスワードを書かないでおくと実行時に聞いてもらえる。

[distutils]
index-servers =
  pypi
  pypitest

[pypi]
repository=https://pypi.python.org/pypi
username=<ユーザ名>

[pypitest]
repository=https://testpypi.python.org/pypi
username=<ユーザ名>

setup.py を作る

空のディレクトリに以下の内容で setup.py を置く。

from setuptools import find_packages
from setuptools import setup

setup(
    name='<パッケージ名>',
    version='0.0.1',
    description='<せつめい>',
    author='<名前>',
    author_email='<メールアドレス>',
    packages=find_packages(),
)

アップロード

$ python setup.py sdist upload -r pypitest  # お試し
$ python setup.py sdist upload  # ガチ

apt パッケージ探偵をするときに使うコマンド

会社のバイアリアン(?)の人の問題解決が僕の10倍ぐらい速い。僕も少しずつでもコマンドを覚えていきたい。

apt-cache show cuda-drivers
apt-cache depends cuda-drivers

dpkg -l | grep nvidia
dpkg -l | grep cuda

apt-get changelog cuda-8-0
apt-get download cuda-8-0

ar xv cuda-repo-ubuntu1404_8.0.44-1_amd64.deb

CNN による画像分類で使われる前処理・テスト時処理まとめ

とりあえず ImageNet 系の論文で、目に入ったものから順々にまとめていきます。情報・ツッコミ歓迎。

前処理・Data Augmentation

Mean Subtraction

入力画像から平均を引く。[103.939, 116.779, 123.68] を各ピクセルから引く。VGG はこれ。

Per-pixel Mean Subtraction

入力画像から平均を引く。ピクセル・チャンネルごとに計算された平均を引く。即ち、224x224x3 個の値について個別に平均を計算し用いる。AlexNet 論文から使われており、ResNet もこれ

Random Crop

256x256 ピクセルに画像をリサイズし、そこから 224x224 のパッチをランダムに取り出す。AlexNet 論文で使われていた。ちなみに Chainer の ImageNet サンプルはこれと Horizontal Flip をやっている(これしかやっていないので相応の精度しか出ない)。

Horizontal Flip

画像をランダムにフリップする。ImageNet では縦方向はなく水平方向の flip のみが使われるようであり、AlexNet 論文以降必ず使われているようだ。

Scale Augmentation

まず画像をリサイズする。[256, 480] からランダムに短辺の長さを選ぶ。次に、224x224 のパッチをそこからランダムサンプルする。

VGG 論文から使われており、ResNet 本家論文でも使われる。

Aspect Ratio Augmentation

上の Scale Augmentation に加え画像のアスペクト比を [¾, 4/3] で変換する・・・ぽい?(論文の記述が短くわかりにくい)

GoogLeNet の論文で使われている。FAIR の ResNet 再現記事でも使われており、本家から 1.2% の精度向上に寄与したらしい。

Color Augmentation

AlexNet 論文で行われた方法は以下である。各ピクセルの RGB を 3 次元のベクトルの集合だと考え PCA をかける。ガウス分布でノイズを生成し、固有ベクトル方向にノイズを加える。乱数は各ピクセルではなくパッチ全体に対して共通。論文によると AlexNet の精度への寄与は 1% 程度。ResNet 本家論文でも使われている。PCA した結果はここにあったり。

“Some Improvements on Deep Convolutional Neural Network Based Image Classification” 論文で行われた方法は以下である。contrast, brightness, color を、[0.5, 1.5] の間でランダムに変更する。変更の順番もランダムに選択する。(ご丁寧に、Python image library (PIL) を使ったと書いてある。)その後で、AlexNet 論文と同様の操作を行う。FAIR の ResNet 再現記事ではこれを利用したと書いてあったが、精度への寄与はとても小さかったらしい。

テスト時

Ensemble

複数のモデルを独立に学習し、それらの予測を平均する。

GoogLeNet 論文では、ネットワークは同じだが入力の処理法を変えた 7 つのモデルをアンサンブルしているらしい。GoogLeNet の論文は全体的に詳細が濁されているのでよくわからない。single crop だと top-5 error が 2% 弱程度向上。

ResNet 本家論文では、34B, 34C, 50, 101, 152×2 の 6 モデルをアンサンブルしている。fully-convolutional-form で top-5 error に 1% 弱程度向上。

10-crop Testing

テスト画像 1 つから data augmentation と類似した手順で 10 個のパッチを切り出し、それぞれに対する予測を平均して答える。

AlexNet 論文では、(4 スミ+中央)×(反転の有無)で 10 個のパッチを切り出している。GoogLeNet は 144 パッチも試してる。

GoogLeNet 論文では、crop 数の精度への影響が載っている。top-5 error で、10 crops で約 1% 弱向上、144 crops で 2% 強向上(下表は GoogLeNet 論文より引用)。

f:id:iwiwi:20161231213228p:plain

Fully-convolutional-form Testing

まず、全結合層たちを畳み込み層とみなす。例えば、直前の画像サイズが s×s であれば、最初の全結合層は s×s → 1×1 の畳み込み層であるとみなす。すると、ネットワークは fully convolutional (全レイヤーが畳み込み)となる。fully convolutional なネットワークの利点は、入力の画像サイズが変化しても適用することができることである(ただし、出力サイズも変化する)。

テスト画像をリサイズする。この時の画像サイズは、学習で使っている画像サイズと一致しているとは限らないし、正方形とも限らない。例えば、短辺を 480 にする。ネットワークをこの画像に適用する。出力を average pooling してそれを予測とする。

さらに、テスト画像のサイズを複数試し、その結果の平均を用いる。例えば、ResNet 本家論文では短辺を 224, 256, 384, 480, 640 になるようにリサイズしている。また、horizontal flip も試して平均を取る。

VGG から使われている。ResNet 本家論文を見るところ、10-crop Testing と比べて、大体 2% 程度精度に寄与している。

Chainer で全結合層を畳み込み層にするコードの例を mitmul さんから貰ったので貼っておきます。

def linear2conv(model, name, feature_size=1):
    """Convert Linear layer to 1x1 Convolution Layer
    args:
        model (chainer.Chain): The input model
        name (str): Name of a Linear link that will be converted to 1x1 conv
            ex. '/predictor/trunk/fc6'
        feature_size (int): The feature map size of convolution layer
    """
    target = model
    lnames = [n for n in name.split('/') if len(n) > 0]
    for l in lnames[:-1]:
        target = target.__dict__[l]
    t = target.__dict__[lnames[-1]]
    assert ('Linear' in str(t.__class__))
    out_dim, in_dim = t.W.data.shape
    in_dim = in_dim // (feature_size ** 2)
    conv = L.Convolution2D(in_dim, out_dim, feature_size)
    W = t.W.data.reshape((out_dim, in_dim, feature_size, feature_size))
    conv.W.data, conv.b.data = W, t.b.data
    target.__dict__[lnames[-1]] = conv
    return model

参考文献

謝辞

  • 宮戸さん
  • mitmul さん

スヌープモードを設定して QPI を爆速で超える

スヌープモードの影響

マルチ CPU のマシンでメモリ帯域を測ると、別ソケット側のメモリとの帯域が死ぬほど遅いという現象がある。これは、CPU のスヌープモードがデフォルトの「Early Snoop」になっているからである。BIOS からこれを「Home Snoop」に変更することによって、帯域は大きく向上する。

software.intel.com

この記事によると、Early Snoop では 6GB/s 程度であったのが、Home Snoop では 25GB/s 程度になっている。

ただし、Home Snoop にすると、代償として同一 NUMA ノード内でのレイテンシが 10% 程度悪くなってしまう。

スヌープとは

キャッシュメモリ - Wikipedia

キャッシュコヒーレンシを保つ方法の 1 つがスヌープ方式(スヌープキャッシュ)である。各キャッシュメモリが、自身とよそのキャッシュラインの状況を管理し、メッセージにより情報交換を行う方式である。この情報交換の方式に、MESI プロトコル等が含まれる。

スヌープ方式以外のアプローチは、ディレクトリ方式、共有キャッシュなどである。

スヌープモードとは

software.intel.com

技術的詳細は分からないが、スヌープモードを変更すると、このスヌープのアルゴリズムが切り替わると思われる。ちなみに、上述の Early Snoop, Home Snoop の他に Cluster on Die (COD) モードというのがある。これは、他の NUMA ノードへのアクセスがかなり少ない仮定を置いたモードのようで、仮想マシンを扱う場合などを想定しているようだ。

数列の和を計算するアルゴリズム

数列の和の計算にアルゴリズムなんて考える余地はあるのか?と思ったが、誤差についても考える場合、単純な方法以外にも複数のアルゴリズムが存在し使われているということを教えてもらった。

Kahan summation はより高い精度を達成できるが、pairwise summation のほうが高速である。NumPy の sum では pairwise summation algorithm が使われているようだ。

ちなみに、分散を計算する際には専用のアルゴリズムもある。