うしのおちちの備忘録

AtCoderや日記、自然言語処理などについて書きます。

病名の表記揺れを吸収するライブラリを作った

はじめに

日本語の病名を病名辞書である万病辞書に紐づけるパッケージを所属研究室のRAとして作りました。この記事ではそもそも病名の表記揺れとはどういうものなのかから、パッケージの基本的な機能を紹介します。

github.com

病名の表記揺れ吸収

医療のテキストデータを扱っている人なら経験があると思いますが、病名は電子カルテや医学論文中でさまざまな表記をされます。例えば、「高血圧」が「HT」とか具体的な血圧値で書かれていたりしていて、そのままだとシステムは全くの別物としてみなしてしまいます。そのため、書かれている病名を概念レベルでまとめる必要があり、それを病名の表記揺れ吸収とかいったりして、自然言語処理系の会議や医療情報系のジャーナルとかでよく研究されています。

病名の表記揺れ吸収は、類義語がたくさん集まった辞書を用意し、入力テキストと一番近い類義語を見つけることで行われます。類義語はICD-10とかの疾病の分類に紐づいているので、それと似ている入力テキストも同じ概念だろう、というわけです。

高度な推論についてはACLなどの自然言語処理のトップ会議の論文(最近だと[1, 2]とか)をみていただくとして、実用上はもっと手軽に、だけどそれなりの精度で表記揺れを吸収したい場面も多いと思います。英語ではMetaMapとか有名なソフトウェアがあり広く普及していますが、日本では代表的なソフトウェアは自分の知る限り公開されていません。

そのため、日本語の病名辞書である万病辞書をベースに、日本語の病名の表記揺れ吸収パッケージをつくりました。簡単に機能などを紹介します。

機能

基本的には入力された病名を、一番近い万病辞書のエントリに紐付けます。

>>> from japanese_disease_normalizer.normalizer import Normalizer
>>> normalizer = Normalizer("abbr", "fuzzy")
>>> normalizer.normalize("急性骨髄性白血病")
DictEntry(name="急性骨髄性白血病", icd="C920", norm="急性骨髄性白血病", level="S")

他の細々した機能は以下の通りです。

  • 略語の展開
    入力したテキストの任意の部分文字列について、アルファベットがあった場合に略語の展開を試みます。下にいくつか簡単な例を出します。内部的には略語辞書での完全一致による変換を行っています。
>>> normalizer.normalize("AML")
DictEntry(name="急性骨髄性白血病", icd="C920", norm="急性骨髄性白血病", level="S")

>>> normalizer.normalize("低K血症")
DictEntry(name="低カリウム血症", icd="E876", norm="低カリウム血症", level="S")
  • Spacy extension
    Spacyの固有表現抽出の後ろにつけるコンポーネントです。add_pipeしておけば、固有表現について先程の表記揺れ吸収までしてくれるようになります。ちなみにSpacyの病名認識モデルも公開予定なので、それと合わせると手軽に病名を抽出・表記揺れ吸収できます。
import spacy
from japanese_disease_normalizer.spacy_extension import ManbyoNormalizer

nlp = spacy.load("/path/to/NER_model")
nlp.add_pipe("manbyo_normalizer")

text = "急性骨髄性白血病により緊急入院"
doc = nlp(text)
for ent in doc.ents:
    print(ent._.norm)

現状でできないこと

とはいえ高度な推論を行っていないので、できないこともたくさんあります。

  • 文脈を考慮した表記揺れ吸収
    例えば「AML」は「急性骨髄性白血病」と「血管筋脂肪腫」の二通り考えられますが、それは文書の性質や文脈をみないとわかりません。今回のパッケージではそれは考慮していません。

  • 意味的な類似性を考慮した推論
    単語埋め込み表現などを利用しておらず、文字列としての類似性のみに着目しています。そのため、万病辞書のエントリとかけ離れている表現への動作は保証できません。

おわりに

今回は病名表記揺れ吸収のパッケージを紹介しました。まだまだ不完全な部分が多いですが、使っていただける方がいればフィードバックをいただけると幸いです。

参考文献

[1] Liu F, Shareghi E, Meng Z, Basaldella M, Collier N. Self-Alignment Pretraining for Biomedical Entity Representations. In: Proc. of NAACL; 2021:4228-4238.
[2] Angell R, Monath N, Mohan S, Yadav N, McCallum A. Clustering-based Inference for Biomedical Entity Linking. In Proc. of ACL; 2021:2598-2608.

Rust✖️WebAssemblyでブラウザ上で固有表現抽出する

はじめに

最近sudachi.rsをwasmにビルドして使ってるツイートを見て、自然言語処理の結構いろんなことが同じようにできるのではと思い、手始めに固有表現抽出してみることにしました。

https://twitter.com/vbkaisetsu/status/1412761328943460355?s=21

使用ライブラリ

形態素解析

sudachi.rsdを使います。ただ、2021/9/15日現在のものではビルドは通りますが初期化時にどうしてもパニックしてしまうため、適当に動いてそうなコミットまで戻って使いました。

固有表現抽出

今回はRust✖️WebAssemblyの入門ということで、簡単にCRFを使うことにします。 Rustではpure-rustで書かれたCRFクレートが公開されています。ただ、学習には対応していないようなので、学習だけはcrfsuiteのRustバインディングを使う必要があります。とはいっても、メンテナは同じみたいで、実際使い勝手はほとんど変わらないので特に問題はなさそうです。

モデルの学習

先ほど紹介したcrfsuite-rsを使って、固有表現抽出用のモデルを学習していきます。 今回はたまたま手元に病名抽出の学習データがあるので、それを使っていきます。

データの準備

とりあえずIOB2タグ形式の学習データを作っていきます。別にxmlみたいな生テキストから形態素解析するところまで学習コードでやってもいいですが、IOB2タグ形式のデータが手元にあってのでそれベースでやっていきます。

IOB2タグ形式のファイル例です。1行1トークンで(トークン、ラベル)列を並べて行って、空行で文を区切ります。今回は文字種や品詞を特徴量として使わないのでそれらの情報は入れていません。

今治 O
タオル O
は O
愛媛 B-Location
の O
誇り O
だ O

みかん O
は O
おいしい O

ちなみにbratなどを使っていてデータ形式がオフセットになっている場合、Spacyのiob_utilsが便利です。生テキストとオフセットを入れると、タグが返ってきます。現状BILUO形式しか対応していませんが、BILUOからBIOへの変換の関数も用意されているのでそれを使えばオッケーです。

データの前処理

crfsuite-rsは、1文ごとに素性列Vec<Vec<Attribute>>とラベル列Vec<String>を用意して学習に使います。Attributenamevalueを持つ構造体で、nameに素性を、valueに素性の値を入れます。valueは特に素性に重み付けしたいわけでなければ全部1で良さそうです。

とりあえずIOB2タグ形式のデータを読み込みます。Rusut初心者なので書き方が拙いのは勘弁してください...

use std::fs::File;
use std::io::{self, BufRead, BufReader};

