Google Kickstart 2020 Round 1B - Wandering Robot の解説

Google Kickstart 2020 Round 1Bの最後の問題、Wandering Robot についてやっと理解できたので解説を書きます。

問題概要

W*Hの盤面が与えられる。盤面には ある矩形1つ分の穴が空いている。ロボットは左上の(1, 1)を出発し、等確率で右か下に移動する。ただし盤面の右端に到達した場合は必ず下に、盤面の下端に到達した場合は必ず右に移動する。ロボットが穴に落ちずに盤面の右下(W, H)に到着できる確率を求めよ。

着想

例えば以下の盤面を考えます。■は穴を表します。

f:id:minus9d:20200430231500p:plain

★に着目してください。ロボットが右下に到達するためには、必ず★のどれか一つを通らなければいけません。かつ、★を2つ以上通ることはできません。なので、各★を通る確率を個別に求め、その和をとれば、答が求まりそうです。

各セルを通る確率は、以下のように求められます。さきほどの盤面の場合、3つの★の確率の和 1/16 + 4/16 + 1/8 = 7/16 = 0.4375 が答になります。

f:id:minus9d:20200430231821p:plain

上記の確率はいかにも二項分布で一般化できそうな形をしています。しかし、上図であえて空白にしている部分の確率はどうでしょうか。すべての確率を求めた図を以下に示します。ロボットが右端 or 下端に達したときは確率1で移動方向が決定するため、二項分布の法則が崩れます。

f:id:minus9d:20200430234324p:plain

なので、以下のような盤面が与えられたとき、★の部分の確率の和を求めるのは一筋縄ではいきません。

f:id:minus9d:20200430234337p:plain

工夫1: 仮想盤面の導入

本ラウンド1位のscotwu氏の回答 がそれへの解になります。この回答では、まるでロボットが右端や下端を無視して移動し続けられるかのような仮想盤面を考えます。

xxxf:id:minus9d:20200430234414p:plain

上の仮想盤面において☆の確率を足すと、ちょうど前の盤面の★の確率の和と同じになっていることが分かります!! 仮想盤面では二項分布の法則が崩れないので、確率の計算が容易です。

ただし、穴が盤面の下または右に接するコーナーケースに注意です。以下の例の場合、×印で示した★の確率を足してはいけません。

f:id:minus9d:20200501214850p:plain

工夫2: logの計算

本質的にはここまでの説明で解けたようなものですが、実際に確率を算出するためにはもうひと工夫必要です。

ロボットがマス(x, y)を通過する確率は C((x - 1) + (y - 1), (x - 1)) / 2^((x - 1) + (y - 1)) で書けます(ここで、C(n, k)は二項分布)。しかし、分子も分母も巨大な整数になるため愚直に計算すると計算時間がかかりすぎます。

そこで、分子、分母それぞれを底を2とするlogをとることで、計算時間を抑えることができます。C(n, k) = n! / k! (n - k)! なので、1!, 2!, 3!, ... それぞれについて底を2とするlogの値を前計算で求めておけばOKです。

コード

Python 3です。

#!/usr/bin/env python3

import math


# log2(n!)のテーブルを作成
log_table = [0] * 200001
log_value = 0
for i in range(1, 200001):
    log_value += math.log(i, 2)
    log_table[i] = log_value


def log_of_choose(n, k):
    """log C(n, k)を求める"""
    return log_table[n] - log_table[k] - log_table[n - k]


def calc_probability(x, y):
    """(1, 1)から(x, y)に到着する確率を求める
    """
    x -= 1
    y -= 1
    return log_of_choose(x + y, x) - (x + y)


def solve_fast(W, H, L, U, R, D):

    ans = 0.0

    # ◎の部分を下から順に
    # □□□□□◎
    # □□□□◎
    # □□□■□
    # □□□■□
    # □□□□□
    if R != W:
        x = R + 1
        y = U - 1
        while y >= 1:
            log2_of_prob = calc_probability(x, y)
            ans += pow(2, log2_of_prob)
            x += 1
            y -= 1

    # ◎の部分を右から順に
    # □□□□□
    # □□□□□
    # □□□■□
    # □□□■□
    # □□◎□□
    #  ◎
    # ◎
    if D != H:
        x = L - 1
        y = D + 1
        while x >= 1:
            log2_of_prob = calc_probability(x, y)
            ans += pow(2, log2_of_prob)
            x -= 1
            y += 1

    return ans


def solve():
    W, H, L, U, R, D = map(int, input().split())
    print("{:.20f}".format(solve_fast(W, H, L, U, R, D)))


T = int(input())
for testcase in range(T):
    print("Case #{}: ".format(testcase+1), end="")
    solve()

Dockerfileでkeras環境を作成する練習

Docker ImageからContainerを作るコマンドのまとめ - minus9d's diary の続きです。今回はKeras環境を備えるDocker Imageを作成する練習をしてみました。普通であればTensorflow公式のDocker Imageを使うのが正しいと思いますが、練習なので気にしないことにします。

この記事では私の試行錯誤の過程をそのまま記述しています。最終的なDockerfileは末尾に記載しています。

最初のDockerfile

まず、以下のようなDockerfileを作成します。

FROM nvidia/cuda:10.2-cudnn7-devel-ubuntu18.04

RUN apt-get update && apt-get install -y \
    python3-pip \
    wget

RUN pip3 install tensorflow-gpu && pip3 install keras

RUN wget https://raw.githubusercontent.com/keras-team/keras/master/examples/cifar10_cnn.py

CMD python3 cifar10_cnn.py

