AtCoder で scipy を使って問題を解く

AtCoder で scipy を使って解いた問題をメモ代わりに残しておきます.一部 yukicoder や Library-Checker も含まれています(タイトル詐欺).

AtCoder に入っている numpy / scipy のバージョンはコードテストに以下を入力して実行することで確認できます.

import numpy as np
import scipy as sp
print(f"numpy {np.version.full_version}")
print(f"scipy {sp.version.full_version}")

出力結果(2020/02/28 時点)

numpy 1.18.2
scipy 1.4.1

グラフアルゴリズム: scipy …

more ...

情報検索:検索エンジンの実装と評価 第 8 章 確率的情報検索

この記事は 「情報検索:検索エンジンの実装と評価」(Buttcher本) Advent Calendar 2020 の 25 日目の記事です.

この記事では第 8 章を最初から解説する...予定だったのですが,8.1 から 8.5 までの話,つまり確率的ランキング原理から BM25 の導出までについては,既に素晴らしい日本語解説が存在するため,この部分に関してはそちらを御覧ください12.また,導出などはどうでもいい,とにかく BM25 の式の意味を知りたい,という人は解説動画34を見るとよいと思います.TF-IDF から BM25 までを非常に平易に説明してくれています.

この記事では,8.6 と 8.7 について解説をしていきます.

8.6 Relevance …

more ...

LightGBM でかんたん Learning to Rank

概要

LightGBM には LambdaRank が実装されており,簡単にランキング学習ができるようになっている. しかし残念なことに,日本語で試してみた例は非常に少ない. 特に,実際にデータ用意して学習し,評価するところまでやって公開している例がほぼ見当たらない.

そこで,ランキング学習の練習を兼ねて,データの読み込み,モデルの学習,評価までを行う notebook を作成して公開した. Google Colab で作成しているので,Open in Colab のリンク先に行くことで,作成した notebook を Google Colab 上ですぐに実行することも可能にしている. データとしては,LightGBM が公式で用意している examples のデータを使用し,評価指標としては NDCG@10 を用いた.

作成した notebook

more ...

Manhattan Minimum Spanning Tree

問題

解法

  • NOTE: ここで述べる解法は基本的に以下の topcoder の記事を参考に分割統治部分を座標圧縮+セグメント木で置き換えたものである.

ナイーブに考えると,全点対でマンハッタン距離を計算して Kruskal 法などの最小全域木を求めるアルゴリズムを適用すればよいと思えるが,この解法では入力の頂点数 \(N\) に対して,枝数が \(O(N^2)\) になってしまう.

実は全点対を考える必要はなくて,マンハッタン距離で最小になる点の間で枝を貼るだけでよい(要証明).この方法によって枝数が \(O(N)\) になり,解法の計算量を \(O(N \log N)\) にすることができる.

ではここからは,ある点 P に対してマンハッタン距離が最短になる点を求める方法を説明する.ある点 P とマンハッタン距離が最短になる点を以下の図のような 8 方向の領域のそれぞれで探索し,その 8 …

more ...

第4回 統計・機械学習若手シンポジウム「Academic Writing for Top Conferences」聴講録

概要

2019/11/15(金)・16(土) に名古屋(名工大)で開催された、第 4 回統計・機械学習若手シンポジウムに参加してきました。

  • URL: https://sites.google.com/view/statsml-symposium19/

その中でも「Academic Writing for Top Conferences」というセッションは個人的に有用そうだと思ったので共有します。 後半の「第2部:パネルディスカッション・質疑応答」については、Q&A 集が公開されています (URL)。

第1部:講演

鈴木潤先生(東北大学):国際会議への論文の通し方(一般論)

  • おおよそ以下の発表の縮小版
    • https://www.slideshare.net/JunSuzuki21/2019-0826-yansinvitedtalk …
more ...

機械学習・データマイニング・人工知能分野周りの日本所属の国際会議論文を集めてみる

概要

