ARC 077 D: 11

競技プログラミング/AtCoder 競技プログラミング 競技プログラミング/テクニック/mod

arc077.contest.atcoder.jp

解き方

  • 重複を考えずに組み合わせを計算し，重複分を引く
    • 条件より重複は必ず1個存在する
  • 組み合わせの計算は，n!を事前に計算しておく事でO(1)で行う
    • n!^{-1}もmodを取る場合は前計算できる

ハマった所

  • 組み合わせ計算の高速化方法
    • n!の前計算は，逆数の前計算の方法が分からなかったのでコンテスト中はできなかった
    • 割り算の場合にも普通にmodをとってしまっていた（深く考えてなかった）
  • 重複計算のところで無駄なループをしていた
    • 組み合わせ計算に関するループ（積和計算のような）は削れる可能性高そう？

DeepCoder追実装記録 (1)

chainer 機械学習 DeepCoder 実装

DeepCoder概略

[(Input, Output)] => Map[関数, 出現確率]の関数をディープラーニングで学習し，それを利用してプログラム空間を探索・プログラム合成をする． 詳しくは論文．

追実装について

レポジトリ: ここ

データセットの生成

深さ優先探索でプログラムを列挙しながら，適当に入出力の組を生成する．同じ挙動をするプログラムを排除する部分の処理が重く，時間がかかっている．

高速化の手段としては，

  1. 並列化（入力の型が違えば独立に扱えるので）
  2. 削除する部分が遅いようなので，その処理の見直し

あたりが思いついている．恐らく1は重要だと思う．

学習

恐らく過学習してしまっている．原因は不明だけど，データセットの生成の仕方が偏っている気がしないでもない． とりあえずデータセットの生成を高速化して，ちゃんとデータセット作ってもう一度やり直す．

ハマった点

  • チュートリアルのままでOptimizerをSGDにしたら局所解に陥ったのか収束しなかった．Adamだと収束する

今後

  1. 過学習の問題を解消する．せめて原因を特定する
  2. 小さめのデータセット(N=100くらい？)で評価をしてみたい

chainer 2.0勉強記録

機械学習 ライブラリ python chainer

チュートリアルを一通りやった上で，追加でハマったことのメモ

Datasetの作成方法

以下のように，DatasetMixinを使って作る．データの生成（ファイル読み込みなど）をget_exampleまで遅延させるのもOK

class Dataset(chainer.dataset.DatasetMixin):
    def __init__(self):
        xs = np.array(np.random.uniform(-math.pi, math.pi, (10000, 1)), dtype=np.float32)
        f = lambda t: np.array([math.sin(t)], dtype=np.float32)
        ys = np.array([f(e) for e in xs])
        self.input = xs
        self.output = ys
    def __len__(self):
        return len(self.output)
    def get_example(self, i):
        return self.input[i], self.output[i]

Trainerに与えるModelの実装方法

__call__の引数

第一引数が入力，第二引数が出力（actual）となり，loss関数を実装する．

__call__での引数の扱い

上記Datasetの場合，引数がただの変数なので，Variable(...)でラップする必要がある．

その他

計算途中を変数に置かないと上手く動かないケースがある（？ 未検証）

例えば，

h1 = l1(x)
h2 = l2(h1)
return h2

は上手く動くが，

return l2(l2(x))

は上手く動かないような気がする．

活動記録(2017/6/27-2017/7/2)

競技プログラミング

AOJ 0588

蟻本で練習問題に上げられていたので取り組んだ． 幅優先探索の実装練習．

ARC 077

結果: 425th, 1198->1268 (パフォーマンス: 1614)

Cは順調に解けた． Dは組み合わせを高速に計算する方法を思いつけなかった．あと10^9+7のmodをとる時の知識が足りない． Eはまだちゃんと見れてないけど，考察，実装両面でダメそう．

そろそろ爆死してレート下がりそう

実装

chainer

簡単な関数（sinとか）の学習はできた．意味の理解という点では基礎をちゃんと勉強しないとダメそう．

AOJ 0588: Cheese

競技プログラミング/AOJ アルゴリズム/幅優先探索 アルゴリズム/最短経路 競技プログラミング

チーズ | Aizu Online Judge

蟻本の練習問題に挙げられていたので練習

解き方

ハマった所

  • 最初，N=9を見逃して効率良い幅優先を考えていた
    • コンテストだったらただの幅優先以外の方法を考えてハマった気がする
    • とりあえず紙にまとめてから解き始める方が良いかも知れない

CHI2017勉強会 論文メモ

勉強会 学会/CHI/2017 HCI

Camera-Based Tracking

study.hci.one

  • EagleSense: Tracking People and Devices in Interactive Spaces using Real-Time Top-View Depth-Sensing

Chatbot Interfaces

study.hci.one

  • “Could You Define That in Bot Terms”?: Requesting, Creating and Using Bots on Reddit
    • bot開発時の注意点とかがまとまっていそうな気がする

Online Experiments

study.hci.one

  • Self-Experimentation for Behavior Change: Design and Formative Evaluation of Two Approaches
    • 「ユーザー自身が自分が使うツールを作る」という点に興味

All about Data

study.hci.one

  • Variolite: Supporting Exploratory Programming by Data Scientists
    • 自分の修論に近い
    • Git Integrationとかにはこっちのほうが良さげ
      • 自分の修論と組み合わせられる？
      • 最新のもの以外はこれで，みたいな感じに

Understanding Data Visualization

study.hci.one

  • Understanding Concept Maps: A Closer Look at How People Organise Ideas
    • コンセプトマップの自動生成