NASBench101のQuick Start

# はじめに
本記事では[NASBench101](https://github.com/google-research/nasbench)の導入方法と簡単な利用方法を説明します．
NASBenchを利用する方はかなり限定的な層であると考えられるため，NASBenchが何であるか，またどのような使い方をするのか，というような説明は一切省略します．
なお，Paperは[こちら](https://arxiv.org/pdf/1902.09635.pdf)にあります．

# 環境構築
はじめに環境構築に際して注意点を述べます．
1: TensorflowのVersionは1.15等の古いversionでないと[エラー](https://github.com/google-research/nasbench/issues/27)が発生する
2: 上述のエラーを回避するためには[python3.5 ~ 3.7を利用する必要](https://qiita.com/shoheihagiwara/items/5a3a4dac29b26836f185)がある

以上の注意点に留意しつつ以下のコマンドを実行することでNASBench101の環境構築が可能．

```shell
# NASBench101を使いたいディレクトリに移動
$ git clone https://github.com/google-research/nasbench
$ cd nasbench

# 必要な依存関係をInstall
$ pip install -e .
$ cd ..
# pathを通す
$ pip install ./nasbench

# data用のディレクトリを用意
$ mkdir benchmark
$ cd benchmark

# 単一budget sizeのTable data (500MB) を取得
$ wget https://storage.googleapis.com/nasbench/nasbench_only108.tfrecord

# 4種類のbudget sizeのTable data (2GB) を取得
$ wget https://storage.googleapis.com/nasbench/nasbench_full.tfrecord
```

また，公式ではないですが，こちらの[Version](https://github.com/nabenabe0928/nasbench)はtensorflow 2に対応しており，データの読み込みにかかる時間を元の2%程度 (つまり50倍速い) に抑えています．

# 実行テスト

```python
from nasbench import api

# datasetの読み込み
dataset = api.NASBench('benchmark/nasbench_only108.tfrecord')

# 有効な操作: 'conv1x1-bn-relu', 'conv3x3-bn-relu', 'maxpool3x3'
# 以下のリストはグラフに入れる操作群
# indexが各操作の頂点番号に対応する
labeling = ['input', 'conv1x1-bn-relu', 'maxpool3x3', 'conv1x1-bn-relu', 'maxpool3x3', 'conv3x3-bn-relu', 'output']

# 各操作同士の隣接行列
# 例えば，input layer vs 1x1 convが1ならそれらは辺を持つ
# 頂点の数は最大7個で辺の数は最大9個までという制約がある
# 以下，コメントアウトに存在する操作名は上述のlabelingの順番に対応する
matrix = [[0, 1, 1, 1, 0, 1, 0],  # input layer
          [0, 0, 0, 0, 0, 0, 1],  # conv1x1-bn-relu
          [0, 0, 0, 0, 0, 0, 1],  # maxpool3x3
          [0, 0, 0, 0, 1, 0, 0],  # conv1x1-bn-relu
          [0, 0, 0, 0, 0, 0, 1],  # maxpool3x3
          [0, 0, 0, 0, 0, 0, 1],  # conv3x3-bn-relu
          [0, 0, 0, 0, 0, 0, 0]]  # output layer

model_spec = api.ModelSpec(matrix, labeling)
_, metrics = dataset.get_metrics_from_spec(model_spec)

print(metrics)
```

```sh
Out: {108: [{'halfway_training_time': 510.31201171875, 'halfway_train_accuracy': 0.8297275900840759, 'halfway_validation_accuracy': 0.7688301205635071, 'halfway_test_accuracy': 0.7655248641967773, 'final_training_time': 1022.3150024414062, 'final_train_accuracy': 1.0, 'final_validation_accuracy': 0.9289863705635071, 'final_test_accuracy': 0.9185696840286255}, {'halfway_training_time': 509.9259948730469, 'halfway_train_accuracy': 0.9094551205635071, 'halfway_validation_accuracy': 0.8442507982254028, 'halfway_test_accuracy': 0.8363381624221802, 'final_training_time': 1021.072021484375, 'final_train_accuracy': 1.0, 'final_validation_accuracy': 0.9276843070983887, 'final_test_accuracy': 0.9186698794364929}, {'halfway_training_time': 509.8699951171875, 'halfway_train_accuracy': 0.9066506624221802, 'halfway_validation_accuracy': 0.8484575152397156, 'halfway_test_accuracy': 0.8387419581413269, 'final_training_time': 1021.427001953125, 'final_train_accuracy': 1.0, 'final_validation_accuracy': 0.9281851053237915, 'final_test_accuracy': 0.9254807829856873}]}
```

# 全探索
NAS-Bench101には423624個のArchitectureが存在します．
これらの数え上げ方を考えます．
上記のコードにおいて，頂点の数が `len(matrix)`，辺の数が `np.sum(matrix)` に対応する．
また，`labeling` の先頭要素と末尾要素はそれぞれ `input layer`, `output layer` でなければならない．
従って，単純な計算であれば，

- labelingの選択方法： $3^0 + 3^1 + 3^2 + 3^3 + 3^4 + 3^5 = 364$
- $n$ 頂点時の辺の選択方法 (単純連結グラフ・根がinput・ループなし)：解析的な値は（おそらく）ないですが，指数アルゴリズムで求められます (合計は$38259$になりました．)

|頂点数$n$|辺数$m$|総数|
|:--:|:--:|:--:|
| 2 | 1 | 1 |
| 3 | 2 | 1 |
| 3 | 3 | 2 |
| 4 | 3 | 2 |
| 4 | 4 | 7 |
| 4 | 5 | 11 |
| 4 | 6 | 12 |
| 5 | 4 | 6 |
| 5 | 5 | 33 |
| 5 | 6 | 83 |
| 5 | 7 | 132 |
| 5 | 8 | 159 |
| 5 | 9 | 167 |
| 6 | 5 | 24 |
| 6 | 6 | 192 |
| 6 | 7 | 722 |
| 6 | 8 | 1718 |
| 6 | 9 | 2957 |
| 7 | 6 | 120 |
| 7 | 7 | 1320 |
| 7 | 8 | 6970 |
| 7 | 9 | 23620 |

- 頂点の番号付けと辺の付け方による重複の削除

これらを考慮すると全探索できるはず．