fn load_dataset(path: &str) -> (Vec<Vec<Vec<Attribute>>>, Vec<Vec<String>>){
    let file = File::open(path).unwrap();
    let reader = BufReader::new(file);
    let mut x_sent: Vec<String> = Vec::new();
    let mut y_sent: Vec<String> = Vec::new();

    let mut x_all: Vec<Vec<Vec<Attribute>>> = Vec::new();
    let mut y_all: Vec<Vec<String>> = Vec::new();

    for line in reader.lines() {
        let l = line.unwrap();
        if l == "" {
            if x_sent.len() != 0 {
                let attributes = extract_features(&x_sent);
                x_all.push(attributes);
                y_all.push(y_sent);

                x_sent = Vec::new();
                y_sent = Vec::new();
            }
            continue;
        }

        let mut iter = l.split_whitespace();
        let x = match iter.next() {
            Some(x) => x.to_string(),
            None => {
                "None".to_string()
            }
        };
        let y = match iter.next() {
            Some(x) => x.to_string(),
            None => {
                "None".to_string()
            }
        };
        x_sent.push(x);
        y_sent.push(y);
        assert_eq!(iter.next(), None);
    }
    (x_all, y_all)
}

読み込んだデータを素性に変換していきます。今回は精度を追い求めているわけではないので、前後一文字とBi-gramだけを素性に使います。

use crfsuite::Attribute;
fn extract_features(sent: &Vec<String>) -> Vec<Vec<Attribute>> {
    let mut result: Vec<Vec<Attribute>> = Vec::new();
    for idx in 0..sent.len() {
        let mut attributes: Vec<Attribute> = Vec::new();
        attributes.push(Attribute::new(&sent[idx], 1.0));

        let pre_word = match idx {
            0 => "BOS",
            _ => &sent[idx-1],
        };

        let post_word = match idx {
            n if n >= sent.len() - 1 => "EOS",
            _ => &sent[idx+1],
        };

        attributes.push(Attribute::new(format!("-1_{}", pre_word), 1.0));
        attributes.push(Attribute::new(format!("{}_{}", pre_word, &sent[idx]), 1.0));

        attributes.push(Attribute::new(format!("+1_{}", post_word), 1.0));
        attributes.push(Attribute::new(format!("{}_{}", &sent[idx], post_word), 1.0));

        result.push(attributes);
    }
    return result;
}

モデルの学習

先ほど読み込んだデータを元にモデルを学習します。モデルの学習自体は特に難しいことはなさそうですね。ドキュメントは充実してないですが、適当にテストコードみてパクりました。 学習はCPUでも十分におわります。学習データは50万文程度でしたが、半日放置すれば学習は終わっていました(放置していた&時間測ってないせいで正確な学習時間はわかりませんが...)。

use std::path::Path;
use crfsuite::{Trainer, Attribute, Algorithm, GraphicalModel};

fn main() {
    let train_path = Path::new("./resource/train.iob");
    let valid_path = Path::new("./resource/valid.iob");
    let (x_all, y_all) = load_dataset(train_path.to_str().unwrap());

    let mut trainer = Trainer::new(true);
    trainer
        .select(Algorithm::LBFGS, GraphicalModel::CRF1D)
        .unwrap();

    for (x_sent, y_sent) in x_all.iter().zip(y_all.iter()) {
        trainer.append(x_sent, y_sent, 0i32).unwrap();
    }
    trainer.train("models/hatena/crfsuite", -1i32).unwrap();
}

推論

生テキストを読み込んで、学習させたCRFに推論させていきます。推論には冒頭で触れたCRFクレートであるcrfs-rsを使います。使い方は学習時に使ったものと同じです。ラベルの遷移に制限をつけたかったですが、そういう機能は見つけられませんでした。例えばOからIには絶対に遷移しないので、遷移行列に罰則を加えたりしたかったですよね。

ともあれ、一緒にwasm-bindingjs-sysを使ってWebAssembly用にコードを書きます。基本的には#[wasm_bindgen]をつけた関数などがWebAssemblyで使えるようにコンパイルされます。

include_bytes!でモデルと辞書を埋め込んで、WebAssemblyで呼び出せるように書いていきます。

use crfs::Model;
use wasm_bindgen::prelude::*;

#[wasm_bindgen]
pub struct NER {
    tagger: Model<'static>,
    tokenizer: Tokenizer<'static>,
}

#[wasm_bindgen]
impl NER {
    pub fn new() -> Self {
        // data for crf
        let buf = include_bytes!("/path/to/models/hatena.crfsuite");

        // data for tokenizer
        let bytes = include_bytes!("/path/to/sudachi.rs/src/resources/system.dic");
        Self {
            tagger: Model::new(buf).unwrap(),
            tokenizer: Tokenizer::new(bytes),
        }
    }
}

学習時にはすでにトークナイズ済みのデータを使っていましたが、推論では生テキストを扱うので、形態素解析のための関数も必要です。トークナイズはwasmから呼び出す必要はないので#[wasm_binding]はつけません。

impl NER {
    pub fn tokenize(&self, s: &str) -> Vec<String> {
        let morpheme_list = self.tokenizer.tokenize(&s.to_string(), &Mode::B, false);

        let tokens: Vec<String> = morpheme_list
            .iter()
            .map(|m| String::from(m.surface()))
            .collect();
        return tokens;
    }
}

いよいよ、生テキストを読み込んでIOB2タグ系列を返す関数を作ります。IOB2タグだけ返しても仕方ないので、トークン列も一緒に返すことにします。javascriptで使うのでjs-sysというクレートでjavascript対応の変数に変換しています。

use js_sys::{Array, JsString, global, Object};

#[wasm_bindgen]
impl NER {
    pub fn tag(&mut self, sent: &str) -> Array {
        let xseq = self.tokenize(sent);

        let mut tagger = self.tagger.tagger().unwrap();
        let attributes = extract_features(&xseq);
        let res = tagger.tag(&attributes).unwrap();
        let yseq: Array = res.iter()
            .map(|s| JsString::from(s.to_string()))
            .collect();
        let xseq: Array = xseq
            .iter()
            .map(|s| JsString::from(s.clone()))
            .collect();
        Array::of2(&xseq, &yseq)
    }

WebAssembly

Cargo.toml

Cargo.tomlはこんな感じです。別に変わったことはありませんが、crate-type = ["cdylib"]にすることだけ注意です。

[package]
name = "ner-wasm"
version = "0.1.0"
authors = ["ujiuji1259 <suzzz428@gmail.com>"]
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[lib]
crate-type = ["cdylib"]

[dependencies]
js-sys = "0.3.52"
wasm-bindgen = "0.2.74"
crfs = "0.1.3"

[dependencies.sudachi]
path = "/path/to/sudachi.rs"

ビルド

wasm-packといういい感じにjavascriptから使えるwasmにビルドしてくれる便利なツールがあるので、それを使います。インストールはcargo install wasm-packするだけです。

--target webにしておくと、javascriptから直接触れる感じのコードにしてくれるらしいです。web-packとか必要ない人はこちらで十分ぽいですが、正直よくわかってないです。

# install
cargo install wasm-pack

# build
wasm-pack build --target web

Javascriptから呼び出す

ビルドしたらpkgというディレクトリにいろいろ生成されますが、{パッケージ名}.jsというモジュールからビルドしたWebAssemblyを全部呼び出せます。

<script type="module">
    import init, {NER} from './pkg/ner_wasm.js';

