Pythonだけでクロスワードパズルを自動生成 〜自然言語処理・組合せ探索・Webアプリ開発〜

Pythonだけでクロスワードパズルを⾃動⽣成 〜⾃然⾔語処理‧組合せ探索‧Webアプリ開発〜 ⾺嶋海⽃ ⽇本経済新聞社 2023年10⽉28⽇（PyCon APAC 2023） 1

⾃⼰紹介 n 名前 p ⾺嶋海⽃（まじま かいと） n 所属 p ⽇本経済新聞社（2023/4新卒⼊社） Ø ⽇経電⼦版の開発 Ø 2022/6~ インターンとして⾃然⾔語処理の研究 n Pythonと私 p 5年前の⼤学の授業で出会う p 研究‧インターン‧業務などで使⽤ 2

発表⽬的 n PythonだけでのWebアプリ開発の体験を共有 p Pythonの応⽤領域の広さ p Pythonの使いやすさ n 想定する聞き⼿ p Pythonのライブラリについて広く浅く知りたい⼈ p Pythonでのフロントエンドも含めたアプリ開発に興味がある⼈ p ⾃然⾔語処理、最適化に興味がある⼈ 3

⽬次 第１部 アプリケーションの概要 第２部 アプリケーションの処理 第３部 開発者体験 n どんなアプリ？ n 全体像 n 環境 n 作成背景 n ⾃然⾔語処理 n Pythonだけでの開発 n 実装上の課題 n パズル⽣成 n Webアプリ表⽰ 4

⽬次 第１部 アプリケーションの概要 第２部 アプリケーションの処理 第３部 開発者体験 n どんなアプリ？ n 全体像 n 環境 n 作成背景 n ⾃然⾔語処理 n Pythonだけでの開発 n 実装上の課題 n パズル⽣成 n Webアプリ表⽰ 5

どんなアプリ？w/ デモ ニュース⽤語でクロスワードを⾃動⽣成するアプリ 設定を⼊⼒ ニュース⽤語を含むヒント付きクロスワードパズルを⽣成 6

作成背景 ニュースメディアとパズルの親和性の⾼さ n ニューヨークタイムズ p クロスワードを毎⽇掲載 p パズルの購読者数が100万⼈を突破（全体の10%） p 2022年に⼈気パズル「Wordle」を買収 n ⽇経新聞 p 毎週⽇曜⽇にクロスワードを掲載 Ø https://vdata.nikkei.com/nikkeithestyle/crossword/ p 2021年にスマホアプリ「⽇経脳活クイズ」をリリース https://vdata.nikkei.com/nikkeithestyl e/crossword/mondai.html?id=0338 7

• https://vdata.nikkei.com/nikkeithestyle/crossword/
• https://vdata.nikkei.com/nikkeithestyl

作成背景 ニュースメディアとパズルの親和性の⾼さ n 教育ツールとしての側⾯ p ニュース：「教育に新聞を」プロジェクト p クロスワード：教育効果について多くの研究がある n ⽇経の所有するデータ p ⽇経電⼦版の記事データ p ⽇経電⼦版ユーザーの閲覧履歴 8

• https://nie.jp/

作成背景 ⽇経電⼦版のデータを⽤いてクロスワードを⾃動⽣成 n クロスワードの特徴 p ニュース⽤語を多く含む p ユーザーや⽤途に合わせてテーマを変更可能 縦のカギ 1: -----2: ------ ⽇経電⼦版データ 内部処理 表⽰ 横のカギ 1: -----2: ------ Pythonのみでアプリケーション全体を実装 9

実装上の課題 n クロスワード⾃動⽣成の難しさ n ⽇本語としての難しさ n ニュースメディア特有の問題 10

課題① クロスワード⾃動⽣成の難しさ n 考慮すべき事項が多い：⼈⼿での作成は職⼈芸 p 単語の配置 p 黒マス配置 p 各単語のカギ（ヒント） n 数学的にも複雑な問題である（NP困難）ことが知られている n 先⾏研究をそのまま使って今回の⽬的を達成できない p 「パズル⽣成」と「ヒント⽣成」を同時に⾏いたい p ニュース⽤語を多く含めたい 11

