接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

AtCoder Beginner Contest 138 (ABC138)

精進日記といいつつ精進記事を生やしたことがなかったので書いてみます
今回は4完59分(1ペナ)でちょい冷えでした
コードや解法が間違っていたらぜひ指摘してください

A - Red or Not

条件分岐するだけですね
提出コード


int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int a;
string s;
cin>> a >> s;
if(a>=3200) cout << s << endl;
else cout << "red" << endl;
}

ところで珍しく早解きできてA提出時点で7位でした
この後はもう見どころがありません(かなしいね)


B - Resistors in Parallel

一瞬頭がこんがらがりましたが,分母を足していって最後にそれを逆数にするというふうにしました
提出コード


int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int N;
cin >> N;
double ans = 1;
double sum = 0;
REP(i,N){
double a;
cin >> a;
sum += 1/a;
}
sum = 1 / sum;
printf("%.8lf\n",sum);
}

C - Alchemist

ぱっと見貪欲法っぽそう
要素を全部プライオリティキューに入れて,小さい順に2つ取ってからその結果をまたキューに入れるみたいにやりました
ソートして取っていくだけでもいいみたいです
提出コード(プライオリティキュー版)
提出コード(ソート版)


int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int N;
cin >> N;
priority_queue,greater> pq;
REP(i,N){
double v;
cin >> v;
pq.push(v);
}
while(pq.size() != 1){
double x = pq.top(); pq.pop();
double y = pq.top(); pq.pop();
pq.push((x+y)/2);
}
double ans = pq.top();
printf("%.8lf\n",ans);

}

D - Ki
最初見た瞬間よくわからなくて,途中オイラーツアーとかをググっていました(ア)
AC数が多かったので愚直にDFSでクエリを処理して投げるとTLEしたので
ぐっと睨むと各頂点に加算しておいて最後にDFSで累積和っぽく伝搬させるとOKでした
ところでコンテスト中は有向辺だと思いこんでいて投げたら通りました(嘘)
問題文はちゃんと読もうね(反省)
提出コード(コンテスト後修正)


vector<vector<int>> G;
vector<ll> sum(202020);
void dfs(int v, int p, ll s){
sum[v] += s;
for(auto nv : G[v]){
if(nv == p) continue;
dfs(nv,v,sum[v]);
}
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int N,Q;
cin >> N >> Q;
G.resize(N);
REP(i,N-1){
int a,b;
cin >> a >> b;
--a,--b;
G[a].push_back(b);
G[b].push_back(a);
}
REP(i,Q){
int p,x;
cin >> p >> x;
--p;
sum[p] += x;
}
dfs(0,-1,0);
REP(i,N) cout << sum[i] << " ";
cout << endl;
}

E - Strings of Impurity
Dで時間かけてしまったため,コンテスト中は通せなかった
コンテスト後ガリガリ実装してると無事AC
Tを前から順に見ていってSにおける今いるindex(cur)と次の文字のindex(next)で答えを加算していくみたいな感じです
curよりも後にnextがあればそのまま取れば良くて
curよりも前にnextがあったらSを継ぎ足していくことになるので,|S| - curとnextを足していくみたいにやりました
インデックスを愚直に調べるとTLEするので二分探索で調べると間に合います
提出コード


int main(){
cin.tie(0);
ios::sync_with_stdio(false);
string S,T;
cin >> S >> T;
vector> idx(26);
REP(i,S.size()){
idx[(S[i]-'a')].push_back(i+1);
}
ll ans = 0;
int cur = 0;
REP(i,T.size()){
if(idx[T[i]-'a'].size() != 0){
int next_idx = upper_bound(idx[T[i]-'a'].begin(),idx[T[i]-'a'].end(),cur) - idx[T[i]-'a'].begin();
int next;
if(next_idx == idx[T[i]-'a'].size()){
next = idx[T[i]-'a'][0];
ans += (int)S.size() - cur;
cur = next;
ans += cur;
}
else{
next = idx[T[i]-'a'][next_idx];
ans += next - cur;
cur = next;
}
}
else{
cout << -1 << endl;
return 0;
}
}
cout << ans << endl;
}

おわりに