以下、Dockerfileの簡単な解説です。

一行目のFROM nvidia/cudaで、Docker Hub にあるNVIDIA公式のCUDAの環境をベースイメージとして指定します。

二行目のapt-getで、あとで必要になるバイナリの習得を行います。つい手癖でapt-get updateの後はapt-get upgradeしたくなりますが、Best practices for writing Dockerfilesによるとapt-get upgradeは避けるべきだそうです。また、apt-get updateと、apt-get install -y XXXは同じRUN命令で同時に実行すべきだそうです。

三行目でtensorflow-gpuとkerasをインストールします。

四行目でkerasのサンプルスクリプトをダウンロードします。

次に、このDockerfileをもとにDocker Imageを作成します。このDockerfileと同じディレクトリにて

$ docker build -t mykerasimage .

とすることで、mykerasimageという名前のDocker Imageを作成します。

次に、このDocker Imageから、コンテナを作成して実行します。

$ docker run -it mykerasimage

とすると、Dockerfileの最終行に書いたpython3 cifar10_cnn.pyがコンテナ内で実行されます。

以下はそのときのログです。

$ docker run -it mykerasimage
Using TensorFlow backend.
/usr/local/lib/python3.6/dist-packages/tensorflow/python/framework/dtypes.py:516: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  _np_qint8 = np.dtype([("qint8", np.int8, 1)])
/usr/local/lib/python3.6/dist-packages/tensorflow/python/framework/dtypes.py:517: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  _np_quint8 = np.dtype([("quint8", np.uint8, 1)])
/usr/local/lib/python3.6/dist-packages/tensorflow/python/framework/dtypes.py:518: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  _np_qint16 = np.dtype([("qint16", np.int16, 1)])
/usr/local/lib/python3.6/dist-packages/tensorflow/python/framework/dtypes.py:519: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  _np_quint16 = np.dtype([("quint16", np.uint16, 1)])
/usr/local/lib/python3.6/dist-packages/tensorflow/python/framework/dtypes.py:520: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  _np_qint32 = np.dtype([("qint32", np.int32, 1)])
/usr/local/lib/python3.6/dist-packages/tensorflow/python/framework/dtypes.py:525: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  np_resource = np.dtype([("resource", np.ubyte, 1)])
/usr/local/lib/python3.6/dist-packages/tensorboard/compat/tensorflow_stub/dtypes.py:541: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  _np_qint8 = np.dtype([("qint8", np.int8, 1)])
/usr/local/lib/python3.6/dist-packages/tensorboard/compat/tensorflow_stub/dtypes.py:542: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  _np_quint8 = np.dtype([("quint8", np.uint8, 1)])
/usr/local/lib/python3.6/dist-packages/tensorboard/compat/tensorflow_stub/dtypes.py:543: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  _np_qint16 = np.dtype([("qint16", np.int16, 1)])
/usr/local/lib/python3.6/dist-packages/tensorboard/compat/tensorflow_stub/dtypes.py:544: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  _np_quint16 = np.dtype([("quint16", np.uint16, 1)])
/usr/local/lib/python3.6/dist-packages/tensorboard/compat/tensorflow_stub/dtypes.py:545: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  _np_qint32 = np.dtype([("qint32", np.int32, 1)])
/usr/local/lib/python3.6/dist-packages/tensorboard/compat/tensorflow_stub/dtypes.py:550: FutureWarning: Passing (type, 1) or '1type' as a synonym of type is deprecated; in a future version of numpy, it will be understood as (type, (1,)) / '(1,)type'.
  np_resource = np.dtype([("resource", np.ubyte, 1)])
Downloading data from https://www.cs.toronto.edu/~kriz/cifar-10-python.tar.gz
170500096/170498071 [==============================] - 130s 1us/step
x_train shape: (50000, 32, 32, 3)
50000 train samples
10000 test samples
WARNING:tensorflow:From /usr/local/lib/python3.6/dist-packages/keras/backend/tensorflow_backend.py:4070: The name tf.nn.max_pool is deprecated. Please use tf.nn.max_pool2d instead.

Using real-time data augmentation.
2020-04-07 14:16:02.853936: I tensorflow/core/platform/cpu_feature_guard.cc:142] Your CPU supports instructions that this TensorFlow binary was not compiled to use: AVX2 FMA
2020-04-07 14:16:02.857300: I tensorflow/stream_executor/platform/default/dso_loader.cc:53] Could not dlopen library 'libcuda.so.1'; dlerror: libcuda.so.1: cannot open shared object file: No such file or directory; LD_LIBRARY_PATH: /usr/local/nvidia/lib:/usr/local/nvidia/lib64
2020-04-07 14:16:02.857318: E tensorflow/stream_executor/cuda/cuda_driver.cc:318] failed call to cuInit: UNKNOWN ERROR (303)
2020-04-07 14:16:02.857334: I tensorflow/stream_executor/cuda/cuda_diagnostics.cc:163] no NVIDIA GPU device is present: /dev/nvidia0 does not exist
2020-04-07 14:16:02.875675: I tensorflow/core/platform/profile_utils/cpu_utils.cc:94] CPU Frequency: 3600000000 Hz
2020-04-07 14:16:02.876032: I tensorflow/compiler/xla/service/service.cc:168] XLA service 0x453cdb0 executing computations on platform Host. Devices:
2020-04-07 14:16:02.876049: I tensorflow/compiler/xla/service/service.cc:175]   StreamExecutor device (0): <undefined>, <undefined>
2020-04-07 14:16:02.915462: W tensorflow/compiler/jit/mark_for_compilation_pass.cc:1412] (One-time warning): Not using XLA:CPU for cluster because envvar TF_XLA_FLAGS=--tf_xla_cpu_global_jit was not set.  If you want XLA:CPU, either set that envvar, or use experimental_jit_scope to enable XLA:CPU.  To confirm that XLA is active, pass --vmodule=xla_compilation_cache=1 (as a proper command-line flag, not via TF_XLA_FLAGS) or set the envvar XLA_FLAGS=--xla_hlo_profile.
WARNING:tensorflow:From /usr/local/lib/python3.6/dist-packages/keras/backend/tensorflow_backend.py:422: The name tf.global_variables is deprecated. Please use tf.compat.v1.global_variables instead.

