読者です 読者をやめる 読者になる 読者になる

北野坂備忘録

主にインストールやプログラミングのメモを載せています。

言語処理100本ノック 2015年版 (55~59)

55. 固有表現抽出

入力文中の人名をすべて抜き出せ.

Named Entity Recognition は直訳すると「名前符号認識」ですが、現在は一般的に「固有表現抽出」と呼ばれています。
今回はこのNERタグを用います。

#!/usr/bin/env python

import codecs
import copy
import re

fin = codecs.open('nlp.txt.out', 'r', 'utf_8')
src = []
token = {}
word = ""

if __name__ == "__main__":
  n = 0 
  for line in fin:
    if n == 50:
      break
    word = re.findall(r'<word>.*</word>',line)
    NER = re.findall(r'<NER>PERSON</NER>',line)
    if word:
      token['word']= word[0][6:-7]
    if NER:
      src.append(copy.deepcopy(token))
      token = {}
      n = n + 1

  for tokenx in src:
    print(tokenx['word'])
    
結果
Alan
Turing
Joseph
Weizenbaum
MARGIE
Schank
Wilensky
Meehan
Lehnert
Carbonell
Lehnert
Jabberwacky
Moore

56. 共参照解析

Stanford Core NLPの共参照解析の結果に基づき,文中の参照表現(mention)を代表参照表現(representative mention)に置換せよ.ただし,置換するときは,「代表参照表現(参照表現)」のように,元の参照表現が分かるように配慮せよ.

共参照解析(Coreference Analysis)とは自然言語処理のうちの一つで、文章中に出てくる単語が同じ実体を指していることを解析する処理です。「オバマは~。大統領は~。」という文章があったとき、人間は「オバマ」と「大統領」が同一人物であることが(だいたい)分かりますが、機械は共参照解析しないと分かりません。
Stanford Core NLP では "-annotators dcoref" と指示すれば処理してくれます。
で、結論から言いますと 非常にうまくいっていない。

    <coreference>
      <coreference>
        <mention representative="true">
          <sentence>1</sentence>
          <start>7</start>
          <end>16</end>
          <head>12</head>
          <text>the free encyclopedia Natural language processing -LRB- NLP -RRB-</text>
        </mention>
        <mention>
          <sentence>1</sentence>
          <start>17</start>
          <end>22</end>
          <head>18</head>
          <text>a field of computer science</text>
        </mention>

しょっぱなからこんな感じです。

上では
the free encyclopedia Natural language processing (NLP)

a field of computer science
を代表しているとなっています。2行の文章をまとめて処理するなど、切り出しすらうまくいっていません。

このあたり他の挑戦者もおかしいと感じているようで、1センテンスずつ処理するなど工夫を凝らしています。
処理に結構な時間がかかったのもこの共参照解析が原因ではないでしょうか。
おもしろいので今回はこのまま使ってみたいと思います。
ただ、これをそのまま使おうと思うと、文構造をきちんと取り込まなくてはいけません。
JSONの設問はあるけれどもxmlのパーシングって設問に入っていない。もしかするとこの問題がそうなのか。それとも53の時点からパーシングすべきだったのか。
泥縄式ですが、今からパーシングを始めます。
今回は一番オーソドックスな ElementTree を用います。

方針としては、 sentence カウンターと token カウンターを回し、該当個所にくれば"「","representative mention","("を表示、終了箇所に来れば")」"を表示させるというものです。
必要なのは
・開始番号[sentence][token]["representative mention"]
・終了番号[sentence][token]["\""]
となります。

#!/usr/bin/env python

import re
from xml.etree import ElementTree

tree = ElementTree.parse("nlp.txt.out") # ElementTreeでパーシング
root = tree.getroot() 

src = []
sentences = []
coreferences = []
mentions = []
tags = {}
tokens = []
referenceslist = []

if __name__ == "__main__":
#トークンを収集
  for sentence in root[0][0]:
    for token in sentence[0]:
      sentences.append(token[0].text)
    src.append(sentences)
    sentences = []

#coreference情報を収集
  for coreference in root[0][1]:
    for mention in coreference:
      b = mention.attrib
      if b.keys():
        tags["representative"]=b['representative']
      for m in mention:
        tags[m.tag]=m.text
      mentions.append(tags)
      tags = {} 
    coreferences.append(mentions)
    mentions = []

#置換のため代表参照表現等を準備     
  for coreferencex in coreferences:
    for mentionx in coreferencex:
      if "representative" in mentionx:
        representative_text = mentionx["text"]
        representative_text = re.sub(r'-LRB- ',r'(',representative_text)
        representative_text = re.sub(r' -RRB-',r')',representative_text)
        representative_text = "「"+representative_text+"("
      else:
        referenceslist.append([mentionx["sentence"],mentionx["start"],representative_text])
        referenceslist.append([mentionx["sentence"],mentionx["end"],")」"])