    function ner() {
        let wasm = await init();
        model = NER.new();
        let tokens = model.tag("急性骨髄性白血病とは、血液のがんの一種です。");

        console.log(tokens[0]);
        console.log(tokens[1]);
    }
</script>

結果

がんはとれてないですが、急性骨髄性白血病はちゃんととれてるっぽいです。

f:id:kuroneko1259:20210816011121p:plain
出力結果

おわりに

RustでCRFによる固有表現抽出モデルを学習して、wasmとしてブラウザ上で動かしてみました。 固有表現抽出でも例に漏れずBERTなどが猛威を奮っていますが、シビアに精度が求められない場合はCRFでも十分固有表現抽出できたりします。CPUでも十分学習できますし、そんなにモデルサイズも大きくないです(素性の取り方によると思いますが、今回のモデルが67MBくらいです)。ブラウザで動作することを考えれば十分感がありませんか?

何に使えるかはわかりませんが、同じようなことがBERTとかでもできると思うので、いろいろ試していこうと思います。

森羅2020-JPでNER入門

はじめに

概要

本記事では、森羅プロジェクトで開催されている日本語Wikipediaを対象とした属性抽出タスクについて、学習データの取得からモデルの構築までの流れを簡単に解説します。 具体的には、以下のことについて説明していきます。

  • 森羅プロジェクトの概要
  • 属性抽出のアプローチ
  • データの取得・前処理
  • モデルの構築

今回のコードはこちらに公開しています。

対象読者

  • 森羅プロジェクトに参加してみたいけど、どういう流れで進めていいか分からない人
  • BERTを使って日本語で固有表現抽出してみたい人
  • pytorchでの深層学習における基本的な流れを知りたい人

前提知識

実行環境

著者は以下の環境で実行しました。

torch==1.7.1
transformers==4.3.3

少なくともtransformers>=3.0.1ではある必要があると思います。環境構築が難しそうな方は、こちらのDockerfileで今回の環境を構築していただけます。

森羅プロジェクト

森羅プロジェクトって?

森羅プロジェクトは、RIKEN AIPが進めているリソース構築プロジェクトです。公式ページでは以下のように説明されています。

森羅プロジェクトは2017年にスタートしたリソース構築プロジェクトで、人が読むことを想定して書かれたWikipediaの知識を計算機が扱える形に構造化することを目指し、「協働によるリソース構築(Resource by Collaborative Contribution(RbCC))」という枠組みで、評価型タスクとリソース構築を同時に進めています。

要するに、「Wikipediaの記事を、パソコンがわかるように整理したい!」というプロジェクトです。

詳しく見るために、松山市Wikipediaを例にとってみていきましょう。松山市の記事には、概要として以下の内容が記述されています。

約50万9千人の人口を有する四国最大の都市であるが、日本の1地方の最大の都市では唯一の100万人以下で政令指定都市ではない都市である[* 2]。中四国においては、政令指定都市である広島市岡山市に次ぐ3番目の人口規模を有する。都市圏人口は、総務省統計局の定義における「松山都市圏]」が70万6883人(2015年)、都市雇用圏の「松山都市圏」が64万2841人(2010年)である。

ここから人間は「松山は四国にある」「人口は約50万9千人」など、多くの情報を得ることができます。しかし、コンピュータはそうはいきません。これらの情報を情報技術で活用しようと思うと、以下のように、もっと明示的に情報を与えてやる必要があります。

属性 情報
所在地 四国
人口 約50万9千人

Wikipediaでは、これらの情報はinfoボックスとして部分的に提供されていますが、多くの場合、記事本体に文として記述されています。そのため、テキスト(非構造化データ)から表(構造化データ)に変換する必要があり、このタスクを構造化タスクと言います。 森羅プロジェクトは、wikipediaの記事を表形式にまとめる(構造化する)プロジェクトと言えます。

日本語構造化タスク

概要

森羅プロジェクトは前述の構造化を進めるため、シェアドタスク(kaggleのコンペのようなもの)を主催しています。このタスクでは、各カテゴリwikipediaの記事から拡張固有表現で定義された属性に対応する文字列を抽出します。拡張固有表現については説明を省きますが、上述の表における属性の集合と思っていただいて構いません。

ここで、このタスクにおけるカテゴリ属性を整理しておきます。すごく大雑把にいうと、wikipediaの各記事は、カテゴリにあらかじめ分類されており、そのカテゴリに応じて抽出すべき属性が定義されています。

例えば、Cityカテゴリには所在地人口などの属性が定義されています。 先程の「松山市」という記事はCityカテゴリに分類されているため、これらの属性に対応して「四国」「約50万9千人」を抜き取ってきます。

このタスクでは、「人名」や「化合物名」、「選挙名」などさまざまなカテゴリについて学習データが提供されているため、色々なドメインのデータについてモデルを試すことができます。詳細は公式ページを参照してください。

タスクの流れ

タスクは以下のような流れで進んでいきます。

  1. 森羅プロジェクトへの登録
  2. 学習データの取得
  3. モデルの構築
  4. 結果の提出

なお、タスクとしての評価はカテゴリが複数個集まったグループ単位で行われるようです。結果として、抽出した文字列だけでなく、データ中の文字の位置(オフセット)も合わせて提出する必要があります。

属性抽出のアプローチ

ここまでみてきたように、属性抽出(情報抽出)は「文字列を抽出する」ことで実現されます。(多くの場合「抽出した文字列を正規化する(normalize)」処理が入りますが、本タスクの範囲外のため割愛します。)

本節では、情報抽出の基本的なアプローチについて説明していきます。「固有表現抽出なんてもう知ってるよ!」という方はまるっとここを飛ばしてください。

固有表現抽出

「固有表現抽出」は、テキストから対象となる文字列を抽出できる技術です。ここでは特に、各トークン(文字or単語or形態素)にラベルを付与していく方法を紹介します。一般的な表記にならい、固有表現抽出はNamed Entity Recognition (NER)、抽出する文字列を固有表現と表現します。

トークンの分類

この方法では、文をトークン列に分解し、それぞれのトークンについて分類問題を解きます。分類により付与されるラベルによって、どの部分トークン列が固有表現かどうかを判断します。

例として、松山市はとても住みやすいという文から松山市という都市名を抽出することを考えます。この文をMeCab形態素解析すると松山 市 は とても いい ところ だ 。になります。この時、各形態素に以下のようなラベルを振っていきます。

松山 とても いい ところ
B-CITY I-CITY O O O O O O

ここで、B-は固有表現の先頭、I-は固有表現がそのトークンまで続いていること、Oは固有表現でないトークンを表します。このラベル付さえできてしまえば、B-から連続してI-にラベル付されたトークンを選ぶことで、固有表現を抽出することができます。

今回のラベルのフォーマットをIOB2と呼びます。他にもIOB1BIOESといったフォーマットがあり、それぞれに利点がありますが、広く用いられているのはIOB2のようです。

分類手法

トークンのラベルの分類手法として、最も素朴には、各トークンを独立に分類する手法が考えられます。これは、各トークンに対して特徴量を抽出し、その特徴量のみから分類する手法です。本記事でもこの手法をとります。

