クラウドエンジニアのノート

情報技術系全般，自分用メモを公開してます。

PFN2020インターンの課題 解答

Python OSS Github 就活

PFN2020インターンに応募した話

M1になり，そろそろ夏インターンを探さなきゃってことで，色々応募しました．

強化学習のインターンをやりたかったのですが，勉強不足を面接であっさり見抜かれてしまい，落ちてしまいました．

これを糧に，これから強化学習の勉強をしっかりしようと強く思いました．

現在はberkeleyの強化学習スライドをベースに，基礎的な部分の勉強をしています．いずれはそれをまとめた記事を公開しようと思ってます．

PFN2020課題

Github上で2020の課題が公開されたので大丈夫だとは思いますが，もし何か差し支えるようでしたら，ご連絡頂けますと幸いです．

こちらのリポジトリに解答例を載せましたので，ソースはこちらをご覧ください． github.com

また，問題文はこちらです github.com

PFNの課題というと，深層学習のイメージがありましたが，今回はかなり競プロっぽい内容でした． 最近はそういう流れなんですかね．

また，大問が3つあって，それぞれコーディング課題と，その正しさを検証する課題の2つセットで解答する必要があります．

もし数式が正しく表示されていなければ，ブラウザをリロードしてみてください．

Q1

3つの整数 x, y, d が与えられる。 3x3 行列の各要素を x または y で埋めるとき、行列式がちょうど d になるような 埋め方は何通りあるか数えよ。

問題の解法説明

まず最初に思いつくアプローチは全探索である．

しかし，3x3行列というのは各列を3次元ベクトルと見ると，平行六面体を表しており，行列式の値はその体積に相当する．つまり同じ向きのベクトルが存在すると体積は0になる．この性質を利用して計算量を減らした．

$d \neq 0$ の場合

  • 3次元ベクトルそれぞれが取ることができるx, yの組み合わせは$2^{3}=8$通り
  • そこから重複なく3つ選ぶ数は ${}_8 C_3 = 56$ 通り
  • また，ベクトルをそれぞれ入れ替えて行列式の符号が同じになるような組み合わせは3通り

つまり56通り検索し，見つかった数×3すれば良い．

$d == 0$の場合

  • 同じく56通り調べる（転置してベクトルが0になる場合）
  • 重複する選び方の数(=全通り - 重複しない数)を計算

行列式が0なので，見つかった数×6に重複する選び方の数を足せば良い．

プログラムの正しさの検証

q1_in.txt を総当りのプログラムとの出力の比較を行った．

境界条件としてdが正・負・0, x, yが同符号・異符号・0の場合のすべての組み合わせ(12通り)について検証を行った．

また，おまけとして，全通りでも制約すべての条件下で現実的な時間内に終わりそうだったため，q1_validation_extra.pyにてすべての場合の検証を行った．

進捗を見やすくするため，tqdmという外部ライブラリを使用した．（並列化してますが，それでも手元の6コアCPUで30分程度かかりました）

Q2

文字列 S1, S2, ... を以下で定める。

  • S1 = "a"
  • S2 = "b"
  • S3 = "c"

Sk = Sk-3 + Sk-2 + Sk-1 (k ≥ 4) (ここで、+ は文字列の結合を表す) 例えば、S4 = "abc", S5 = "bcabc" である。 3つの整数 k, p, q が与えられる。 Sk の p 文字目から q 文字目までに含まれる文字 "a", "b", "c" の個数をそれぞれ求 めよ。

問題の解法説明

まず最初に思いつくアプローチとしてDPがある．しかし試してみたところ，メモリが$k > 40$をこえたあたりで足りなくなった．

そこで，この漸化式の行列表現を考える．

Svec_{k} = \begin{pmatrix}a_k&b_k&c_k&sum_k \end{pmatrix}

とすると以下のように表現できる．

このとき，$a_k$とは，文字列$S_k$に含まれるaの個数である．

\begin{pmatrix}Svec_k\cr Svec_{k-1}\cr Svec_{k-2}\end{pmatrix}=A^{k-3}\begin{pmatrix}0&0&1&1\cr 0&1&0&1\cr 1&0&0&1\end{pmatrix}, (k>3)


このAを毎回累乗して求めても良いが，高速化のためにこのAを対角化してn乗を求めておく． すると$O(1)$で，文字列$S_k$に含まれるa, b, c の個数がわかる．