学生が研究室を選んだり、企業が共同研究先を選ぶ際に、その研究室がきちんと論文を通している研究室かどうかというのは一つに基準になるかと思います。計算機科学分野、特に機械学習・データマイニング・人工知能分野周りの分野では、企業の研究所が強く速報性が求められる影響などにより国際会議論文の影響力が強い傾向があります。そこで本記事では、これらの分野の国際会議に日本所属で論文を通している人を収集することを考えます。

本記事では機械学習・データマイニング・人工知能分野の国際会議を ML, DM, and AI Conference Map に記載されている国際会議とします。

手法

日本所属の国際会議論文を収集する方法として、現在は目視で収集する方法が主流です。既存のプロジェクトとしては以下のものがあります。

目視で収集する手法の問題点として、スケールしないことがあげられます。さらに近年は機械学習・データマイニング・人工知能分野の国際会議論文は増加している傾向もあり、目視で収集するには限界があります。

そこで今回は ACM Digital …

more ...

連続する部分列の和の総和

問題

  • 長さ \(N\) の数列 \(A = [a_1, a_2, ..., a_N]\) が与えられる
  • この数列の任意の連続する部分列の和の総和を \(10^9+7\) で割った余りを求めよ

\(A = [1, 2, 3]\) のとき、和は \(1+2+3+(1+2)+(2+3)+(1+2+3)=20\)

制約

  • \(1 \le N \le 10^6\)
  • \(-10^9 \le a_i \le 10^9 (i = 1, ..., N)\)

解法 …

more ...

pelican(python3)で日本語のカテゴリやタグごとのページのurlを変更する方法

  • 動作環境
    • Python 3.6.1
    • pelican 3.7.1

状況

pelicanでタグ毎にページを表示するurlはtag/(タグ名).htmlであるが、日本語のタグを付けたときにはurlの(タグ名)の部分がよく分からない文字列に自動変換される。 正確にはアルファベットと数字以外の文字列を使った場合であり、これはカテゴリでも同様である。

例えば、日記というタグが付けられている記事一覧のurlはtag/ri-ji.htmlと変換される。

対処

これを直すためには、公式ドキュメントによると、SLUG_SUBSTITUTIONSAUTHOR_SUBSTITUTIONSCATEGORY_SUBSTITUTIONSTAG_SUBSTITUTIONSなどの設定をpelicanconf.pyに追加すればよく、以下の例のように置き換え元と置き換え先の文字列の組を記述すれば良い。

TAG_SUBSTITUTIONS = (('C++', 'cpp'))

この場合、C++というタグが付けられている記事一覧は、tag/cpp.htmlとなる。

しかし日本語タグの場合 …

more ...

(論文メモ) Improving Hypernymy Detection with an Integrated Path-based and Distributional Method (ACL2016)

書誌情報

  • title
    • Improving Hypernymy Detection with an Integrated Path-based and Distributional Method
  • author
    • VeredShwartz, Yoav Goldberg, Ido Dagan
      • Bar-Ilan University, Israel
  • venue
    • ACL 2016
  • url
  • その他
    • ACL 2016 Outstanding Paper Award

解くべき問題は何か?

  • 単語の組(x,y)に対して、yがxの上位語であるかどうかを推定
    • 例: x = トム・クルーズ, y = 俳優 -> yはxの上位語である
    • 質問応答などで有用な応用がある …
more ...

仮説検定早見表

Date Tags 統計

正規母集団に対する仮説検定

  • 『統計学入門』第12章より

早見表

何の検定 検定統計量 自由度 分布
母平均(母分散既知) \(\frac{\overline{X}-\mu}{\sqrt{\sigma^2/n}}\) 標準正規分布 \(N(0,1)\)
母平均(母分散未知) \(\frac{\overline{X}-\mu}{\sqrt{s^2/n}}\) \(n-1\) t分布
母分散 \(\frac{(n-1)s^2}{\sigma_{0}^2}\) \(n-1\) \(\chi^2\) 分布
2分布の平均(分散が等しい) \(\frac{\overline …
more ...