より具体的に、特徴量の抽出器としてRNNなどの時系列を扱う深層学習モデルを考えます。ここでは、モデルはブラックボックスとして扱いますので、気になる方は参考記事を参照してください。この手法では、図のように、あるモデルから得た各トークンの特徴量を、それぞれ重みを共有した出力層に流すことで各トークンを分類します。

f:id:kuroneko1259:20210812162006p:plain
NERモデルの概略

発展

トークンの分類は、トークン列全体として最適化する系列ラベリングとして定義されます。これは、他のトークンの分類結果に依存するためです。よくConditional Random Field (CRF)が用いられ、深層学習モデルとCRFを組み合わせる手法も提案されており [1]、AllenNLPなどで簡易に扱うことができます。

データの取得・前処理

学習データをダウンロード、処理していきます。

データの取得

データのダウンロードはこちらから行えます。ダウンロードするためには、アカウント登録する必要があります。ダウンロードページに、アカウント登録ページがあるので、各自登録してください。氏名やメールアドレスなどの登録だけなので、すぐに済みます。

配布データとして、「学習データ・ターゲットデータ」と「学習データ・ターゲットデータ(トークナイズ)」があります。「学習データ・ターゲットデータ(トークナイズ)」は、あらかじめ記事をトークン列に分解し、テキストオフセットと対応付けられたデータです。 データが膨大でトークナイズはかなり時間がかかる+テキストオフセットとトークンの対応付けが若干めんどくさいので、余程の理由がない限り「学習データ・ターゲットデータ(トークナイズ)」をダウンロードすることをお勧めします。今回は、東北大BERTを使用するので「MeCab (IPA辞書)+BPE」をダウンロードします。

データ形式トークナイザのgithubに詳しく記載されています。(トークナイザ前データの詳細はこちらにある通りです。)データは、アノテーションされたデータ(学習データ)とされていないデータ(テストデータ)の2種類があります。アノテーションの情報は*_dist.jsonにまとまっていますので、ここに情報のない記事はテストデータとなります。

データの注意点

今回のデータはエンティティが入れ子になることがあります。 前節の固有表現抽出の枠組みではエンティティの範囲は重複しない想定だったので、それらに対応する必要があります。

今回は各属性ごとに分類層を用意することで入れ子のエンティティに対応することにして、それに応じてデータの前処理をしていきます。 つまり、「City」や「Popularity」ごとに独立にIOBタグの分類を行います。

前処理

配布フォーマットはアノテーションデータとトークンデータが分かれているため、前節で見たように、NER用に(トークン、IOB2ラベル)のペアに変換する必要があります。

  • 元データ

    • (カテゴリ名)_dist.json

      {"page_id": "3507880", "title": "アンパーラ空港", "attribute": "別名", "html_offset": {"start": {"line_id": 39, "offset": 395}, "end": {"line_id": 39, "offset": 406}, "text": "SLAF Ampara"}, "text_offset": {"start": {"line_id": 39, "offset": 61}, "end": {"line_id": 39, "offset": 72}, "text": "SLAF Ampara"}, "ENE": "1.6.5.3", "token_offset": {"start": {"line_id": 39, "offset": 7}, "end": {"line_id": 39, "offset": 9}, "text": "SLAF Ampara"}}

    • (page_id).txt

      717,0,2 11,3,4 580,4,8 20,8,9 23,9,10 240,10,12 510,12,13 32,0,1 30,1,2 3812,2,5 30,5,6 5056,6,9 245,9,10 494,10,12 832,12,14 1117,0,2 30,2,3 5207,3,6 657,6,7

  • 作りたいデータ形式(IOB2形式)

    tokens: ["松山", "市", "は", ...] label1( = City): ["B", "I", "O", ...] label2( = Event): ["O", "O", "O", ...]

これは泥臭く変換するだけですので、前処理がめんどくさい方は私が書いたコードを使ってください。ダウンロードしたデータのパスを指定すれば、属性ごとにIOB系列への変換などをしてくれます。