課題① クロスワード⾃動⽣成の難しさ n ChatGPTに聞いてみた 想定解答 以下の単語を含む4×4マスの クロスワードパズルを作ってください • • • • パイソン トツクリ パケツト ソンタク • • • • ケシン イシ タキ キリ パ ケ イ シ ソ ン ン ツ ト ツ タ ク キ リ 12

課題① クロスワード⾃動⽣成の難しさ n ChatGPTに聞いてみた 想定解答 了解しました。以下に、提供していただいた単語を 含む4x4マスのクロスワードパズルを作成しました。 パ ケ イ シ ソ ン ン ツ ト ツ タ ク キ リ 13

課題① クロスワード⾃動⽣成の難しさ n ChatGPTに聞いてみた このパズルは黒マスを⼆つ含みます 黒マスを含むクロスワードパズルを以下に⽰します。 想定解答 パ ケ イ シ ソ ン ン ツ ト ツ タ ク キ リ 14

課題② ⽇本語の難しさ n ⽂字の種類が多い 26⽂字 → 46⽂字 n ひらがなへの変換が難しい しじょう p 東京株式市場の⽇経平均株価は続伸した いちば p 駅前の市場で取材を⾏ったところ 15

課題③ ニュースメディア特有の問題 n 「ニュース⽤語」の定義が難しい p 固有名詞を全て抜き出せば良い？ p ニュースの理解度の確認になる単語は？ n 適切な記事の抽出が難しい p 全ての記事がニュース⽤語とその説明を含むわけではない Ø ヒントの質に関連 p 記事にも鮮度がある 16

実装上の課題：解決策 n クロスワード⾃動⽣成の難しさ → パズル⽣成は先⾏研究の⼿法を今回の設定に合わせて実装：Python → ヒント⽣成はルールベース（＋⾔語モデル） ：Python n ⽇本語としての難しさ → ⾃然⾔語処理でどうにかする：Python n ニュースメディア特有の問題 →⾃然⾔語処理でどうにかする＋⾃社APIを使⽤：Python やはりPython…!! Pythonは全てを解決する…!! 17

どんなアプリ？ ニュース⽤語でクロスワードを⾃動⽣成するアプリ n ニュース⽤語は⽇経電⼦版から抽出 p カスタムが可能 Ø 朝刊記事、スポーツ記事、読んだ記事など n クロスワードとそれぞれの単語のヒントを⽣成 p アルゴリズムを⾃前で実装 p 詳細は論⽂参照：https://arxiv.org/abs/2308.04688 n 実装は全てPython 18

• https://arxiv.org/abs/2308.04688

⽬次 第１部 アプリケーションの概要 第２部 アプリケーションの処理 第３部 開発者体験 n どんなアプリ？ n 全体像 n 環境 n 作成背景 n ⾃然⾔語処理 n Pythonだけでの開発 n 実装上の課題 n パズル⽣成 n Webアプリ表⽰ 19

アプリケーションの全体像 ①⾃然⾔語処理 ②パズル⽣成 単語＆ヒント キシダフミオ： ⽇本の第100代⾸相は？ ヒントつきクロスワード ソゴウ： セブン＆アイは9⽉1⽇に ○○○‧⻄武の売却を発表した ⽇経電⼦版データ セイセイエーアイ： ⼈間の指⽰に基づき⽂章や 画像を⾃動で⽣成する⼈⼯知能 (⓪外部データ⽤意) ‧‧‧ 外部データ 縦のカギ 1: -----2: ------ 横のカギ 1: -----2: -----20