Epoch 1/100
1563/1563 [==============================] - 63s 40ms/step - loss: 1.8523 - accuracy: 0.3178 - val_loss: 1.5431 - val_accuracy: 0.4363
Epoch 2/100
1563/1563 [==============================] - 63s 40ms/step - loss: 1.5708 - accuracy: 0.4255 - val_loss: 1.3986 - val_accuracy: 0.4933
Epoch 3/100
1563/1563 [==============================] - 62s 40ms/step - loss: 1.4585 - accuracy: 0.4721 - val_loss: 1.3288 - val_accuracy: 0.5212
Epoch 4/100
1563/1563 [==============================] - 62s 40ms/step - loss: 1.3764 - accuracy: 0.5028 - val_loss: 1.2310 - val_accuracy: 0.5604
(以下略)

このログをよく見ると、Could not dlopen library 'libcuda.so.1' failed call to cuInit: UNKNOWN ERROR (303) などの不穏なエラーが並んでいることがわかります。これは、私が NVIDIA Docker の環境を作らなかったことが原因だと思われます。ただ、これらのエラーが出るにもかかわらずサンプルファイルは実行できているようにも見え、謎です…。

NVIDIA Dockerの導入

NVIDIA Dockerの導入は、NVIDIAの中の人が記した NVIDIA Docker って今どうなってるの? (19.11版) - Qiita が歴史的経緯も含めてまとめられていてわかりやすいです。今回は「Docker 19.03 以降の環境で前だけを見て生きる場合」に従い、NVIDIA Dockerの追加インストールを行いました。

そして今度は、コンテナ内で使用するGPUを指定するオプション--gpuを付与して、改めてコンテナを作ります。

$ docker run --gpus all -it mykerasimage 

以下はその実行結果です。さきほどの不穏なエラーは消えましたが、代わりにlibcudart.so.10.0が見つからないというエラーなどが出ました。

(略)
Using real-time data augmentation.
2020-04-07 14:30:25.187308: I tensorflow/core/platform/cpu_feature_guard.cc:142] Your CPU supports instructions that this TensorFlow binary was not compiled to use: AVX2 FMA
2020-04-07 14:30:25.191128: I tensorflow/stream_executor/platform/default/dso_loader.cc:42] Successfully opened dynamic library libcuda.so.1
2020-04-07 14:30:25.281694: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:1005] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-07 14:30:25.282141: I tensorflow/compiler/xla/service/service.cc:168] XLA service 0x34f5f90 executing computations on platform CUDA. Devices:
2020-04-07 14:30:25.282156: I tensorflow/compiler/xla/service/service.cc:175]   StreamExecutor device (0): GeForce GTX 1070, Compute Capability 6.1
2020-04-07 14:30:25.303626: I tensorflow/core/platform/profile_utils/cpu_utils.cc:94] CPU Frequency: 3600000000 Hz
2020-04-07 14:30:25.303940: I tensorflow/compiler/xla/service/service.cc:168] XLA service 0x3e90720 executing computations on platform Host. Devices:
2020-04-07 14:30:25.303972: I tensorflow/compiler/xla/service/service.cc:175]   StreamExecutor device (0): <undefined>, <undefined>
2020-04-07 14:30:25.304181: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:1005] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-07 14:30:25.304464: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1640] Found device 0 with properties: 
name: GeForce GTX 1070 major: 6 minor: 1 memoryClockRate(GHz): 1.683
pciBusID: 0000:01:00.0
2020-04-07 14:30:25.304599: I tensorflow/stream_executor/platform/default/dso_loader.cc:53] Could not dlopen library 'libcudart.so.10.0'; dlerror: libcudart.so.10.0: cannot open shared object file: No such file or directory; LD_LIBRARY_PATH: /usr/local/nvidia/lib:/usr/local/nvidia/lib64
2020-04-07 14:30:25.304673: I tensorflow/stream_executor/platform/default/dso_loader.cc:53] Could not dlopen library 'libcublas.so.10.0'; dlerror: libcublas.so.10.0: cannot open shared object file: No such file or directory; LD_LIBRARY_PATH: /usr/local/nvidia/lib:/usr/local/nvidia/lib64
2020-04-07 14:30:25.304742: I tensorflow/stream_executor/platform/default/dso_loader.cc:53] Could not dlopen library 'libcufft.so.10.0'; dlerror: libcufft.so.10.0: cannot open shared object file: No such file or directory; LD_LIBRARY_PATH: /usr/local/nvidia/lib:/usr/local/nvidia/lib64
2020-04-07 14:30:25.304810: I tensorflow/stream_executor/platform/default/dso_loader.cc:53] Could not dlopen library 'libcurand.so.10.0'; dlerror: libcurand.so.10.0: cannot open shared object file: No such file or directory; LD_LIBRARY_PATH: /usr/local/nvidia/lib:/usr/local/nvidia/lib64
2020-04-07 14:30:25.304880: I tensorflow/stream_executor/platform/default/dso_loader.cc:53] Could not dlopen library 'libcusolver.so.10.0'; dlerror: libcusolver.so.10.0: cannot open shared object file: No such file or directory; LD_LIBRARY_PATH: /usr/local/nvidia/lib:/usr/local/nvidia/lib64
2020-04-07 14:30:25.304950: I tensorflow/stream_executor/platform/default/dso_loader.cc:53] Could not dlopen library 'libcusparse.so.10.0'; dlerror: libcusparse.so.10.0: cannot open shared object file: No such file or directory; LD_LIBRARY_PATH: /usr/local/nvidia/lib:/usr/local/nvidia/lib64
2020-04-07 14:30:25.395108: I tensorflow/stream_executor/platform/default/dso_loader.cc:42] Successfully opened dynamic library libcudnn.so.7
2020-04-07 14:30:25.395193: W tensorflow/core/common_runtime/gpu/gpu_device.cc:1663] Cannot dlopen some GPU libraries. Skipping registering GPU devices...
2020-04-07 14:30:25.395243: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1181] Device interconnect StreamExecutor with strength 1 edge matrix:
2020-04-07 14:30:25.395275: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1187]      0 
2020-04-07 14:30:25.395302: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1200] 0:   N 
2020-04-07 14:30:25.472855: W tensorflow/compiler/jit/mark_for_compilation_pass.cc:1412] (One-time warning): Not using XLA:CPU for cluster because envvar TF_XLA_FLAGS=--tf_xla_cpu_global_jit was not set.  If you want XLA:CPU, either set that envvar, or use experimental_jit_scope to enable XLA:CPU.  To confirm that XLA is active, pass --vmodule=xla_compilation_cache=1 (as a proper command-line flag, not via TF_XLA_FLAGS) or set the envvar XLA_FLAGS=--xla_hlo_profile.
WARNING:tensorflow:From /usr/local/lib/python3.6/dist-packages/keras/backend/tensorflow_backend.py:422: The name tf.global_variables is deprecated. Please use tf.compat.v1.global_variables instead.