自分で変換コードを書く際の注意点として、配布データは文字列ではなくIDで単語を管理されています。これはデータ容量を減らすためです。IDと単語のマッピングvocab.txtで提供されています。(参照

モデルの構築

いよいよモデルを構築していきます。 ここからはこのコードから説明に必要な部分を適宜抜粋する形で進めていきます。

基本的な流れは以下の通りです。

  1. データの読み込み
  2. モデルの作成
  3. 学習

それぞれ大雑把に見ていきます。コードの詳細には言及しませんが、補足となるリンク等をつけていますので、詳しく知りたい方はそちらをご確認ください。

データの読み込み

まず、データを読み込む必要があります。今回はpytorchで提供されているDatasetクラスを利用します。Datasetクラスでデータセットを読み込んでおけば、データセットの部分集合を取ったりバッチ処理をするのが楽になります。 Datasetクラスの自作については、このリンクがわかりやすいです。

Datasetの作成

今回のデータを読み込むNerDatasetクラスを試しに実装してみます。 入力はトークンID、単語のインデックス、ラベルの辞書のリストです。

class NerDataset(Dataset):
    label2id = {
        "O": 0,
        "B": 1,
        "I": 2
    }
    # datas = [{"tokens": , "word_idxs": , "labels": }, ...]
    def __init__(self, data, tokenizer):
        self.tokenizer = tokenizer
        self.data = data

    def __len__(self):
        return len(self.data)

    def __getitem__(self, item):
        input_ids = ["[CLS]"] + self.data[item]["tokens"][:510] + ["[SEP]"]
        input_ids = self.tokenizer.convert_tokens_to_ids(input_ids)
        word_idxs = [idx+1 for idx in self.data[item]["word_idxs"] if idx <= 510]

        labels = self.data[item]["labels"]
        if labels is not None:
            # truncate label using zip(_, word_idxs)
            labels = [[self.label2id[l] for l, _ in zip(label, word_idxs)] for label in labels]

        return input_ids, word_idxs, labels

Datasetクラスで必要なのは、__len____getitem__です。datasetインスタンスがあった時、__len__((self))len(dataset)__getitem__(self, item)dataset[item]の動作を定義します。

NerDatasetを使って実際にEvent/Event_Otherカテゴリのデータを読み込んでみます。

from transformers import BertJapaneseTokenizer
tokenizer = BertJapaneseTokenizer.from_pretrained('cl-tohoku/bert-base-japanese')
shinra_dataset = ShinraData.from_shinra2020_format("/path/to/Event/Event_Other")[0]
dataset = NerDataset(shinra_dataset[0].ner_inputs, tokenizer)

dataset[0]の結果(1文目のデータ)は以下のようになります。

f:id:kuroneko1259:20210812162008p:plain
Datasetの出力

word_idxはサブワード列における各単語の開始位置です。BERTはサブワード(単語をさらに分解したもの)を入力としますが、単語の途中で固有表現が始まるとは考えにくいため、後で単語単位の系列にもどしてやるために使います。 labelsは属性ごとにIOBタグがふられています。このデータでは全てOのようです。

DataLoaderによるバッチ処理

PyTorchには、いくつかのデータをまとめてロードしてくれるDataLoaderクラスが提供されています。 Datasetを入れてやることで、勝手にバッチ処理をしてくれるようになります。

from torch.utils.data import DataLoader
def ner_collate_fn(batch):
    tokens, word_idxs, labels = list(zip(*batch))
    if labels[0] is not None:
        labels = [[label[idx] for label in labels] for idx in range(len(labels[0]))]

    return {"tokens": tokens, "word_idxs": word_idxs, "labels": labels}

dataloader = DataLoader(dataset, batch_size=16, collate_fn=my_collate_fn)

DataLoaderクラスをそのまま使うと、各データの次元を揃えろと怒られてしまうので、collate_fnを指定する必要があります。画像だと元からデータの次元が揃っているので必要ありませんが、自然言語処理などのように可変長データの場合は自作して渡してあげましょう。

パディング

PyTorchの実装上、全てのデータの次元が揃った状態でモデルに入力を渡さなければなりません。各データは可変長のため、入力次元を揃えるために0埋めしてやる必要があります。この処理をパディングといいます。PyTorchではpad_sequenceが提供されています。このサイトがわかりやすいです。

import torch
from torch.nn.utils.rnn import pad_sequence
for inputs in dataloader:
    input_ids = inputs["tokens"]
    word_idxs = inputs["word_idxs"]
    labels = inputs["labels"]

    labels = [pad_sequence([torch.tensor(l) for l in label], padding_value=-1, batch_first=True).to(device) for label in labels]
    input_ids = pad_sequence([torch.tensor(t) for t in input_ids], padding_value=0, batch_first=True).to(device)

ハマりポイントとして、batch_firstがあります。batch_firstはデフォルトでFalseとなっていますが、Falseだと(sequence length, batch size, input size)tensorが返ってきます。(batch size, sequence length, input size)にするためにはこれをTrueにする必要があります。

ここで、labelspadding_value-1にしています。この値は損失関数であるnn.CrossEntropyLossignore_idxと対応させた値にします。こうすることで、ignore_idxに設定したトークンは損失計算で無視されます。

モデル

今回はモデルにBERT [2]を使います。BERTは大規模なテキストで事前学習した汎用言語モデルで、さまざまなタスクで高い精度が確認されています。巷にたくさん解説記事があるので、気になる方はそちらをご参照ください。参考記事

PyTorchでは、haggingfaceが提供するtransformersというライブラリで簡単にBERTを試すことができます。 しかも、BERTを使った簡単な分類モデルやNERモデルも、ワンラインで読み込むことができ、NERにはBertForTokenClassificationが使えます。

が、今回はBertForTokenClassificationから以下の変更を加える必要があります。

  • 各属性ごとに独立した分類層を用意する
  • サブワード単位ではなくワード単位で分類を行う

基本的にはBertForTokenClassification元コードに改変を加える形で実装していきます。要点だけかいつまんでいるので、詳細はコードを参照してください。

分類層の追加

出力層を属性の数だけ増やしてあげます。以下のコードはモデルの__init__.pyの抜粋です。List[nn.Module]nn.ModuleList[nn.Module]にしなければモデルにパラメータとして認識されないことに注意してください。

# classifier that classifies token into IOB tag (B, I, O) for each attribute
output_layer = [nn.Linear(768, 768) for i in range(attribute_num)]
self.output_layer = nn.ModuleList(output_layer)

self.relu = nn.ReLU()

# classifier that classifies token into IOB tag (B, I, O) for each attribute
classifiers = [nn.Linear(768, 3) for i in range(attribute_num)]
self.classifiers = nn.ModuleList(classifiers)

forwardではそれぞれの分類層にBERTの出力を流し込んでいきます。

hiddens = [self.relu(layer(sequence_output)) for layer in self.output_layer]
logits = [classifier(hiddens) for classifier, hiddens in zip(self.classifiers, hiddens)]
logits = [classifier(sequence_output) for classifier in self.classifiers]
単語単位へのプーリング

BERTでは単語をさらに分割してサブワードという単位で処理します。例えば「松山」という単語を「松」「##山」に分割する、という具合です。なので、当然特徴量もサブワード単位で出てきて、分類もサブワード単位になってしまいます。
とはいっても、固有表現が単語の途中で区切られるとは考えにくいので、固有表現抽出としては単語単位で処理をするのが一般的です。そのため、サブワード単位の特徴量から単語単位の特徴量に変換してやる必要があります。先頭サブワードを取ったり平均を取ったりしますが、今回は先頭サブワードを単語の特徴量とみなしたいと思います。

実装は色々考えられますが、プーリングのための行列を用意して、BERTの出力にかけてやることで単語単位の特徴量に変換することにします。具体的には、以下のような計算で任意のベクトルをとってきます。行列をうまく設計すれば、平均など色々な変換も同様の計算でできるようになります。


\begin{pmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{pmatrix}

\begin{pmatrix}
x_0 \\
x_1 \\
x_2
\end{pmatrix}

=

\begin{pmatrix}
x_0 \\
x_2
\end{pmatrix}

実装としては、torch.bmm(pooling_matrix, sequence_output)のように積をとるだけです。pooling_matrixを作るのは少し面倒ですがcreate_pooler_matrixを参考にしてください。

学習

先程作ったモデルを使って学習していきます。学習の流れは以下の通りです

  1. 勾配の初期化(optimizer.zero_grad()
  2. lossの計算(output = model(input_x, labels=input_y, attention_mask=mask)
  3. 誤差の逆伝播(loss.backward()
  4. パラメータの更新(optimizer.step()

基本的に、このサイクルをepoch* batch分繰り返します。 以下は学習コードから抜粋(と少し改変)したものです。

import torch
import torch.optim as optim
from torch.utils.data import DataLoader
from torch.nn.utils.rnn import pad_sequence

optimizer = optim.AdamW(model.parameters(), lr=1e-5)
train_dataloader = DataLoader(train_dataset, batch_size=args.bsz, collate_fn=ner_collate_fn, shuffle=True)
losses = []
for e in range(args.epoch):
    total_loss = 0
    for step, inputs in enumerate(train_dataloader):
        input_ids = inputs["tokens"]
        word_idxs = inputs["word_idxs"]
        labels = inputs["labels"]

        labels = [pad_sequence([torch.tensor(l) for l in label], padding_value=-1, batch_first=True).to(device)
                for label in labels]

        input_ids = pad_sequence([torch.tensor(t) for t in input_ids], padding_value=0, batch_first=True).to(device)
        attention_mask = input_ids > 0
        pooling_matrix = create_pooler_matrix(input_ids, word_idxs, pool_type="head").to(device)

        outputs = model(
            input_ids=input_ids,
            attention_mask=attention_mask,
            word_idxs=word_idxs,
            labels=labels,
            pooling_matrix=pooling_matrix)

        loss = outputs[0]
        loss.backward()

        total_loss += loss.item()
        optimizer.step()
        optimizer.zero_grad()

今回はBERTを使っているため、attention_maskが入力として増えています。これは、パディングに使用されたトークン(ここでは[PAD] )にアテンションがかからないように設定します。

実際のコードでは、過学習を防ぐためにearly stoppingを入れたりしています。

予測

学習したモデルを使って、予測していきます。

基本的にはモデルの出力でlogits(softmaxする前の値)が出てくるので、最も大きい値を持つラベルでデコードします。ただ、系列ラベリングでの固有表現抽出の場合、次にとりうるタグが前のタグによって制限されることがあります。例えばOの次にIが来ることはタグの設計上あり得ません。 そのため、Viterbiアルゴリズムと呼ばれるアルゴリズムで制約を考慮しつつタグの予測を行います。

今回はOからIへの遷移(0から2)の場合について、Iに対応するlogitsをとても小さい値にすることでIが選ばれないようにします。

    def viterbi(self, logits, penalty=float('inf')):
        num_tags = 3

        # 0: O, 1: B, 2: I
        penalties = torch.zeros((num_tags, num_tags))
        penalties[0][2] = penalty

        all_preds = []
        for logit in logits:
            pred_tags = [0]
            for l in logit:
                transit_penalty = penalties[pred_tags[-1]]
                l = l - transit_penalty
                tag = torch.argmax(l, dim=-1)
                pred_tags.append(tag.item())
            all_preds.append(pred_tags[1:])
        return all_preds

    def predict(
        self,
        input_ids=None,
        attention_mask=None,
        word_idxs=None,
        pooling_matrix=None,
    ):
        logits = self.forward(
            input_ids=input_ids,
            attention_mask=attention_mask,
            pooling_matrix=pooling_matrix)[0]
        labels = [self.viterbi(logit.detach().cpu()) for logit in logits]

        truncated_labels = [[label[:len(word_idx)-1] for label, word_idx in zip(attr_labels, word_idxs)] for attr_labels in labels]

        return truncated_labels

それを踏まえながら、データをモデルに流してラベルを予測していきます。torch.no_grad()をすると、自動勾配をオフにできるので、計算時間とメモリの節約になります。

model.eval()
dataloader = DataLoader(dataset, batch_size=8, collate_fn=ner_collate_fn)

with torch.no_grad():
    for step, inputs in enumerate(dataloader):
        input_ids = inputs["tokens"]
        word_idxs = inputs["word_idxs"]

        input_ids = pad_sequence([torch.tensor(t) for t in input_ids], padding_value=0, batch_first=True).to(device)
        attention_mask = input_ids > 0

        preds = model.predict(
            input_ids=input_ids,
            attention_mask=attention_mask,
            word_idxs=word_idxs,
        )

提出フォーマットへの変換

森羅プロジェクトでは、IOBタグではなく配布データのアノテーション形式に合わせたJSON形式で提出する必要があります。テキストのオフセットや行番号、記事番号などをつけないといけないので少し面倒です。

自分で実装するのが面倒な人はこちらを使ってください。ShinraDatasetで配布形式からIOB形式(ner_inputs)、IOB形式から配布形式(add_nes_from_iob)への変換ができます。予測のサンプルコードも参照するとわかりやすいかもしれません。 ただ、入出力が今回の問題設定用なので、他の設定でやる方は自分で書いたほうが早いかもしれません.

改善点

  • 簡単のため、入れ子に関してはmulti-label分類で解いてしましました。他にもスパンの分類問題として解いたり[4]できます。
  • 前後のラベルとの関係も考慮するためにCRFを使うことができます。AllenNLPで比較的簡単に実装できます。
  • 属性は記事との関係性により定義されています。例えば「松山市」というWikipedia記事の「人口」という属性を取ってくる場合、四国全体の人口はとってきたくないわけです。そのため、うまく記事タイトルなどを考慮してタスクを解く必要があります。
  • NERによるアプローチ以外にも、機械読解によるアプローチも提案されています。こちらの方が自然な問題設定かも?[5]

おわりに

今回は、森羅プロジェクトの日本語構造化タスクを使って、日本語Wikipediaから属性抽出しました。日本語構造化タスクではリーダーボードも開催されていますので、ぜひ参加して見て下さい!手軽に情報抽出モデルを試せる良いタスクだと思います。

参考文献

[1] Ma, Xuezhe, and Eduard Hovy. 2016. “End-to-End Sequence Labeling via Bi-Directional LSTM-CNNs-CRF.” In Proceedings of the ACL, 1064–74.

[2] Devlin J, Chang M-W, Lee K, Toutanova K. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the NAACL-HLT; 2019:4171-4186.

[3] Jana Strakova´ and Milan Straka and Jan Hajic. 2019. Neural Architectures for Nested NER through Linearization. In Proceedings of the ACL, 5326–5331.

[4] Congying Xia, Chenwei Zhang, Tao Yang, Yaliang Li, Nan Du, Xian Wu, Wei Fan, Fenglong Ma, and Philip Yu. 2019. Multi-grained named entity recognition. In Proceedings of ACL, pages 1430–1440.

[5] 石井 愛, 機械読解によるWikipediaからの情報抽出. In the proceedings of the 言語処理学会第25回年次大会.# BERTでwikipediaからNER

論文まとめ① [ClinicalNLP]

論文まとめ

概要

英語以外の言語でのClinical NLPサーベイ論文

  1. NLPシステムの構築
  2. 英語のNLPシステムの言語拡張
  3. アプリケーション

の3つの観点から研究を俯瞰している.

内容

日本語についての研究,個人的に面白そうな研究を列挙します.

英語のNLPシステムの言語拡張

MetaMapなどの英語NLPシステムの言語拡張を目指した研究

cTakesのドイツ語拡張
Extraction of UMLS® Concepts Using Apache cTAKES™ for German Language. - PubMed - NCBI

アプリケーション

上述のNLPシステムを使ったclinicalなアプリケーションの構築を目指した研究

エピソード記憶の分析,自動分類
Unraveling the linguistic nature of specific autobiographical memories using a computerized classification algorithm. - PubMed - NCBI

議論

英語以外の言語でのClinical NLPでは,主に「英語ですでにあるツールを自国語でも作りたい」というモチベーションで研究されているように感じました.
UMLSの翻訳などがされてない言語では,そもそも医療概念を定義・抽出すること自体が難しく,リソースの自動構築や英語リソースへのリンクなども行われているようです.

AtCoder:ABC140振り返り

AtCoderのABC140に参加したのでその振り返りです.今回はなんとかDまで解けたという感じで,D問題の実装にてこずりました...ただ,一応全部一発で通せたので,そこはよかったです.

A問題

f:id:kuroneko1259:20190908134548p:plain

3桁のうち,それぞれの桁が1からNまでN個の可能性があるので,単純に{N^3}です.

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    cout << pow(N, 3) << endl;
    return 0;
}

B問題

f:id:kuroneko1259:20190908134859p:plain

i番目の料理{A_i}を食べた時の満足度{B_{A_i}}{A_{i+1} = A_i + 1}なら追加の満足度{C_{A_i}}を足して行きます.これも複雑なアルゴリズムは必要なく,言われた通りに実装すれば良い問題でした.ここ1ヶ月くらいABCに参加した感じでは,基本B問題までは素直に実装すれば良い感じですね.

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    vector<int> a(N), b(N), c(N-1);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < N; i++) cin >> b[i];
    for (int i = 0; i < N-1; i++) cin >> c[i];

    int res = 0;
    for (int i = 0; i < N; i++) {
        res += b[a[i]];
        if (i < N-1 && a[i+1] == a[i] + 1) res += c[a[i]];
    }

    cout << res << endl;
    return 0;
}

C問題

f:id:kuroneko1259:20190908135333p:plain
数列{A_i}に関する2項間の関係{B_i}がわかっていて,{\sum A_i}の最大値を求める問題でした.{B_i \geq \max (A_i, A_{i+1})}を読み替えると{A_i \leq min(B_{i-1}, B_i)}になります.{A_i}をそれぞれ最大にするには,{A_i = min(B_{i-1}, B_i)}にすればよいことになります.ただし,{A_1}{A_n}{B_0, B_n}がないので,{A_1 = B_1}{A_n = B_{n-1}}になります.

こういうところで{B_0, B_n = inf}(infは十分大きい数)とおければ場合分けなしでかっこよくコードが書けるんですが,なかなかとっさに思いつかないですね...

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    vector<ll> b(N-1);
    for (int i = 0; i < N-1; i++) cin >> b[i];

    ll res = b[0];
    for (int i = 0; i < N - 2; i++) {
        if (b[i] <= b[i+1]) res += b[i];
        else res += b[i+1];
    }
    res += b[N-2];
    cout << res << endl;
}

D問題

f:id:kuroneko1259:20190908140424p:plain
一応ACになりましたが,無理やり通した感...前にもLとRの文字列の問題がありましたが,規則はわかりますが実装が難しいです...

この問題では

  • LRLLを反転するとRRLR
  • LRLRを反転するとLRLR

みたいな感じで,両端以外は反転しても幸福な人は増えません.しかも両端がLRRLみたいに揃っていないと,ひっくり返しても幸福な人は増えないことになります(LLRRをひっくり返してもLLRR).

なので,基本的な方針としてLLRRLLのRのように別の文字に囲まれている文字を一気にひっくり返すことにしました.この操作1回ずつに幸福な人は2人(両端の人)増えることになります.また,両端を別の文字で囲まれて,同じのみで構成される部分列の個数はLとRで1個違いになります.

ここまで考えて,両端の文字が揃っていない場合にうまくいかない(最後の一回は1人しか幸福な人が増えない)ことに気づいて,慌てて場合分けを増やそうとして,あってるのかわからないけどサンプルは全部通ったし出しちゃえ!でACでした.

今思えば,両端が揃っていなくても最後の1回しか処理は変わらない +各操作で2人ずつ増えていくので,最初の幸福な人の人数をfとすると{f + 2 \times K}が幸福な人の最大値N-1以上になるかどうかで場合分けすれば良いだけの話でした.つまり,K回の操作すべてで2人増えることにしても差が生じるのは最後の操作だけであり,その場合は幸福な人の最大値を超えてしまうので最大値を出力すればよかったです.うまく言えませんが...

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    int N, K; cin >> N >> K;
    string s; cin >> s;

    int res = 0;
    for (int i = 1; i < int(s.size()); i++) {
        if (s[i-1] == s[i]) res++;
    }

    vector<int> R, L;
    int idx = 0, r=0, l=0;
    while (idx != N && s[idx] != 'R') idx++;
    while (idx != N) {
        while (idx != N && s[idx] != 'L') idx++;
        while (idx != N && s[idx] != 'R') idx++;
        if (idx != N) l++;
    }
    idx = 0;
    while (idx != N && s[idx] != 'R') idx++;
    while (idx != N) {
        while (idx != N && s[idx] != 'R') idx++;
        while (idx != N && s[idx] != 'L') idx++;
        if (idx != N) r++;
    }

    if (r==0 || l==0) {
        cout << N - 1 << endl;
        return 0;
    }
    int sr=0, sl=0;
    if (s[0] == 'L') sl++;
    else sr++;
    if (s[int(s.size())-1] == 'L') sl++;
    else sr++;

    if (K >= min(r+sr, l+sl)) {
        cout << N-1 << endl;
        return 0;
    } else if (K >= min(r, l)){
        cout << res + min(r, l)*2 << endl;
    } else {
        cout << res + K*2 << endl;
    }
    return 0;
}

まとめ

今回はE問題にまわす時間はなかったです.見た感じE問題は時間があっても解けなかったと思いますが...D問題のような問題はなんの情報を保持しておけば良いのか(LとR,RとLの変わり目を分けるのかどうか,とか),それをどう処理すれば良いのか難しいです.

AtCoder:ABC139の振り返り

ABC139に参加したのでその振り返りです.今回はE問題まで解くことができました!ゴリゴリの競プロ的な問題ではなかったのがよかったのかな??と思います.まだまだ典型的なアルゴリズムや基本的な発想が身についていないので,今回のD問題やE問題のような数学的な問題の方が解きやすく感じます.

A問題

f:id:kuroneko1259:20190903091254p:plain
単純に3文字を比較するだけでした.

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    string s, t; cin >> s >> t;
    int res = 0;
    if (s[0] == t[0]) res++;
    if (s[1] == t[1]) res++;
    if (s[2] == t[2]) res++;
    cout << res << endl;
}