アプリケーションの全体像 ①⾃然⾔語処理 • • • • • • requests • re • pykakasi • jaconv • alphabet2kana alkana spacy pytorch transformers MeCab 単語＆ヒント キシダフミオ： ⽇本の第100代⾸相は？ ②パズル⽣成 • • • • numpy line-profiler pandas streamlit ヒントつきクロスワード ソゴウ： セブン＆アイは9⽉1⽇に ○○○‧⻄武の売却を発表した ⽇経電⼦版データ セイセイエーアイ： ⼈間の指⽰に基づき⽂章や 画像を⾃動で⽣成する⼈⼯知能 (⓪外部データ⽤意) ‧‧‧ 外部データ 縦のカギ 1: -----2: ------ 横のカギ 1: -----2: -----21

⓪ 外部データの⽤意 n ニュース⽤語だけではパズルが埋まらない p 抽出できても数万語程度 p どの組合せでもパズルを作成することができない n 外部データを⽤いて単語‧ヒントのペアを作成 p Wikipedia：⾒出しと最初の⽂を抽出 p JAQKET：⽇本語QAデータセット n Pythonの役割 p 前処理：読み仮名抽出、単語のフィルタリング等 22

• https://ja.wikipedia.org/wiki/Wikipedia:データベースダウンロード
• https://www.nlp.ecei.tohoku.ac.jp/projects/jaqket/

① ⾃然⾔語処理 ⼤別すると３つの処理が⾏われている 1: 記事選定 2: 単語抽出 閲覧履歴や記事に付与されている情報 から記事をフィルタリング ニュース⽤語を記事内から抽出 出⼒ 単語 ⽇経電⼦版データ 対象記事データ ヒント ex) キシダフミオ ex) ⽇本の100代⾸相は？ 3: ヒント⽣成 ニュース⽤語と記事本⽂を⼊⼒としてヒントを⽣成 23

① ⾃然⾔語処理：記事選定 n ニュース⽤語を抽出する記事のフィルタリング p クローズドな社内APIを使⽤ Ø 記事に付与されているデータで記事検索 Ø 閲覧ログの抽出 p 抽出例 Ø 特定のジャンルの記事（例：スポーツ、経済） Ø 直近１週間の朝刊の記事 Ø 特定のユーザーが閲覧した記事 n 使⽤ライブラリ p requests：API呼び出し 24

• https://requests.readthedocs.io/en/latest/

① ⾃然⾔語処理：単語抽出 n ニュース⽤語を記事内から抽出‧カタカナに変換 p 抽出⼿法（⼀例） Ø 社内APIで記事に紐づくキーワードを取得 Ø 品詞、本⽂との関連性によるフィルタリング Ø 固有表現抽出（NER） n 使⽤ライブラリ p spacy：品詞の判定 p pykakasi, alphabet2kana, alkana, jaconv, MeCab：カタカナへの変換 25

• https://spacy.io/
• https://pypi.org/project/pykakasi/
• https://pypi.org/project/alphabet2kana/
• https://pypi.org/project/alkana.py/
• https://pypi.org/project/jaconv/
• https://pypi.org/project/mecab-python3/

① ⾃然⾔語処理：ヒント⽣成 n ニュース⽤語と記事本⽂を⼊⼒としてヒントを⽣成 p クロスワードのヒントの要件 Ø 解が⼀意に定まる Ø ⽂章が短い⽅が⾒栄えが良い p ⽣成⼿法（⼀例） Ø 記事の該当部分を抽出して⽳埋め問題に Ø 機械学習モデルを使⽤：T5, GPT4など n 使⽤ライブラリ p pytorch, transformers：機械学習モデルの使⽤ 26

• https://pytorch.org/
• https://huggingface.co/docs/transformers/index

② パズル⽣成 n 前提 p ⼊出⼒ Ø ⼊⼒：空のパズル盤⾯‧ニュース⽤語‧外部データの単語 Ø 出⼒：⽭盾なく⽂字が⼊ったパズル盤⾯ p パズル盤⾯の⼤きさ、黒マスの位置は固定 p ニュース⽤語を最低𝑁個含むパズルを⽣成 空のパズル盤⾯ ニュース⽤語 外部データ キシダフミオ ソゴウ セイセイエーアイ ストライキ クラウド ニーサ … リンゴ ゴリラ ランドセル ルールブツク クリスマス スミレ … クロスワード ス ト ラ イ キ ス ミ レ リ ン ト ク ラ ウ ド ミ キ ー プ イ ス 27