Epoch 1/100
1563/1563 [==============================] - 63s 40ms/step - loss: 1.9029 - accuracy: 0.3008 - val_loss: 1.5870 - val_accuracy: 0.4238
Epoch 2/100
1563/1563 [==============================] - 63s 40ms/step - loss: 1.5875 - accuracy: 0.4180 - val_loss: 1.3819 - val_accuracy: 0.4944

$ docker run --gpus all -it mykerasimage bashでコンテナの中を探ってみると、libcudart.so.10.0は存在せず、かわりに/usr/local/cuda-10.2/targets/x86_64-linux/lib/libcudart.so.10.2があるのみでした。また、 tensorflow-gpuのバージョンが1.14.0と古いことに気づきました。tensorflow-gpu 1.14.0はCUDA 10.0を要求するにもかかわらず、CUDA 10.2のベースイメージを用意してしまったのが失敗でした。

ベースイメージの見直しとpip3の更新

この反省をもとに、現時点で最新である tensorflow-gpu 2.1 と、これが要求するCUDA 10.1の組み合わせを実現するDockerfileを書き直すことにしました。

書き直したDockerfileを以下に示します。ベースイメージをCUDA 10.1に変更し、かつ、pip3を最新版に更新(現時点で20.0.2)してから、tensorflow-gpuとkerasをバージョン指定で入れるようにしました。

FROM nvidia/cuda:10.1-cudnn7-devel-ubuntu18.04

RUN apt-get update && apt-get install -y \
    python3-pip \
    wget

RUN pip3 install --upgrade pip

RUN pip3 install tensorflow-gpu && pip3 install keras

RUN wget https://raw.githubusercontent.com/keras-team/keras/master/examples/cifar10_cnn.py

CMD python3 cifar10_cnn.py

このDockerfileをもとにDocker Imageを再作成し、docker run --gpus all -it mykerasimageしたときのログを以下に示します。まだlibnvinfer.so.6, libnvinfer_plugin.so.6 などがロードできない旨のエラーが出ていますが、それ以外は正しく動いていそうです。