また，この行列は固有値に虚数を含むため誤差が生じる．しかし，$A^{50}$のときの誤差が $ [0.0144 +0.0016j, 0.0124+0.0014j, 0.0072+0.0013j] $ であるため，問題ないと言える．

（当時は2乗法を知らずn次行列を求めてますが，あまり美しい方法じゃないので，2乗法を使ったほうが良いと思います‥）

qiita.com

つぎに$[p, q]$だが，もし，$[p, q]$の範囲が，ある S_l, (l \leq k) の文字数と同じ場合，先程の行列の結果をそのまま返せば良い． つまり，そのような$S_l$を探せば良い．

$S_k$は S _ {k-3}+S _ {k-2}+S _ {k-1} の3つの文字列から構成されている． つまり，$[p, q]$は$S_k$の各構成要素を跨ぐ場合と，そうでない場合に分けることができる．

以上の性質を用いると以下のようなアルゴリズムを考えることができる．

区間が跨いでいる場合

  • それぞれを区間を跨がないように分割し，最後にそれぞれの結果を足す

区間が跨いでいない場合

  • $[p, q] = S_{l}$ ならば，行列計算の結果を返す
  • $[p, q] \neq S_l$ ならば，対応する部分の$S_m, (m < l)$を調べる

以上の手順を再帰的に繰り返すことによって調べることができる．

プログラムの正しさの検証

プログラムの境界条件と，それぞれが1回以上の文字連結で構成されている$k=7$でのすべてのケースについて検証を行った．
また，DPで解くプログラムの限界が$k<40$であるので，その条件に満たすq2_in.txt でも同様に出力の検証を行った．

Q3

長いので省略

問題の解法説明

まず考えられるアプローチとして，各距離をすべて保持する方法が考えられる．

単純に，ある$j$番目人を最も距離が大きいかつ一番左の$a_j$に座らせて，$a_j$から両端まで距離を更新して行けば良い．

しかし，この手法は$O(n^{2})$であり，制約の$n$が大きいため時間がかかる．そのため高速化を考える．

ある$j$番目の人が$a_j$に座ったとき，そこから$l$方向($0 < l < j$)と， $r$方向の区間($j < r \leq n$)のまだ誰も座っていない区間に分割する．

それぞれ分割された区間の中で，区間の左右から最も離れた位置が最も大きい場所に座れば良い．
つまり，分割された区間が$l$から$r$とすると($l$は0から)，その区間内で離れることができる最大の距離$dist$は$(l - r) // 2$であり， 座る位置のindexは$l + dist$として表現できる．また，$dist$が最も大きいものから（同じからlが小さい方）から選んでいけば良い．

この手順を再帰的に繰り返し適用していけば，すべての座る位置が求まる．
しかし，最初の分割だけ例外があり，端に誰も座っていないため2で割る必要がない．よって$dist = l - r$とした．

実装上の工夫として，$dist$の最も大きい値を効率的に探すためにheapqを用いた．

プログラムの正しさの検証

プログラムの境界条件（最初に端に座る，n=1など）の検証を行った．
また，$O(n^{2})$の方法が現実的な時間で終わるのが$k < 10000$なので，その条件を満たすq3_in.txt についても同様の検証を行った．

Top-K Off-Policy Correction for a REINFORCE Recommender System

DLゼミ 論文紹介 強化学習

スライド

説明

Top-K Off-Policy Correction for a REINFORCE Recommender System – Google Research

YouTubeで実際に運用された（今も運用されてるかは不明）強化学習を用いた推薦システムの論文です．

内容として，RENFORCEをoff-policyかつ複数の行動を出力するように変更したみたいです．しかし，この推薦システムが性能良いのか悪いのかについて議論されていないので，そこが気になりますね．

でも，この数百万オーダの空間へスケールアップと，バイアス・バリアンスへの対処は，強化学習の非常によい勉強になりました．

スライド中でも軽く方策勾配法について解説しているので，良かったら見てください．

参考にしたサイト

medium.com

qiita.com

有志実装

実装主のブログ
https://towardsdatascience.com/top-k-off-policy-correction-for-a-reinforce-recommender-system-e34381dceef8

Github github.com

Azure Web App + Flask + Github Actionsで認証ページ付きポートフォリオをデプロイする方法

Github Web Python

はじめに

以前Firebaseでデプロイしたときをベースに書いてますので、先にこちらを見て下さい。 tmyoda.hatenablog.com