今回のDが2000人,Eが1250人くらい通していて人々強いなあという感想
こういう早解き回になるとパフォ取れないがちなので頑張りたいね

論文メモ ACL2019 Bestpaper 「Zero-Shot Entity Linking by Reading Entity Descriptions」

Zero-Shot Entity Linking by Reading Entity Descriptions

Lajanugen Logeswaran, Ming-Wei Chang, Kenton Lee, Kristina Toutanova, Jacob Devlin and Honglak Lee
ACL2019
https://www.aclweb.org/anthology/P19-1335

どんなもの?

ゼロショットエンティティリンキングのタスクを新しく提案,そのデータセットを構築
レーニングデータ(in-domain)に出現しないエンティティ(out-domain)に対し,
ドメイン固有の知識を読解,推測することによって解決を試みる
pre-trainingとしてDomain-adaptive pre-training(DAP)を提案
f:id:tkm-kyudo:20190809192421p:plain

先行研究と比べてどこがすごい?

従来では使用されていない,コンテキスト中のメンションとエンティティの説明(記述)の間のアテンションが重要であることを示す
DAPを行うことでエンティティリンキングのパフォーマンスの改善を示す

技術や手法のキモはどこ?

DAP:ターゲットドメインのデータに対してのみ事前トレーニングをする
DAPを既存の事前トレーニングの後に挿入することで精度の向上

どうやって有効だと検証した?

DAPを行うことで,行わなかったときと比較し,精度の向上が確認された
f:id:tkm-kyudo:20190809192535p:plain
f:id:tkm-kyudo:20190809192538p:plain

議論はある?

BM25 scoring with LuceneによってTop-64の候補エンティティのカバー率は77%
→タスクの難しさと,候補生成に改善の余地があることを示している
f:id:tkm-kyudo:20190809192658p:plain

モデルのエラーと予測結果
f:id:tkm-kyudo:20190809192812p:plain
f:id:tkm-kyudo:20190809192826p:plain
f:id:tkm-kyudo:20190809192842p:plain
f:id:tkm-kyudo:20190809192848p:plain

次に読むべき論文は?

・Nitish Gupta, Sameer Singh, and Dan Roth. 2017. Entity linking via joint encoding of types, descriptions, and context. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing.
・Luheng He, Kenton Lee, Omer Levy, and Luke Zettlemoyer. 2018. Jointly predicting predicates and arguments in neural semantic role labeling. arXiv preprint arXiv:1805.04787

Google Cloud Platform (GCP)でGPUを使えるようにする

はじめに

GCPGPUを使えるようにする際に幾つかハマったところがあったので残しておきます

GCPアカウントの作成

はじめにGCPアカウントの作成を行います。
アカウント作成については以下の記事などを参照してください。
【GCP入門編・第2回】まずは、ここから!知らないと恥ずかしい Google Cloud Platform (GCP) の事前準備! | 株式会社トップゲート

Google Compute Engine(GCE)の利用

GCPアカウントを作成したら、プロジェクトが出来ていると思います。
新しくプロジェクトを作成してもいいです。
プロジェクトを作成したら、GCEのインスタンスを立てる前にGPUの割り当てというものを行います。
メニューからIAMと管理を選択します。
次に左のメニューから割り当てを選択します。
すると、次のような画面になっていると思います。
f:id:tkm-kyudo:20190704130852p:plain
指標のところで使いたいGPUを選択肢し、自分の使いたいリージョンのところを確認します。
ここで、上限が1になっていればすでに1つ割当てられています。

ハマったところ

GPUを割り当ててインスタンスを作成するときにGPUを選択すると、エラーが起きました。
色々調べると、Compute Engine APIが割当てられていないことが原因でした。(以下の記事のハマりポイント2参照)
Compute Engine APIの割当て申請を行います。
GCEでtensorflow-gpuの環境を構築する - Qiita

インスタンス作成

インスタンスの作成は以下の記事を参照してください。
【GCP入門編・第3回】難しくない! Google Compute Engine (GCE) でのインスタンス起動方法! | 株式会社トップゲート
インスタンスの作成の際に画像のGPUを追加のところから使用したいGPUを選択します。
OSはubuntu16.04にしました。
f:id:tkm-kyudo:20190704131635p:plain