$ docker run --gpus all -it mykerasimage     
Using TensorFlow backend.
2020-04-08 01:11:33.204351: W tensorflow/stream_executor/platform/default/dso_loader.cc:55] Could not load dynamic library 'libnvinfer.so.6'; dlerror: libnvinfer.so.6: cannot open shared object file: No such file or directory; LD_LIBRARY_PATH: /usr/local/nvidia/lib:/usr/local/nvidia/lib64
2020-04-08 01:11:33.204485: W tensorflow/stream_executor/platform/default/dso_loader.cc:55] Could not load dynamic library 'libnvinfer_plugin.so.6'; dlerror: libnvinfer_plugin.so.6: cannot open shared object file: No such file or directory; LD_LIBRARY_PATH: /usr/local/nvidia/lib:/usr/local/nvidia/lib64
2020-04-08 01:11:33.204496: W tensorflow/compiler/tf2tensorrt/utils/py_utils.cc:30] Cannot dlopen some TensorRT libraries. If you would like to use Nvidia GPU with TensorRT, please make sure the missing libraries mentioned above are installed properly.
Downloading data from https://www.cs.toronto.edu/~kriz/cifar-10-python.tar.gz
170500096/170498071 [==============================] - 91s 1us/step
x_train shape: (50000, 32, 32, 3)
50000 train samples
10000 test samples
2020-04-08 01:13:07.198910: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcuda.so.1
2020-04-08 01:13:07.217257: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:981] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-08 01:13:07.217949: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1555] Found device 0 with properties: 
pciBusID: 0000:01:00.0 name: GeForce GTX 1070 computeCapability: 6.1
coreClock: 1.683GHz coreCount: 15 deviceMemorySize: 7.93GiB deviceMemoryBandwidth: 238.66GiB/s
2020-04-08 01:13:07.219716: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcudart.so.10.1
2020-04-08 01:13:07.273601: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcublas.so.10
2020-04-08 01:13:07.308268: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcufft.so.10
2020-04-08 01:13:07.317546: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcurand.so.10
2020-04-08 01:13:07.384937: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcusolver.so.10
2020-04-08 01:13:07.393726: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcusparse.so.10
2020-04-08 01:13:07.493477: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcudnn.so.7
2020-04-08 01:13:07.493865: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:981] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-08 01:13:07.495793: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:981] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-08 01:13:07.497123: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1697] Adding visible gpu devices: 0
2020-04-08 01:13:07.497893: I tensorflow/core/platform/cpu_feature_guard.cc:142] Your CPU supports instructions that this TensorFlow binary was not compiled to use: AVX2 FMA
2020-04-08 01:13:07.538725: I tensorflow/core/platform/profile_utils/cpu_utils.cc:94] CPU Frequency: 3600000000 Hz
2020-04-08 01:13:07.539661: I tensorflow/compiler/xla/service/service.cc:168] XLA service 0x40f4d80 initialized for platform Host (this does not guarantee that XLA will be used). Devices:
2020-04-08 01:13:07.539710: I tensorflow/compiler/xla/service/service.cc:176]   StreamExecutor device (0): Host, Default Version
2020-04-08 01:13:07.637951: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:981] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-08 01:13:07.638329: I tensorflow/compiler/xla/service/service.cc:168] XLA service 0x417adc0 initialized for platform CUDA (this does not guarantee that XLA will be used). Devices:
2020-04-08 01:13:07.638342: I tensorflow/compiler/xla/service/service.cc:176]   StreamExecutor device (0): GeForce GTX 1070, Compute Capability 6.1
2020-04-08 01:13:07.638458: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:981] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-08 01:13:07.638711: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1555] Found device 0 with properties: 
pciBusID: 0000:01:00.0 name: GeForce GTX 1070 computeCapability: 6.1
coreClock: 1.683GHz coreCount: 15 deviceMemorySize: 7.93GiB deviceMemoryBandwidth: 238.66GiB/s
2020-04-08 01:13:07.638738: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcudart.so.10.1
2020-04-08 01:13:07.638750: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcublas.so.10
2020-04-08 01:13:07.638759: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcufft.so.10
2020-04-08 01:13:07.638770: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcurand.so.10
2020-04-08 01:13:07.638785: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcusolver.so.10
2020-04-08 01:13:07.638808: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcusparse.so.10
2020-04-08 01:13:07.638827: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcudnn.so.7
2020-04-08 01:13:07.638878: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:981] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-08 01:13:07.639220: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:981] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-08 01:13:07.639473: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1697] Adding visible gpu devices: 0
2020-04-08 01:13:07.639501: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcudart.so.10.1
2020-04-08 01:13:07.641096: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1096] Device interconnect StreamExecutor with strength 1 edge matrix:
2020-04-08 01:13:07.641107: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1102]      0 
2020-04-08 01:13:07.641113: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1115] 0:   N 
2020-04-08 01:13:07.641218: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:981] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-08 01:13:07.641555: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:981] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2020-04-08 01:13:07.641833: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1241] Created TensorFlow device (/job:localhost/replica:0/task:0/device:GPU:0 with 7011 MB memory) -> physical GPU (device: 0, name: GeForce GTX 1070, pci bus id: 0000:01:00.0, compute capability: 6.1)
Using real-time data augmentation.
Epoch 1/100
2020-04-08 01:13:11.232517: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcublas.so.10
2020-04-08 01:13:11.745019: I tensorflow/stream_executor/platform/default/dso_loader.cc:44] Successfully opened dynamic library libcudnn.so.7
1563/1563 [==============================] - 19s 12ms/step - loss: 1.8952 - accuracy: 0.3029 - val_loss: 1.5868 - val_accuracy: 0.4233
Epoch 2/100
1563/1563 [==============================] - 17s 11ms/step - loss: 1.6196 - accuracy: 0.4084 - val_loss: 1.4305 - val_accuracy: 0.4763
Epoch 3/100
1563/1563 [==============================] - 17s 11ms/step - loss: 1.4915 - accuracy: 0.4593 - val_loss: 1.3402 - val_accuracy: 0.5222

Python3でエラー発生時にデバッガを起動する

Python3のスクリプトを数時間動かしたあとにエラーで落ちるという経験はないでしょうか。エラーが発生したら pdb と呼ばれるデバッガが起動するようにしておくと、エラーの究明に役立ちます。

例えば、以下のような script.py があったとします。

def main():
    a = 10
    b = 0
    print(a / b)


main()

このスクリプト$ python3 script.py と普通に実行すると、以下のようにゼロ除算エラーが発生し、異常終了してしまいます。

$ python script.py
Traceback (most recent call last):
  File "script.py", line 7, in <module>
    main()
  File "script.py", line 4, in main
    print(a / b)
ZeroDivisionError: integer division or modulo by zero

ここで、

$ python3 -m pdb -c continue script.py