B問題

f:id:kuroneko1259:20190903091416p:plain

最初,1口のときを考えていなくてWAが出てしまいました.もったいない!
場合分けしない方が良いと思いますが,へんに書き直すより場合分けで追加した方が良いかなと思ったのでこんな感じのコードになりました.

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int a, b; cin >> a >> b;
    if (b == 1) {
        cout << 0 << endl;
        return 0;
    }
    int tap = a, res = 1;

    while (tap < b) {
        tap += a - 1;
        res++;
    }
    cout << res << endl;
    return 0;
}

C問題

f:id:kuroneko1259:20190903091843p:plain

一つ右の階段での最大移動回数がわかれば,今の最大移動回数がわかるので(高さが右以上であれば+1,右より下であれば0)後ろからDPみたいな感じで回していけばO(N),その中で最大のものを探索してもO(N)だと思ってその方針で行きました.比較的すんなり解けて,この問題終わった時点で15分くらいだったので,次以降の問題につながったと思います.

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    vector<int> v(N);
    for (int i = 0; i < N; i++) cin >> v[i];

    int dp[N];
    for (int i = 0; i < N; i++) dp[i] = 0;

    for (int i = N-2; i >= 0; i--) {
        if (v[i] >= v[i+1]) dp[i] = dp[i+1] + 1;
    }
    
    int res = 0;
    for (int i = 0; i < N; i++) {
        if (dp[i] > res) res = dp[i];
    }
    
    cout << res << endl;
}

