二部グラフの最大マッチング問題｜Python実装
参考にした実装
改良点
setのエラーの回避
setでは .items() が使えないので回避した
条件分岐の追加
パッケージの都合で(3, 9)の組み合わせが(9,3)の順で出力される場合が考慮されていなかったので修正した
Python実装
import networkx as nx from networkx.algorithms import bipartite import numpy as np import itertools import matplotlib.pyplot as plt group1 = range(5) group2 = range(5,10) node_color = ["b"] * 5 node_color.extend(["r"] * 5) g = nx.Graph() g.add_nodes_from(group1, bipartite=1) g.add_nodes_from(group2, bipartite=0) for (i,j) in itertools.product(group1, group2): val = np.random.randint(1, 10) g.add_edge(i, j, weight=val) A,B = bipartite.sets(g) pos = dict() pos.update((n,(1,i)) for i,n in enumerate(A)) pos.update((n,(2,i)) for i,n in enumerate(B)) edge_width = [ d['weight']*0.3 for (u,v,d) in g.edges(data=True)] nx.draw_networkx(g, pos, node_color=node_color) nx.draw_networkx_edges(g, pos, width=edge_width) plt.axis("off") plt.show()
d = nx.max_weight_matching(g) for (i, j) in list(g.edges()): if (i, j) not in d: if (j, i) not in d: g.remove_edge(i,j) edge_width = [ d['weight']*0.3 for (u,v,d) in g.edges(data=True)] nx.draw_networkx(g, pos, node_color=node_color) nx.draw_networkx_edges(g, pos, width=edge_width) plt.axis("off") plt.show()
安定結婚問題｜ゲール-シャプレイ (Gale-Shapley) アルゴリズムのPython実装
参考にした実装
挙動
入力
python3 gale_shapley.py 3 4
出力
[[3. 1. 0. 2.] [1. 2. 3. 0.] [1. 3. 2. 0.]] [[0. 1. 2.] [1. 0. 2.] [2. 1. 0.] [0. 1. 2.]] Engaged (0, 2) Engaged (1, 3) Already engaged (1, 3) Engaged (2, 0) [[0 2] [1 3] [2 0]]
Python実装
# coding: utf-8 import sys import numpy as np """ Original: http://cielan.hateblo.jp/entry/2016/12/25/193618 """ def create_priority(n, m): """ 優先順位が行ごとにシャッフルされたn次正方行列を生成する :param n: 自グループの次数 :param m: 相手グループの次数 :return: 優先順位行列 """ data = np.empty([0, m]) priority = np.arange(m) for i in range(n): np.random.shuffle(priority) data = np.vstack([data, priority]) return data def gale_shapley(a, b): """ Gale-Shapley アルゴリズムを用いて安定結婚問題を解く :param a: 優先順位行列 :param b: 優先順位行列 :return: 結果行列 """ single_as = {i for i in range(len(a))} # set型の独身集合A single_bs = {i for i in range(len(b))} # set型の独身集合B engaged = np.zeros((len(a), len(b)), dtype=bool) # 婚約行列 while len(single_as) != 0: single_a = single_as.pop() # 好みのリストを順に走査 for target_b in np.argsort(a[single_a, :]): if target_b in single_bs: # まだ婚約していなかったらめでたく婚約成立 engaged[single_a, target_b] = True single_bs.remove(target_b) print('Engaged ', (single_a, target_b)) break else: # 既に婚約していたら婚約者を探し出してどっちがより好まれているか調べる engaged_a = np.where(engaged[:, target_b])[0][0] print('Already engaged ', (engaged_a, target_b)) target_a_list = b[target_b, :] if np.where(target_a_list == single_a)[0][0] < np.where(target_a_list == engaged_a)[0][0]: # 好みの優先順位を調べて今回のほうが好まれていたら元の婚約者との婚約を破棄 engaged[engaged_a, target_b] = False single_as.add(engaged_a) print('Discard ', (engaged_a, target_b)) # 改めて婚約 engaged[single_a, target_b] = True print('Engaged ', (single_a, target_b)) break return engaged if __name__ == '__main__': MEN_NUM = int(sys.argv[1]) # 人数はコマンドライン引数から取得 WOMEN_NUM = int(sys.argv[2]) # 人数はコマンドライン引数から取得 men = create_priority(MEN_NUM, WOMEN_NUM) # 男性の優先順位生成 print(men) women = create_priority(WOMEN_NUM, MEN_NUM) # 女性の優先順位生成 print(women) result = gale_shapley(men, women) # 安定結婚問題を解く print(np.transpose(np.where(result))) # 結果表示
データ分析からの新規施策提案｜SF Bay Area Bike Share, Kaggle
はじめに
某イベントにて、「データ分析からの新規施策提案」をテーマに資料を作成したのでブログでも共有します。
Oculus Goが届いた（感想）
昨晩に届いて2時間くらい一気に試して、今日は「もう別に触らなくて良いかな」という気分まで燃え尽きた。
終わりに
- 勝手に燃え尽きたのは、まだまだ魅力的なコンテンツを知らないからな気もするので調べたい。
【Pandas】欠損値を、欠損していない値からランダム抽出して補完する
あまりこういう欠損値補完はしない気もするけど、業務にて要望があった。調べても、これくらいしか情報が出てこなかったので、自分用メモ。もっと良い書き方がある気がする。
target_column_name = list(df.columns[df.isnull().any(0)]) for tcn in target_column_name: df[tcn] = df[tcn].apply(lambda x: df[tcn].dropna().sample().values[0] if x != x else x)
自然言語処理×ジャーナリズムな研究まとめ ~ 言語処理学会(NLP2018)より ~
今年のGWも終わりますね。僕は若者らしく、今年3月の言語処理学会の論文を読み漁っていました*1。
言語処理学会第24回年次大会(NLP2018) の発表論文集を一般公開しました。年次大会参加者だけでなく、すべての方が登録等一切なしですべての発表論文PDFをご覧いただけます。この公開姿勢を評価いただき、ぜひ学会への入会という形でご支援をお願いします。https://t.co/Lc3kuE8NcT
— 山本 和英 (@y8o) March 26, 2018
個人的に興味のあるジャーナリズム絡みの論文を中心に総計12本読んだので、下記の記事からタイトルを拝借する形で、一つの記事にまとめておきます。
- 新聞記事における政治家の発言の引用記述と議会会議録との対応関係の調査 ―フェイクニュース検出に向けて―
- 関連記事判定のためのニュース記事キーフレーズ抽出
- 経済記事からの不祥事報道検知
- 決算短信からの事業セグメント情報抽出
- ブートストラップ法による科学ニュース記事からの雑誌名抽出
- 検索エンジンによる上位検索ページを情報源とするフェイクニュース自動検出のためのデータセット作成
- ニュースからのトピックに関するストーリーラインの生成
- 複数エンコーダを用いたヤフートピックス見出し候補生成
- 会話によるニュース記事伝達のための間の調整
- プレイデータからのサッカーの速報テキスト生成
- ファクトチェックを必要とするニュース記事の探索の支援
- Experiment on Using Topic Sentence for Neural News Headline Generation
新聞記事における政治家の発言の引用記述と議会会議録との対応関係の調査 ―フェイクニュース検出に向けて―
概要
フェイクニュース検出に向けた調査の研究。「新聞記事に掲載された政治家の発言の引用」と「地方議会会議録」を逐一比較していき、約95%はBoWなどの語句レベルの一致で推定できるとまとめている。
所感
BoWという単純な仕組みで、結構な高割合が評価できるというのは意外。ただよく考えると、新聞記事でそこまで凝った文章加工はしないので妥当な数字な気も。
関連記事判定のためのニュース記事キーフレーズ抽出
概要
ニュースサイトで良くある「関連記事」を自動で導出するタスク。「キーフレーズ共有性」という新たな評価尺度と、その概念に基づく抽出法を提案している。
所感
計算量の節約のためにRNNによる近似を導入したら、性能も上がったという報告が興味深い（本論文の考察でも理由は十分に掘り下げられていない）。
経済記事からの不祥事報道検知
概要
経済記事を「不祥事」に関するものか否かで二値分類するシステムの開発。アルゴリズムはロジスティクス回帰とN-gram。精度を追い求めるだけでなく、解釈性・頑健性などを深く議論している。
所感
機械学習を実システムに導入する際のTipsのような論文。
決算短信からの事業セグメント情報抽出
概要
決算短信特有の言語的な特徴を考慮した「事業セグメント情報抽出手法」を提案し、その有用性について実データを用いて評価。
所感
ドメイン知識をフル活用して、実直にタスクに取り組んでいる。
ブートストラップ法による科学ニュース記事からの雑誌名抽出
概要
雑誌名が特定の文脈に出現しやすいという仮定を立て、雑誌名の両側から学習した文脈をパターンとして利用しブートストラップ法で雑誌名を抽出
所感
論文の第一文のこの問題の解消が根本的な解決策ではないかと思ったり。。。
日本語の科学ニュース記事では，研究成果がわかりやすく述べられるが，出典となる文献情報は明記されない傾向にある．
検索エンジンによる上位検索ページを情報源とするフェイクニュース自動検出のためのデータセット作成
概要
フェイクニュース検出に関して、人間と同じやり方（検索エンジンによる上位検索ページを情報源として判断）をコンピュータで再現しようとした論文。
所感
うまくいかなかった例を分析した結果「検索された結果ページにフェイクニュースの記事のほうが多く存在してしまう場合」が挙げられていて、そうだよなあと思った。このアプローチだとどうやっても人間を大きく超える性能は出せないだろうが、目的は「データセット作成」に置いているので悪くもない気もする。
upura.hatenablog.com
ニュースからのトピックに関するストーリーラインの生成
概要
ニュースコーパスからトピック (知りたい事柄) に関連するテーマを抽出し，そのテーマに関連する文が時系列順に並んだ文集合 (ストーリーライン) を出力するシステムを提案。
所感
「ストーリーラインの生成」というタスクを、細かいタスクに分解している。他の研究成果を動員して実現する応用研究のような立ち位置。
複数エンコーダを用いたヤフートピックス見出し候補生成
概要
「記事タイトル」と「記事リード文」を入力とし、エンコーダ・デコーダの枠組みからトピックス見出しを生成する手法を提案。
所感
単に先行研究をサービスに適用するだけでなく、技術的な修正もしているのが良い。
会話によるニュース記事伝達のための間の調整
概要
会話によるニュース記事伝達において、割り込みを許容しながら快適なリズムで会話を進行させるための間の調整について検討。テクノロジー系のニュース記事 100 個を人手で要約・口語化し、実際に声優に話してもらいコーパスを作成。双方向 LSTMやBayesianRidgeモデルで学習させた。
所感
スマートスピーカーが流行っている中、ある意味新しいジャーナリズムの形を模索する論文と言っても良い気がする。
プレイデータからのサッカーの速報テキスト生成
「選手名やチーム名を汎化タグに変換」「単語bigramを1つの単語として結合」の工夫で、encoder-decoder[6]モデルの性能が向上。
所感
直感的にも性能改善しそうな前処理をすることで、実際に性能が改善しており、腑に落ちやすかった。
ファクトチェックを必要とするニュース記事の探索の支援
概要
ファクトチェックの必要性を示唆する情報（＝「端緒情報」）の探索を自動化し，人手による要検証記事探索作業を技術的に支援する仕組みを構築。
所感
うまくいかなかった例を見ていると、人間の発言をコンピュータに解釈させることの難しさを改めて実感する。
Experiment on Using Topic Sentence for Neural News Headline Generation
概要
encoder-decoderモデルを用いたニュースの見出し生成タスクで、第一文ではなく「トピックセンテンス」を使った場合の影響を調べる。第一文に加えてトピックセンテンスも利用した方が性能が上がった。
所感
多様な情報を利用した方が精度は出そうなので、最後はどこかで計算コストと性能のトレード・オフみたいな話に帰着しそう。
*1:その他にKaggleもやっていました
【論文メモ】Experiment on Using Topic Sentence for Neural News Headline Generation
Experiment on Using Topic Sentence for Neural News Headline Generation
- Jan Wira Gotama Putra (東工大), Hayato Kobayashi (ヤフー/理研AIP), Nobuyuki Shimizu (ヤフー)
- 言語処理学会第24回年次大会(NLP2018)
- http://anlp.jp/proceedings/annual_meeting/2018/pdf_dir/A1-2.pdf
どんなもの？
- encoder-decoderモデルを用いたニュースの見出し生成タスクにおいて、先行研究では文章の第一文を使うことが多い
- 本研究では、トピックセンテンス（文章内の重要な文章）を使った場合の影響を調べる
- 第一文よりもトピックセンテンスの方が有用か否か
- 第一文に加えてトピックセンテンスも使った場合にも有用か否か
先行研究と比べてどこがすごい？
上記に記載
技術や手法のキモはどこ？
「トピックセンテンス」の定義
文献[14]に基づき、以下のように定義する
Topic sentence contains the core elements ⟨subject, verb, object⟩ and at least one subordinate element time or location
どうやって有効だと検証した？
議論はある？
- 「トピックセンテンス」以外の重要文抽出アルゴリズムについても検討したい
次に読むべき論文は？
NULL