Azure クラウド サービス | Microsoft Azure にはとんでもない数のサービスがありますが 、 今回はポートフォリオを公開するために、WebのApp Serviceを使用しました。分類的にはPaaSですかね。

そしてなにより、1Gメモリ F1を選択すると無料で使えます。 また、学生でしたら、登録したときに1万円分のサブスククーポンを貰えます。

概要

  • AzureでWebページをデプロイ
  • AzureではBasic認証が使えないので、ログインページを用意(Flask)
  • 以前Firebaseでデプロイしたhtml,css,jsを使いまわしたいのでサブモジュールにて保持

参考にさせて頂いた記事

  • Azureの登録方法等 qiita.com

  • Flaskでログイン機能の実装 qiita.com

  • Bootstrap Login form

www.tutorialrepublic.com

Azure登録まで

参考記事に従ってAzureを登録します。 このとき、Flaskを使いたいのでランタイムスタックをPython3にします。

しばらくするとインスタンスが作成されます。

Flaskで認証ページを実装

Firebase Hostingでデプロイしたときは、Basic認証が使えたので、実質静的ページの公開と同じでした。

しかし、AzureはBasic認証が使えないようなので、Flaskでかんたんなログインを実装しようと考えました。 参考記事に従いながら実装していると‥

なんと、Flaskでhtmlを表示するにはjinja2のテンプレートに対応した記述が必要です。

しかし、サブモジュールでhtmlを保持しているため、書き換え等はしたくない、、、

かといってFlaskのstaticフォルダに格納したら直接が見られるが認証がかけられない、、、

そこで、

  • @app.route('/portfolio/')にGETが来たら、直接htmlをテキストとして読み出しResponse型で返す
  • その他のcss,jsへのアクセスが来たら、send_fileする

といった方針でひとまずやりたいことは実現しました。

解決策

from flask import Flask, request, Response, abort, render_template, redirect, url_for, send_file
from flask_login import LoginManager, login_user, logout_user, login_required, UserMixin
from collections import defaultdict
import os
import logging

app = Flask(__name__)
login_manager = LoginManager()
login_manager.init_app(app)
app.config['SECRET_KEY'] = なんらかしらのキーを設定

# logging setting
logging.basicConfig(level=logging.DEBUG)
#logging ex
# app.logger.info("Hello World %s", variable) 


# path setting
currnet_dir = os.path.dirname( os.path.abspath(__file__) )
static_dir = 'portfolio/functions/static/'


class User(UserMixin):
    def __init__(self, id, name, password):
        self.id = id
        self.name = name
        self.password = password

# ログイン用ユーザー作成
users = {
    1: User(1, "user01", "password"),
    2: User(2, "user02", "password")
}

# ユーザーチェックに使用する辞書作成
nested_dict = lambda: defaultdict(nested_dict)
user_check = nested_dict()
for i in users.values():
    user_check[i.name]["password"] = i.password
    user_check[i.name]["id"] = i.id

@login_manager.user_loader
def load_user(user_id):
    return users.get(int(user_id))


# css, js ,imgなどのコンポーネント呼び出し用
@app.route('/portfolio/<path:path>/<string:filename>', methods=["GET"])
@login_required
def portfolio_content(path, filename):
    return send_file(static_dir + path + "/" + filename)    

# index.html呼び出し 
# .htmlはこの方法じゃないとだめみたい
@app.route('/portfolio/')
@login_required
def portfolio():
    with open(currnet_dir + '/' + static_dir + 'index.html') as f:
        txt = f.read()
        return Response(txt)


# ログインパス
@app.route('/', methods=["GET", "POST"])
def login():
    if(request.method == "POST"):
        # ユーザーチェック
        if(request.form["username"] in user_check and request.form["password"] == user_check[request.form["username"]]["password"]):
            # ユーザーが存在した場合はログイン
            login_user(users.get(user_check[request.form["username"]]["id"]))
            return redirect(url_for('portfolio'))
        else:
            return abort(401)
    else:
        return render_template("login.html")

# ログアウトパス
@app.route('/logout/')
@login_required
def logout():
    logout_user()
    return Response('''
    logout success!<br />
    <a href="/login/">login</a>
    ''')

if __name__ == '__main__':
    app.run(threaded=True)