#文中に代表参照表現等を差し込んでいく
  n = 1
  m = 1
  for sentence in src:
    for tokens in sentence:
      for x in referenceslist:
        if int(x[0]) == n and int(x[1]) == m:
          print(x[2],end="")
      tokens = re.sub(r'-LRB-',r'(',tokens)
      tokens = re.sub(r'-RRB-',r')',tokens)
      print(tokens,end=" ")
      m += 1
    print("")
    m = 1
    n += 1

結果を最初のほうだけ表示しておきます。

Natural language processing From Wikipedia , the free encyclopedia Natural language processing ( NLP ) is 「the free encyclopedia Natural language processing (NLP)(a field of computer science )」, artificial intelligence , and linguistics concerned with the interactions between computers and human ( natural ) languages .
As such , NLP is related to the area of humani-computer interaction .
Many challenges in NLP involve natural language understanding , that is , enabling 「computers(computers )」to derive meaning from human or natural language input , and others involve natural language generation .
History The history of NLP generally starts in the 1950s , although work can be found from earlier periods .
In 1950 , Alan Turing published an article titled `` Computing Machinery and Intelligence '' which proposed what is now called the 「Alan Turing(Turing )」test as a criterion of intelligence .
The Georgetown experiment in 1954 involved fully automatic translation of more than sixty Russian sentences into English .
The authors claimed that within three or five years , 「a solved problem(machine translation )」would be a solved problem .
(略)

Turing が Alan Turing と同定されいるのはいいのですが、さきほどの a field of computer science もおかしいし、machine translation とa solved problem で a solved problem のほうが representative であると評価されています。
 性能が良いとされている Stanford Core NLP であっても、適切な前処理をしなければ結果はこの程度となります。

57. 係り受け解析

Stanford Core NLP係り受け解析の結果(collapsed-dependencies)を有向グラフとして可視化せよ.可視化には,係り受け木をDOT言語に変換し,Graphvizを用いるとよい.また,Pythonから有向グラフを直接的に可視化するには,pydotを使うとよい.

dependencies のタイプは以下の3つありますが、このうち'collapsed-dependencies'を使え、というのが指示です。
dependencies {'type': 'basic-dependencies'}
dependencies {'type': 'collapsed-dependencies'}
dependencies {'type': 'collapsed-ccprocessed-dependencies'}

で、英語の係り受けの恐ろしいところは、日本語が右から左へと行くのに対し、左や右へと自在に動く点です。
ただ、core NLPで処理された xml 上では governor と dependent に分けて処理してくれているので苦労はありません。
日本語は根(root)になる動詞が最後に来ますが、英語は動詞が途中で出てきます。
あと、日本語では根に向かって矢印を描きますが、英語の場合は根となる動詞を一番上に置いて矢印が始まることが多い。もしくはrootから根となる動詞に矢印が描かれてそこから始まる。逆方向もたまに見かけますが。今回はrootスタートとします。
あと、core NLPは"."や","も容赦なく係り受け解析していますが、これをpydotに放り込むとおかしくなるので削除します。

#!/usr/bin/env python

import re
from xml.etree import ElementTree
import pydot
import sys

tree = ElementTree.parse("nlp.txt.out") 
root = tree.getroot() 

sentences = []
dependencies = []

if __name__ == "__main__":
  param = sys.argv 

  for sentence in root[0][0]:
    for dep in sentence[3]:
      if dep[1].text != "." and dep[1].text != ",":
        dependencies.append([dep[0].text,dep[1].text])
    sentences.append(dependencies)
    dependencies = []

  if len(param)>1:
    stringn = int(param[1])
  else:
    stringn = 1

  edges = sentences[stringn]
  print(edges)

  g=pydot.graph_from_edges(edges, directed=True)
  g.write_jpeg('nlp.jpg', prog='dot')

結果の一例は以下のとおり。
f:id:kenichia:20160215192711j:plain

58. タプルの抽出

Stanford Core NLP係り受け解析の結果(collapsed-dependencies)に基づき,「主語 述語 目的語」の組をタブ区切り形式で出力せよ.ただし,主語,述語,目的語の定義は以下を参考にせよ.

述語: nsubj関係とdobj関係の子(dependant)を持つ単語
主語: 述語からnsubj関係にある子(dependent)
目的語: 述語からdobj関係にある子(dependent)

ようはこんな記述セットを探してこいということです。

         <dep type="nsubj">
            <governor idx="13">provided</governor>
            <dependent idx="11">ELIZA</dependent>

          <dep type="dobj">
            <governor idx="13">provided</governor>
            <dependent idx="17">interaction</dependent>

 一つのセンテンスにいくつも入っている場合があるので注意。

#!/usr/bin/env python

import copy
import re
from xml.etree import ElementTree
import sys

tree = ElementTree.parse("nlp.txt.out")
root = tree.getroot() 

sentences = []
dependencies = []
depnsubj = []
depdobj = []

if __name__ == "__main__":
  param = sys.argv 

# nsubj と dobj のリストを作成
  for sentence in root[0][0]:
    for dep in sentence[3]:
      deptype = dep.attrib
      if deptype["type"] == "nsubj":
        gidx = dep[0].attrib
        didx = dep[1].attrib
        dependencies.append([deptype["type"],gidx["idx"],dep[0].text,didx["idx"],dep[1].text])
      if deptype["type"] == "dobj":
        gidx = dep[0].attrib
        didx = dep[1].attrib
        dependencies.append([deptype["type"],gidx["idx"],dep[0].text,didx["idx"],dep[1].text])
    sentences.append(dependencies)
    dependencies = []