② パズル⽣成 n 処理（概要） p 先述の前提を満たすパズル⽣成を最適化問題として定式化 p 先⾏研究の⼿法を問題設定に適⽤できる形に変形 Ø 先⾏研究： https://ojs.aaai.org/index.php/SOCS/article/view/18547 Ø アルゴリズムの詳細： https://arxiv.org/abs/2308.04688 Ø バックトラッキングと呼ばれる⼿法の⼀種 n 使⽤ライブラリ p numpy：⼀部の計算の⾼速化 p line-profiler：計算のボトルネックの特定 28

• https://ojs.aaai.org/index.php/SOCS/article/view/18547
• https://arxiv.org/abs/2308.04688
• https://numpy.org/
• https://pypi.org/project/line-profiler/

②パズル⽣成：Webアプリ表⽰ n StreamlitでWebアプリを作成 p PythonでWebアプリを作成するフレームワーク p Pythonの⽂法で⼿軽にWebアプリが作れる サイドバー n 作った画⾯ ⽣成画⾯ p サイドバー p ⽣成画⾯ 29

②パズル⽣成：Webアプリ表⽰ サイドバー n ⾃動⽣成のパラメーターを⼊⼒ p 黒マス配置 p 記事の取得⽅法 p ヒント⽣成⽅法etc.. n ラジオボタン、スライダーなど多様なボタン p １⾏で実装できる 30

②パズル⽣成：Webアプリ表⽰ ⽣成画⾯ n 現在の進⾏状況を表⽰ p 外部データ→⽇経データ→パズル作成→ヒント作成 n パズル⽣成の様⼦をインタラクティブに表⽰ p 実際の盤⾯に⽂字表⽰ p プログレスバー n ⽣成後はパズル盤⾯とヒントを表⽰ 31

②パズル⽣成：Webアプリ表⽰ ⽣成画⾯ n 現在の進⾏状況を表⽰ p 外部データ→⽇経データ→パズル作成→ヒント作成 n パズル⽣成の様⼦をインタラクティブに表⽰ p 実際の盤⾯に⽂字表⽰ p プログレスバー n ⽣成後はパズル盤⾯とヒントを表⽰ 32

②パズル⽣成：Webアプリ表⽰ ⽣成画⾯ n 現在の進⾏状況を表⽰ p 外部データ→⽇経データ→パズル作成→ヒント作成 n パズル⽣成の様⼦をインタラクティブに表⽰ p 実際の盤⾯に⽂字表⽰ p プログレスバー n ⽣成後はパズル盤⾯とヒントを表⽰ 33

②パズル⽣成：Webアプリ表⽰ ⽣成画⾯ n 現在の進⾏状況を表⽰ p 外部データ→⽇経データ→パズル作成→ヒント作成 n パズル⽣成の様⼦をインタラクティブに表⽰ p 実際の盤⾯に⽂字表⽰ p プログレスバー n ⽣成後はパズル盤⾯とヒントを表⽰ 34

②パズル⽣成：Webアプリ表⽰ n ⾊々なコンポーネントがある p 基本的に１⾏で実装 p パズル盤⾯はpandas.DataFrame.styleで着⾊したもの Ø HTML, CSSを⽤いたレイアウトが可能 https://streamlit.io/ 35

• https://pandas.pydata.org/docs/reference/style.html
• https://streamlit.io/

②パズル⽣成：Webアプリ表⽰ n Streamlitの特徴 p ⻑所 Ø HTML‧CSSの知識が不要 Ø ⼿軽に動くものが作成できる p 短所 Ø 凝ったデザインは難しい Ø 複雑な挙動の実装が難しい n 他のフレームワーク p Gradio：Streamlitと似た使い⽅ができる（機械学習特化） p Django, Flask, Fast API：HTML等と合わせて使う 36