D問題

f:id:kuroneko1259:20190903092335p:plain

もはや数学...?競プロはこんな数学の問題もでるんですね...コードが最終的な計算式かくだけで謎の罪悪感に包まれました.

{\sum_{i}^n i \ mod\ P_i}を求めたいのですが,{i \ mod\ P_i}はi以下であり{P_i}より小さいので,{n\ mod\ P_n}はnよりだいぶ小さい値になるなーというのを出発点にして考えました.そうなるとできるだけ{i = n-1}以下の組み合わせについて最大化したくて,ひとつずつ考えていくと例えば{n-1\ mod\ P_{n-1}}を最大化するのは{P_{n-1}=n}{n-1\ mod\ P_{n-1} = n-1}になります.このように後ろから見ていくとiより1大きい数を{P_i}として選べば,{\sum_i^{n-1} i = \frac{n(n-1)}{2}}で最大化されるのかな??と思って実装したらACでした.

正直厳密な証明に裏付けされた答えじゃなくて,直感に基づく実装だったので実力かと言われると微妙ですが...

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    ll N; cin >> N;
    cout << (N-1) * N / ll(2)<< endl;
}

E問題

f:id:kuroneko1259:20190903093430p:plain
Dまでで30分くらいだったので,E問題も解いて見たら意外と解けました.

  1. 各選手の試合順が決まっているので,各試合における最短日数は一意にきまりそう(本当にそうなのかは不明)
  2. しかも各試合の最短日数は,出場選手が前の試合を行った日にのみ依存しそう(その前にしなければならない試合があれば,その試合の最短日数が決まるまで待てば良い)
  3. あれ??でもそれだとforで各選手を回して,その外側にwhile回さないといけない??時間足りる??
  4. あ,でも最短日の更新はたかだか試合数分しか起こらないから大丈夫かな?更新がなくなってwhile抜ければ問題なさそう