pass,idベタ書きしてますが、本当はDBに格納してパスワードもハッシュ化しないといけませんね。 まあ最悪全世界に晒されても良い内容なので、今回はこの程度で良いでしょう。

/portfolio に来るアクセスはindex.htmlを返して、 /portfolio/img/, css/ とかはsend_fileで返却します。

フォルダ階層

.
├── Pipfile
├── Pipfile.lock
├── app.py
├── portfolio
│   └── functions
│       └── static
│           ├── css
│           ├── img
│           ├── index.html
│           ├── js
│           └── vendor
├── requirements.txt
└── templates
    └── login.html

この工夫点として、portfolioフォルダは別リポジトリのサブモジュールです。 なので、どっちかでポートフォリオをアップデートしたら、もう片方がアップデートされます。

また、 staticフォルダを作成していない点もポイントです。(staticは外から見える)

そして、Pythonは、*.py、requirements.txt、または runtime.txtが最初に呼び出されるらしいので、 名前をちゃんと変えておきましょう。

デプロイ

ここまできたらいよいよです。今回はGithub Actionsでのデプロイが目標ですので、Azure portalのデプロイメントから、 Githubを選択して、Actionsを選択します。（要認証）

すると勝手にworkflowが作成されるので、次々と進むと勝手にCI/CDが走ってデプロイ完了です。 非常にかんたんですね！

注意点として、再起動しないと認識されないので注意です。

サブモジュール関連のトラブル

サブモジュール使ってない人はパスして下さい。

サブモジュールがpullされておらず、htmlがNot Foundになりました。 その解決方法として、追記したworkflow/ymlを晒します。

    steps:
    - uses: actions/checkout@master
      with:
        submodules: true
        token: ${{ secrets.PORTFOLIO_ACCESS_TOKEN }}
    
    - name: Sparse-Checkout
      run: |
        echo /functions/static >> .git/modules/portfolio/info/sparse-checkout
        cd portfolio
        git config core.sparsecheckout true
        git read-tree -mu HEAD
        git checkout master
        cd ..

まず、プライベートリポジトリでしたので、アクセストークンを取得して設定する必要があります。 以下を参考に作成して、サクッと設定しましょう。見ての通り、token: ${{ secrets.PORTFOLIO_ACCESS_TOKEN }}で埋め込めます。

help.github.com

また、私の場合はhtmlに関係するファイルのみ欲しかったので、sparse-checkoutしています。 一括でうまくやってくれるworkflowファイルを見つけられなかったので、runでベタ書きしました。

とりあえず、これで上手く動いてくれているので良かったです。 （すぐデプロイするつもりがなんだかんだ一日かかっちゃいました‥）

注意点

  • 再起動しないとデプロイが反映されない
  • privateリポジトリをサブモジュールで持つなら、Access Tokenが必要
  • FlaskはStatic以下は常に晒されている
  • Secretkey pass, idなどはちゃんとDB管理

追記

Azureは適当にhtmlファイル置くだけでも表示されるらしいので、なんかのWebサーバが裏で動いているんですかね、わかりません。

そしてなんと、Azure Static Web Appというより気軽なサービスが最近追加されたらしいです‥ こっち使ったほうが早かったですね

Learning agile and dynamic motor skills for legged robots 解説スライド

強化学習 機械学習 論文紹介 DLゼミ

スライド

説明

  • 複雑なモータ制御が必要なロボットの制御方法を提案
  • シミュレーションのみで学習した方策をロボットに転送し、実 環境のロボット制御に成功
  • ロボットのシミュレーションとの違いをNNによって吸収
  • これによりシミュレータでのモデリングが改善
  • 方策はシミュレーション上のみで学習
  • 既存のSOTAのモデルベース手法より優れた性能
  • より、少ないエネルギー、計算量ながら、より高速で高い精度
  • 本論文は多脚ロボットの汎用的なコントローラの獲得への一歩

感想

actuator netの精度を向上させたら、ゴリゴリのコスト関数設計はもう少し楽になるのでしょうか‥

恐らくノイズを載せまくってるのがコスト関数を複雑化させている原因になっているので、もう少しシミュレーションが 現実に近いと楽なんですかね
また、TRPOじゃなくてPPOとかSACとかだと学習に違いが出るか気になります

論文のpdfをコピペしたときのいらない改行を削除する

Python OSS

追記 (2020/12/07)

Webで動く便利なサイト見つけました

https://dream-exp.net/shaper/

はじめに