GPUドライバのインストール

インスタンスを作成したら、インスタンスにアクセスします。
自分はGoogle Cloud SDKを利用しました。
SDKを利用する際は、公式ドキュメントを参照してインストールしてください。
Google Cloud SDK documentation  |  Cloud SDK  |  Google Cloud

自分の環境だとデフォルトでsudoが使えなかったので、以下の記事を参考にsudoを使えるようにしました。
OS LoginでGCEインスタンスへのSSH接続を管理する - 本日も乙

sudoが使えるようになったら、公式ドキュメントを参照しながらドライバをインストールします。
自分は公式のスクリプトを利用しました。

vi gpu_install.sh
#!/bin/bash
echo "Checking for CUDA and installing."
# Check for CUDA and try to install.
if ! dpkg-query -W cuda-10-0; then
  # The 16.04 installer works with 16.10.
  curl -O http://developer.download.nvidia.com/compute/cuda/repos/ubuntu1604/x86_64/cuda-repo-ubuntu1604_10.0.130-1_amd64.deb
  dpkg -i ./cuda-repo-ubuntu1604_10.0.130-1_amd64.deb
  apt-key adv --fetch-keys http://developer.download.nvidia.com/compute/cuda/repos/ubuntu1604/x86_64/7fa2af80.pub
  apt-get update
  apt-get install cuda-10-0 -y
fi
# Enable persistence mode
nvidia-smi -pm 1
sudo bash gpu_install.sh

スクリプトが終わったら以下のコマンドで確認します。

nvidia-smi

f:id:tkm-kyudo:20190704133115p:plain
無事GPUが認識されました。

CRFsuiteをバイナリディストリビューションを使用してインストールする

はじめに

CRFsuiteをバイナリディストリビューションを使ってインストールします
ソースファイルからバイナリをビルドする方法ではmakeが上手く行かなかったためこちらを試します

環境

Linux(CentOS7)

インストール

Linux用のバイナリディストリビューションをダウンロードして、解凍します

wget https://github.com/downloads/chokkan/crfsuite/crfsuite-0.12-x86_64.tar.gz
tar -zxvf crfsuite-0.12-x86_64.tar.gz

解凍したら、実行ファイルにパスを通します

cd crfsuite-0.12/bin
sudo mv crfsuite /usr/local/bin

これで終わりです
コマンドラインでcrfsuite -hと打ってhelpが出てきたら完了です

論文メモ 「Joint Learning of the Embedding of Words and Entities for Named Entity Disambiguation」

Joint Learning of the Embedding of Words and Entities for Named Entity Disambiguation

Ikuya Yamada, Hiroyuki Shindo, Hideaki Takeda, Yoshiyasu Takefuji
The SIGNLL Conference on Computational Natural Language Learning (CoNLL), 2016
https://aclweb.org/anthology/K16-1025

どんなもの?

Named Entity Disambiguation(NED)タスクに対し単語とエンティティを一緒に連続したベクトル空間に埋め込んだもの(embedding)を利用することを提案

先行研究と比べてどこがすごい?

・CoNLLデータセット:93.1%
・TAC2010データセット:85.2%
上記のデータセットにおいて、accuracyでSOTA(当時)

技術や手法のキモはどこ?

Knowledge base(KB)モデルとanchor context modelの2つを使用してskip gramモデルを拡張する

どうやって有効だと検証した?

実験結果によりSOTA達成
f:id:tkm-kyudo:20190531170056p:plain

議論はある?

候補エンティティ生成方法がパフォーマンスに影響することがわかった

システムに特徴量を加えた結果、SOTAに匹敵する結果を得られた
f:id:tkm-kyudo:20190531170240p:plain

次に読むべき論文は?

Johannes Hoffart, Stephan Seufert, Dat Ba Nguyen, Martin Theobald, and Gerhard Weikum. 2012. KORE: Keyphrase Overlap Relat- edness for Entity Disambiguation. In Proceedings ofthe 21st ACMInternational Conference on Infor- mation andKnowledge Management (CIKM), pages 545–554.