というふうに、-m pdb -c continue をつけてスクリプトを実行すると、以下のように、エラーが発生した地点でデバッガが起動します。

$ python3 -m pdb -c continue script.py
Traceback (most recent call last):
  File "/usr/lib/python3.6/pdb.py", line 1667, in main
    pdb._runscript(mainpyfile)
  File "/usr/lib/python3.6/pdb.py", line 1548, in _runscript
    self.run(statement)
  File "/usr/lib/python3.6/bdb.py", line 434, in run
    exec(cmd, globals, locals)
  File "<string>", line 1, in <module>
  File "/home/user/script.py", line 1, in <module>
    def main():
  File "/home/user/script.py", line 4, in main
    print(a / b)
ZeroDivisionError: division by zero
Uncaught exception. Entering post mortem debugging
Running 'cont' or 'step' will restart the program
> /home/user/script.py(4)main()
-> print(a / b)
(Pdb) 

あとは、pdbを使って自由に原因究明できます。

(Pdb) print(a)
10
(Pdb) print(b)
0

LinuxでGPUの情報を取得する

LinuxGPUの情報を取得する方法を調べました。以下の表示例およびコマンド例は、すべてUbuntu 18.04 + GTX 1070という環境で試しました。OSによって差異があるかもしれません。

1. lspciを使う

lspciは、PCIバイスのリストを表示するコマンドです。以下のように表示されました。

$ lspci | grep -i VGA
01:00.0 VGA compatible controller: NVIDIA Corporation GP104 [GeForce GTX 1070] (rev a1)

lspciが入っていない場合は、

$ sudo apt install pciutils

としてください。

2. glxinfoを使う

glxinfoは、OpenGLなどに関する情報を表示するコマンドです。

$ glxinfo

としたときの表示の一部を以下に示します。

...(略)...
OpenGL renderer string: GeForce GTX 1070/PCIe/SSE2
OpenGL core profile version string: 4.6.0 NVIDIA 440.33.01
OpenGL core profile shading language version string: 4.60 NVIDIA
...(略)...

glxinfoが入っていない場合は、

$ sudo apt install mesa-utils

としてください。

3. lshwを使う

lshwは、ハードウェアのリストを表示するコマンドです。オプション-C displayを追加すると表示する情報をdisplay関係だけに限定できます。sudoをつけずに実行すると「出力が不完全または不正確な可能性がある」と警告が出ますが、私の場合はつけてもつけなくても同じでした。

$ sudo lshw -C display
  *-display                 
       詳細: VGA compatible controller
       製品: GP104 [GeForce GTX 1070]
       ベンダー: NVIDIA Corporation
       物理ID: 0
       バス情報: pci@0000:01:00.0
       バージョン: a1
       幅: 64 bits
       クロック: 33MHz
       性能: pm msi pciexpress vga_controller bus_master cap_list rom
       設定: driver=nvidia latency=0
       リソース: irq:138 メモリー:f6000000-f6ffffff メモリー:e0000000-efffffff メモリー:f0000000-f1ffffff IOポート:e000(サイズ=128) メモリー:c0000-dffff

lshwが入っていない場合は、

$ sudo apt install lshw

としてください。

4. nvidia-smiを使う

NVIDIA社のGPUを使っている場合はnvidia-smiが定番です。

$ nvidia-smi
Thu Feb 27 21:41:45 2020       
+-----------------------------------------------------------------------------+
| NVIDIA-SMI 440.33.01    Driver Version: 440.33.01    CUDA Version: 10.2     |
|-------------------------------+----------------------+----------------------+
| GPU  Name        Persistence-M| Bus-Id        Disp.A | Volatile Uncorr. ECC |
| Fan  Temp  Perf  Pwr:Usage/Cap|         Memory-Usage | GPU-Util  Compute M. |
|===============================+======================+======================|
|   0  GeForce GTX 1070    On   | 00000000:01:00.0  On |                  N/A |
|  0%   36C    P8     8W / 151W |    628MiB /  8116MiB |      0%      Default |
+-------------------------------+----------------------+----------------------+
                                                                               
+-----------------------------------------------------------------------------+
| Processes:                                                       GPU Memory |
|  GPU       PID   Type   Process name                             Usage      |
|=============================================================================|
...(略)...
+-----------------------------------------------------------------------------+

参考URL

Docker ImageからContainerを作るコマンドのまとめ

いまさらながらDockerの使い方を勉強中です。この記事では、Dockerを使うための環境構築方法と、誰かが作成したDocker ImageをもとにDocker Containerを作成して動かす方法についてまとめます。

環境構築

以下ではUbuntu 18.04にDocker Community Editionをインストールする場合について説明します。

Docker Community Editionのインストール

現時点でのインストールの流れは以下のとおりです。

  • "Uninstall old versions"の節に従い、既にインストール済のdockerを(もしあれば)削除
  • "SET UP THE REPOSITORY"の節に従い、aptを使ってDocker CEのstableをインストール

動作確認

現時点で以下のバージョンが入りました。

$ docker --version
Docker version 19.03.5, build 633a0ea838

正しくDockerをインストールできていれば、sudo docker run hello-world によりHello from Docker!というメッセージが表示されます。

また、sudo docker image lsで、ローカルに取得されたイメージが表示されるはずです。

REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
hello-world         latest              fce289e99eb9        13 months ago       1.84kB

非rootでもdockerを使えるようにする

インストールしただけだとrootしかdockerを使えません。非rootユーザでもdockerを使えるようにするには、 * Post-installation steps for Linux | Docker Documentation の "Manage Docker as a non-root user" に従います。