みたいな思考回路でDPで解きました.実装にもわりと時間がかかって,入力は列が試合順のインデックスにしてるのに,dpは選手のインデックスでこんがらがったりしてました.

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int dp[1005][1005];

int main() {
    int N; cin >> N;
    int A[N][N-1];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N-1; j++) {
            cin >> A[i][j];
            A[i][j]--;
        }
    }
    int next[N];
    for (int i = 0; i < N; i++) next[i] = 0;

    bool flag = false;

    while (!flag) {
        for (int i = 0; i < N; i++) {
            int idx = A[i][next[i]];
            if (next[i] >= N-1 || next[idx] >= N-1) continue;
            int prev_i, prev_idx;
            if (next[i] > 0) prev_i = A[i][next[i]-1]+1;
            else prev_i = 0;

            if (next[idx] > 0) prev_idx = A[idx][next[idx]-1]+1;
            else prev_idx = 0;

            if (A[idx][next[idx]] == i) {
                dp[i+1][idx+1] = dp[idx+1][i+1] = max(dp[i+1][prev_i], dp[idx+1][prev_idx]) + 1;
                next[i]++;
                next[idx]++;
                flag = true;
            }
        }
        flag = !flag;
    }

    int res = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i != j && dp[i+1][j+1] == 0) {
                cout << -1 << endl;
                return 0;
            } else if (i != j) {
                res = max(res, dp[i+1][j+1]);
            }
        }
    }

    cout << res << endl;
    return 0;
}

まとめ

今回は初めてE問題まで解けてかなりうれしかったです.レートもかなり上がって茶色の上の方までいきました.最初の10回までは補正がかかるらしいので(今6回目),とりあえずレートを気にせず10回参加することを目標に頑張りたいと思います.

ABC137振り返り

ABC137の振り返りをしていきます.今回はC問題も解けず,,,まだまだ使える典型の種類が足りてないなとおもいます...

A問題

f:id:kuroneko1259:20190811140641p:plain

これはさすがにそのまま書くだけでした.特に何もないです.

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int A, B; cin >> A >> B;
    int p = A + B, s = A - B, m = A * B;

    cout << max(p, max(s, m)) << endl;
    return 0;
}

B問題

f:id:kuroneko1259:20190811140811p:plain

制約から範囲がはみ出す可能性はないので,これも素直に書きました.

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

typedef long long ll;

int main() {
    int K, X; cin >> K >> X;

    for (int i = X - K + 1; i < X + K; i++) {
        cout << i;
        if (i != X + K - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

C問題

f:id:kuroneko1259:20190811141023p:plain

解けなかったです...

とりあえず,アナグラムを判定する部分と組み合わせを考える部分で分けて考えました.アナグラムの判定は,あらかじめ文字列をソートしておくと定数時間で実行できるので,問題なかったです.

アナグラムになっている文字列をグループ分けしてあげて,同じグループに{n \geq 2}個の文字列があるときに,{{}_n C_2}の総和を出せばいいことに終了10分前くらいに気づきました.

グループ分けは,文字列の配列をソートしてO(NlogN),前から順にO(N)でみていけばよかったので,あとは{{}_n C_2}の総和をとって提出!!したのですが,最後のテストケースだけWAでした.後から考えてみると,組み合わせを{1e9 + 7}で割った余りを出してしまっていたのでそれが原因だと思います.

アナグラムである文字列の個数の数え方も,単純に足して行って,違う文字列がでてきたらリセットでよかったんですが,配列やらフラグやらをこねくり回してわかりにくくなってます.

解説によれば,同じ文字列の個数を数える際は,ハッシュを使うと高速にできるみたいです(検索も追加も平均O(1) ??全てのデータが衝突したとしてO(N)).C++ではunordered_mapで使えます.

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    vector<string> s(N);

    for (int i = 0; i < N; i++) {
        string st; cin >> st;
        sort(st.begin(), st.end());
        s[i] = st;
    }

    sort(s.begin(), s.end());

    bool prev = false;
    vector<int> res;
    for (int i = 0; i < N-1; i++) {
        bool flag = true;
        for (int j = 0; j < 10; j++) {
            if (s[i][j] != s[i+1][j]) flag = false;
        }
        if (flag) {
            if (prev) {
                res[int(res.size())-1] += 1;
            } else {
                res.push_back(2);
            }

            prev = true;
        } else {
            prev = false;
        }
    }
    ll ans = 0;
    for (int i = 0; i < res.size(); i++) {
        ans += ll(res[i]) * (res[i] - 1) / 2;
    }

    cout << ans << endl;
    return 0;
}

D問題

f:id:kuroneko1259:20190811143619p:plain

C問題が解けそうで解けなかったのでこっちも目を通しましたが,こっちも解けなかったです...

時間がたつにつれてできる仕事の選択肢は減っていく(制約が厳しくなっていく)ので,こういう場合は制約が厳しい方から考えるのが定石みたいです.例えば時刻tのときを考えると,選べる仕事はM - t以内に報酬が振り込まれるものになるので,その中で報酬が最大のバイトを選べば良いみたいです.

これに気づいても,愚直に最大値を調べるとO(N^2)かかると思うのですが,毎回選ぶのは最大値なのでpriority_queueを使うと,要素の追加がO(N),最大値を取り出すのがO(M),それぞれの操作はO(logN)かかるのでO((M+N)logN)で計算できます.

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <queue>

using namespace std;

typedef long long ll;

int main() {
    int N, M; cin >> N >> M;
    vector<pair<int, int>> v(N);

    for (int i = 0; i < N; i++) {
        int a, b; cin >> a >> b;
        v[i].first = a;
        v[i].second = b;
    }
    sort(v.begin(), v.end());

    priority_queue<int> q;

    int idx = 0;
    int ans = 0;
    for (int t = 0; t <= M; t++) {
        while (idx != N && v[idx].first <= t) {
            q.push(v[idx].second);
            idx++;
        }

        if (!q.empty()) {
            ans += q.top();
            q.pop();
        }
    }

    cout << ans << endl;
    return 0;
}

まとめ

まずは最低でもCまでは確実に解けるようにしていきたいです