論文を翻訳にかけるとき、単純にCtrl+Cすると余計な改行がはいって非常に煩わしいですよね
そこで、クリップボードを監視して、改行を取り除く簡単なPythonスクリプトを作成しました

導入方法

Githubにて公開しました github.com

こちらをcloneしてpyperclipをインストールすればすぐに使えます
webページとかを介さなくて良いので安心ですね(？)

注意点

  • ソース内 pause パラメータをいじることができますが、あまり短くしすぎると無限ループに陥ります
  • ほんとはDeepL翻訳のショートカットであるCtrl+C 2回と組み合わせて使えたら最高だなと思ったのですが、難しかったです‥（PRお待ちしております)
  • とりあえずで作って見た次第なので、改善案等お待ちしておりますー

MuZero

DLゼミ 強化学習 機械学習 論文紹介

スライド

説明

囲碁・将棋などのドメインはモデルベースな強化学習手法が成功を収めてきたが、そのモデルを自動で獲得し、AlphaZeroなどの従来手法を上回ったと主張しています。 つまり、モデルベースな手法ながら、人間はモデルの定義をする必要がないのです。環境と戦略を同時に学習します。
さらに囲碁・将棋のようなドメインだけでのみ強かったモデルベースな手法ですが、環境のモデルを自動的に獲得できるので、Atariでも従来手法を凌駕する成績を収めました。

EMERGENT TOOL USE FROM MULTI-AGENT AUTOCURRICULA（OpenAIかくれんぼ）

DLゼミ 強化学習 機械学習 論文紹介

スライド

説明

調和系DLゼミ、札幌AI勉強会で発表させて頂いたスライドです。

内容は、チーム戦のかくれんぼを通じて，相互の戦略を獲得できたとする研究です。
各チームごとにシンプルな報酬のみにもかかわらず，人間に関連するスキルを中心とする行動を獲得できたと主張しています。
強化学習手法にはPPO + LSTMが用いられているみたいですね。また、方策を蒸留させようとする工夫が数多く見られました。

やはり強化学習はそのまま適用しただけじゃ上手く行かないことの方が多く、まだまだドメインによって様々な工夫が必要なんでしょうか‥。

DQNからA3C, PPOまで

DLゼミ 論文紹介 機械学習 強化学習

スライド

説明

DQNからA3C, PPOまでの変遷を順に説明したスライドです。札幌AI勉強会で発表させて頂いた資料になります。 強化学習は基本的にDQNからの派生がほとんどなので、いきなり新しい手法の論文を見てもわけがわかりませんでした。
また、近年では全く新しいアプローチの強化学習が成功を収めています。(MuZero)

そちらの解説記事もあるので、よかったら見てってください。

A3C

強化学習 機械学習 論文紹介

スライド

説明

エピソードのサンプリング・学習が非同期 + Actor-Criticな手法の提案。更にGPUではなくCPUのみでDQNより学習時間を削ることに成功。また、DQNが苦手な行動空間が連続な場合の可能性も示した。 しかし、現在ではA2C（同期）の方が性能が良いとされている。

追記

現在（2020/04)ではAtariドメインでMuZeroやAtari57がSOTAなので、そちらのほうが良い手法と言えるだろう。近々そのあたりの論文を読んでみたい。

Android Studio 3.6でAndroid Drawable Importerを使う方法

Android

お急の方

一番下にダウンロードリンクがあります

はじめに

皆さんはandroid開発のとき、アプリ内で使用する画像のimportをどうしてますか？ 理解のあるデザイナーならすべてのサイズでdrawableをくれるでしょうが、私の場合そうはいきませんでした。
今回はそんなdrawableへのimportを一発でできるdrawable importerの導入方法について説明します。

Pluginについて詳しくは以下の記事へどうぞ qiita.com

導入方法

本来なら Preferences->Plugins でAndroid Drawable Importerを検索して導入で終わりですが、検索結果はNot Foundです

なので以下リンクの公式からDownloadして Preferences->Plugins 歯車マーク Install plugin from Diskでzipファイル指定でインストールできますが、3.6ではimportしても何もおきません。

https://plugins.jetbrains.com/plugin/7658-android-drawable-importer

解決方法

issueを漁っていると、Folkして3.6に対応してくれている人がいました。ありがとう！
皆さんもハートマーク押しときましょう

github.com

急ぎの人はここからzipダウンロードできます