成功すれば、docker run hello-worldでメッセージが表示されるようになります。以降の説明ではこの設定を行ったものとします。

使い方

Dockerのバージョンを調べる

docker -vで簡易版のバージョン情報を、docker versionで詳細版のバージョン情報を表示できます。以下は私の環境での例です。

$ docker -v                            
Docker version 19.03.5, build 633a0ea838
$ docker version
Client: Docker Engine - Community
 Version:           19.03.5
 API version:       1.40
 Go version:        go1.12.12
 Git commit:        633a0ea838
 Built:             Wed Nov 13 07:29:52 2019
 OS/Arch:           linux/amd64
 Experimental:      false

Server: Docker Engine - Community
 Engine:
  Version:          19.03.5
  API version:      1.40 (minimum version 1.12)
  Go version:       go1.12.12
  Git commit:       633a0ea838
  Built:            Wed Nov 13 07:28:22 2019
  OS/Arch:          linux/amd64
  Experimental:     false
 containerd:
  Version:          1.2.10
  GitCommit:        b34a5c8af56e510852c35414db4c1f4fa6172339
 runc:
  Version:          1.0.0-rc8+dev
  GitCommit:        3e425f80a8c931f88e6d94a8c831b9d5aa481657
 docker-init:
  Version:          0.18.0
  GitCommit:        fec3683

Docker Imageの取得

まず、誰かが作成したDocker Imageを取得するところから始めます。Docker Imageには"Base Image"と"Child Image"の2種類があります。

Base Imageは親を持たないImageで、例えばubuntu, debian, busyboxなどのOSが代表的です。 Docker Hub にて大量のBase Imageが提供されています。 以下では、Docker Hubから、Base Imageの一つであるubuntuを取得して使ってみます。

$ docker pull ubuntu

とすると、Docker Hubにあるubuntulatestタグがついたimageが取得できます。

タグを明に指定することで特定のバージョンを取得することも可能です。例えば

$ docker pull ubuntu:20.04

とすると、現時点では開発版であるバージョン20.04のUbuntuが取得できます。

これまでに取得したimageの一覧はdocker image lsまたはdocker imagesで確認できます。

$ docker image ls
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
ubuntu              latest              ccc6e87d482b        3 weeks ago         64.2MB

Docker ImageからDocker Containerを作る

取得したDocker ImageからDocker Containerを作るにはdocker runコマンドを使います。

$ docker run ubuntu

上記コマンドを実行すると一見何も実行されないように見えますが、実際には以下が順番に行われます。

  • ubuntuという名前のDocker Imageがローカルにあるかを探す。もしなければDocker HubからDocker Imageを取得
  • ubuntuというDocker Imageから、Docker Containerを作成
  • Containerの中でコマンドを実行

さきほどの例ではコマンドを与えなかったので、ただコンテナが作成されただけでした。次の例では、コマンドls -alFを与えてみます。コンテナの中にあるルートディレクトリ以下のファイル一覧が表示できます。

$ docker run ubuntu ls -alF
total 72
drwxr-xr-x   1 root root 4096 Feb 11 08:51 ./
drwxr-xr-x   1 root root 4096 Feb 11 08:51 ../
-rwxr-xr-x   1 root root    0 Feb 11 08:51 .dockerenv*
drwxr-xr-x   2 root root 4096 Jan 12 21:10 bin/
drwxr-xr-x   2 root root 4096 Apr 24  2018 boot/
drwxr-xr-x   5 root root  340 Feb 11 08:51 dev/
drwxr-xr-x   1 root root 4096 Feb 11 08:51 etc/
drwxr-xr-x   2 root root 4096 Apr 24  2018 home/
drwxr-xr-x   8 root root 4096 May 23  2017 lib/
drwxr-xr-x   2 root root 4096 Jan 12 21:10 lib64/
drwxr-xr-x   2 root root 4096 Jan 12 21:09 media/
drwxr-xr-x   2 root root 4096 Jan 12 21:09 mnt/
drwxr-xr-x   2 root root 4096 Jan 12 21:09 opt/
dr-xr-xr-x 367 root root    0 Feb 11 08:51 proc/
drwx------   2 root root 4096 Jan 12 21:10 root/
drwxr-xr-x   1 root root 4096 Jan 16 01:20 run/
drwxr-xr-x   1 root root 4096 Jan 16 01:20 sbin/
drwxr-xr-x   2 root root 4096 Jan 12 21:09 srv/
dr-xr-xr-x  13 root root    0 Feb 11 08:51 sys/
drwxrwxrwt   2 root root 4096 Jan 12 21:10 tmp/
drwxr-xr-x   1 root root 4096 Jan 12 21:09 usr/
drwxr-xr-x   1 root root 4096 Jan 12 21:10 var/

コンテナの中に入ってインタラクティブに操作を行うには、-itを使います。exitで終了です。

$ docker run -it ubuntu bash

ここで作られるコンテナは使い捨てです。試しに、上記でコンテナの中に入って適当にファイルを作成してコンテナを終了すると、次にコンテナを作成したときにはそのファイルは存在しないことが分かります。

ここまでの作業で、コンテナを使ったあとの残りカスが出ています。docker psしても何も表示されませんが、

$ docker ps -a

とすると、例えば以下のように、停止状態のコンテナが一覧になって表示されます。