• https://www.gradio.app/
• https://docs.djangoproject.com/ja/4.2/
• https://msiz07-flask-docs-ja.readthedocs.io/ja/latest/
• https://fastapi.tiangolo.com/ja/

全体像（再掲） ①⾃然⾔語処理 ②パズル⽣成 単語＆ヒント キシダフミオ： ⽇本の第100代⾸相は？ ヒントつきクロスワード ソゴウ： セブン＆アイは9⽉1⽇に ○○○‧⻄武の売却を発表した ⽇経電⼦版データ セイセイエーアイ： ⼈間の指⽰に基づき⽂章や 画像を⾃動で⽣成する⼈⼯知能 (⓪外部データ⽤意) ‧‧‧ 外部データ 縦のカギ 1: -----2: ------ 横のカギ 1: -----2: -----37

⽬次 第１部 アプリケーションの概要 第２部 アプリケーションの処理 第３部 開発者体験 n どんなアプリ？ n 全体像 n 環境 n 作成背景 n ⾃然⾔語処理 n Pythonだけでの開発 n 実装上の課題 n パズル⽣成 n Webアプリ表⽰ 38

当時の環境 n ⽴場 p 学⽣インターン p 稼働：週２,３回 ‧５時間程度 p スケジュール感：⼆ヶ⽉後提出のワークショップに間に合わせたい… n スキル p Python：研究で触る程度 p それ以外の⾔語：未経験 39

Pythonで良かった点 ライブラリの豊富さ n 今回の処理（再掲） p API呼び出し p ⾃然⾔語処理 p 組合せ探索 p インタラクティブに画⾯表⽰ n 上記の処理を全てPythonで実装 p 学習コストが低く済む p 各処理の連携が楽（importするだけ） 40

Pythonで良かった点 ⼿軽さ、コミュニケーションコストの低さ n アプリケーションの実装までスピーディーにできる p 「動くもの」を直接共有できる Ø イメージが湧きやすい n コミュニケーションコストが低い p 特にデータサイエンス領域での利⽤⼈⼝が多い p 修正‧環境構築が簡単に⾏える 41

今後の展望 n ⾃然⾔語処理 p まだまだニュース⽤語、ヒントの品質に改善の余地あり Ø ヒントの短⽂化、解の⼀意性の担保、不適切な表現の排除など Ø ⼤規模⾔語モデルの活⽤ n パズル⽣成 p 黒マスの配置も含めた最適化 Ø ニュース⽤語の割合を増やせる p ⾼速化 p 表⽰の改善 Ø ダークモード対応やパズルの保存など Ø streamlitだと厳しい部分も… 42

まとめ n Pythonだけでクロスワード⾃動⽣成アプリを作成 p ⽇経電⼦版のデータを⼊⼒ p ニュース⽤語を含むヒントつきクロスワードパズルを出⼒ n 多様な処理をPythonで実装 p API呼び出し、⾃然⾔語処理、組合せ探索、Webアプリ n 開発者体験は良かった p ライブラリの豊富さ p ⼿軽さ‧コミュニケーションコストの低さ 43

We’re Hiring! 募集要項全般 https://herp.careers/v1/nikkei HACK THE NIKKEI（デジタル⼈材採⽤） https://hack.nikkei.com/ 44

• https://herp.careers/v1/nikkei
• https://hack.nikkei.com/

Appendix: パズルの⽣成速度 n ⾃然⾔語処理 p 現在の実装だと外部データ読み込みがボトルネック(~10秒) p 機械学習モデルを⽤いる場合も時間がかかる n パズル⽣成 p 横軸 Ø ニュース⽤語が占める割合(%) p 縦軸 Ø 左：作成成功率 Ø 右：⽣成時間の中央値‧平均値 p 概ね数秒で完了 図：パズル⽣成の作成成功率と⽣成時間 45