#同一センテンスの中で、nsubjとdobjの idx 番号が一致するものを探索
  for dependence in sentences:
    for dep in dependence:
      if dep[0] == "nsubj":
        nsubj = dep[1]
        for dobj in dependence:
          if dobj[0] == "dobj" and dobj[1] == nsubj:
            print(dep[4],"\t",dep[2],end="\t")
            print(dobj[4])
            nsubj = 0
結果
understanding 	 enabling	computers
others 	 involve	generation
Turing 	 published	article
experiment 	 involved	translation
ELIZA 	 provided	interaction
patient 	 exceeded	base
ELIZA 	 provide	response
which 	 structured	information
underpinnings 	 discouraged	sort
(略)

59. S式の解析

Stanford Core NLP句構造解析の結果(S式)を読み込み,文中のすべての名詞句(NP)を表示せよ.入れ子になっている名詞句もすべて表示すること.

S式といえば lisp ですがあまりそこには踏み込みたくありません。構文木のテキスト表現に括弧()を使うのがS式で、たいていの人間は Python のようなインデント表現のほうが理解しやすい。
 具体例を上げた方が分かりやすいでしょう。今回のStanford Core NLPの結果で言うとコレです。

       <parse>(ROOT (S (S (NP (NP (JJ Many) (NNS challenges)) (PP (IN in) (NP (NN NLP)))) (VP (VBP involve) (S (NP (NP (JJ natural) (NN language) (NN understanding)) (, ,) (SBAR (WHNP (WDT that)) (S (VP (VBZ is)))) (, ,)) (VP (VBG enabling) (NP (NNS computers)) (S (VP (TO to) (VP (VB derive) (NP (NN meaning)) (PP (IN from) (NP (ADJP (JJ human) (CC or) (JJ natural)) (NN language) (NN input)))))))))) (, ,) (CC and) (S (NP (NNS others)) (VP (VBP involve) (NP (JJ natural) (NN language) (NN generation)))) (. .))) </parse>

 残念ながらPythonでS式を取り扱う標準的な方法はありません。自分でパーサを作るか、借りてくるかです。
 ただ、 NP を表示させるだけならパーシングまではしないでなんとかできるのではないか。(「なんとかインチキできんのか」 by 大泉父)
 やってみましょう。
 NP の後の括弧の数を数えます。左括弧 であれば +1, 右括弧 であれば -1 、最終的に -1 になったらそこで終わりです。
 あとは NP を発見すると自分より後のトークンを一旦保存すればよい。

#!/usr/bin/env python

import re
from xml.etree import ElementTree

tree = ElementTree.parse("nlp.txt.out") 
root = tree.getroot() 

sentences = []

if __name__ == "__main__":

#<parse>情報を収集
  for sentence in root[0][0]:
    perse = re.sub(r'\)',r' )',sentence[1].text)
    perse = re.sub(r'\(',r'( ',perse)
    tokens = re.split(" ",perse)
    sentences.append(tokens)

  n=0
  RBcounter = 0
  for perse in sentences:
    for token in perse:
      NPtokenlist = []
      if token == "NP":
        NPlist = perse[n+1:] #NP以降のトークンを一旦保存
        for NPtoken in NPlist: #括弧カウンター
          if NPtoken == "(":
            RBcounter += 1
          if NPtoken == ")":
            RBcounter -= 1
          if RBcounter == -1:
            print("")
            break
          NPtokenlist.append(NPtoken)

#ここから描画モード
        LRBflag = 0
        for NPtoken  in NPtokenlist: #左括弧を発見するとタグごと飛ばす
          if NPtoken == ")":
            continue
          if NPtoken == "(":
            LRBflag = 1
            continue
          if NPtoken != "(" and LRBflag == 1:
            LRBflag -= 1
          else: # LRB と RRB を括弧に変換
            if NPtoken == "-LRB-":
              print("(",end=" ")
            elif NPtoken == "-RRB-":
              print(")",end=" ")
            else:
              print(NPtoken,end=" ")        
        RBcounter = 0 
      n += 1
    print("")
    n = 0
結果
Natural language processing
Wikipedia
the free encyclopedia Natural language processing ( NLP )
the free encyclopedia Natural language processing
NLP
a field of computer science , artificial intelligence , and linguistics concerned with the interactions between computers and human ( natural ) languages
a field of computer science
a field
computer science
artificial intelligence
linguistics concerned with the interactions between computers and human ( natural ) languages
linguistics
the interactions between computers and human ( natural ) languages
the interactions
computers and human ( natural ) languages
computers
human ( natural ) languages
(略)

 指示どおり入れ子になっている名詞句もいちいち表示しているためかなりくどくなっています。ただ、共参照解析より遥かに精度が高い。

 うーん。この第6章よりも第5章のほうが難しかったような気がしますね。