$ docker ps -a
CONTAINER ID        IMAGE               COMMAND             CREATED             STATUS                      PORTS               NAMES
45f580404989        ubuntu              "bash"              16 minutes ago      Exited (0) 14 minutes ago                       clever_rhodes
8231b2e245c4        ubuntu              "bash"              18 minutes ago      Exited (0) 18 minutes ago                       sharp_moore
1aa25f7fc213        ubuntu              "ls -alF"           20 minutes ago      Exited (0) 20 minutes ago                       awesome_proskuriakova

停止状態のコンテナを完全に削除するには、

$ docker rm (コンテナID)

とします。

停止状態のコンテナをまとめて一斉に削除するには

$ docker container prune

とします。

コンテナを使い終わるたびに削除をするのは面倒です。コンテナを使い終わったあとに自動で削除されるようにするには、runコマンドに--rmをつけて実行します。

$ docker run --rm -it ubuntu bash

例:GitLabを使う

"Child Image"の利用例として、GitLabをローカルマシンで動かすことを試してみます。

GitLab Docker images | GitLab にある手順書を従ってGitLabをインストールすることもできます。 しかし、これから紹介するDockerを使った方法であれば、もっと簡単にGitLabを動かせます。

GitLab Docker images | GitLab にあるコマンドを少し変えて、以下のコマンドを実行します。

$ docker run --detach \
  --publish 10443:443 --publish 10080:80 --publish 10022:22 \
  --name gitlab \
  --restart always \
  --volume /srv/gitlab/config:/etc/gitlab \
  --volume /srv/gitlab/logs:/var/log/gitlab \
  --volume /srv/gitlab/data:/var/opt/gitlab \
  gitlab/gitlab-ce:latest

--detachはコンテナをバックグラウンドで動かすという意味です。少し待った後、ブラウザでlocalhost:10080にアクセスすると、GitLabが立ち上がっていることがわかります。他の引数の意味は以下の通りです。

  • --name: コンテナに付ける名前の指定
  • --publish: コンテナのポートとホストのポートとの対応付けの指定。10443:443は、コンテナのポート443をホストのポート10443に対応付けるという意味
  • --restart always: システムをリブートしたあと、このコンテナを自動でrestartする
  • --volume: GitLabのデータの保存先の指定。この例の場合、すべてのGitLabデータは/srv/gitlab/以下に保存される

コンテナを停止状態にするにはdocker stop gitlabとします。GitLabで遊び終わったら、/srv/gitlab/にGitLabが保存したデータ一式を消しておきましょう。

参考URL

Ubuntu 18.04でsleepする方法

Ubuntu 18.04でsleepする方法は以下のとおりです。なお、正しくは"sleep"ではなく"suspend”というそうです。

  • Winキーを押す
  • "sleep" または "suspend" とキーボードに打ち込む
  • 途中で「サスペンド」というアイコンが出てくるので、選択する

Santa's Workshop Tour 2019 参加記

10日前まで開催されていたKaggleのSanta's Workshop Tour 2019に参加していました。結果は1620チーム中の142位。Kaggleで初めてのメダルであるブロンズメダルを獲得できました。最適化系のコンテストなのに問題のサイズが小さく、コンテストの序盤から最適解にたどり着く人が徐々に増えていく展開。しかも最適解にたどり着いた人は皆Gurobi や CPLEXなどの商用最適化ソルバを使っているらしいことがわかり、途中で戦意喪失しました。

問題概要

5000個のファミリーをday1からday100までのいずれかに割り振り、あるコストを最小化する最適化問題です。

各ファミリーには以下の情報が与えられます。

  • 家族を構成する人数: 2人から8人。4人が一番多い
  • 希望日: 各家族はchoice_0からchoice_9までの希望日を持っている。

コストは以下の2つの和として計算されます。

  • preference cost
    • 家族の割りあて方に対してつくコスト。各家族は、choice_0に割り当てるとコストが小さく、choice_9に割り当てるとコストが大きい。choice_0からchoice_9以外の日に割り当てるとさらに大きなコストとなる。
  • accounting penalty
    • 各日に割り当てられた人数の連続性に対してつくコスト。ある日に割り当てられた人数と、その次の日に割り当てられた人数とのずれが大きいほど大きなコストとなる。
    • accounting penaltyは具体的には下式で与えられる。ちょうど125人のときにpenaltyが0になることに注意。

f:id:minus9d:20200127211351p:plain

やったこと

基本的には、以下の繰り返しでした。

  • 強いNotebookが発表されて自分の順位がガタ落ちする
  • 強いNotebookの出力を初期値として、自分の実装した最適化手法を適用し、すこし良い値を出す

最終スコアである69410.61には以下のようにして到達しました。

  • Manual to improve submissions | Kaggle で提案された、特定の日を強制的に125人にするノートブックを流用。day37, day44, day51, ...を強制的に125人とした
  • それにより得られた解はいったんスコアがとても悪くなるが、以下の最適化を繰り返すと、最終的に69410.61に到達した
    • 2家族をランダムに選び、割り当て日をスワップ
      • スコアが悪化する場合でも、少しの悪化であれば確率的に受け入れる
    • N家族をランダムに選び、そのN家族について割当を総当りし、もっともよいスコアのものを選ぶ
      • もしある家族が今choice_Kを選んでいるとしたら、choice_0からchoice_Kまでを総当り
      • Nを大きくするほどあたりを引く可能性が大きくなるが、計算時間も大きくなる

焼きなましで最適解に近づけないかと試行錯誤しましたが、うまくいきませんでした。最適解の割当結果を見るとちょうど125人である日がもう一日多かったのですが、そのような分布を焼きなましで作ることは相当難しいようでした。