Upgrade to Pro — share decks privately, control downloads, hide ads and more …

論文紹介: Generating News-Centric Crossword Puzzles As A Constraint Satisfaction and Optimization Problem

論文紹介: Generating News-Centric Crossword Puzzles As A Constraint Satisfaction and Optimization Problem

2023年11月18日の「IR Reading 2023秋(オンライン)」での発表資料
https://sigir.jp/post/2023-11-18-irreading_2023fall/

## 書誌情報
Kaito Majima and Shotaro Ishihara. 2023. Generating News-Centric Crossword Puzzles As A Constraint Satisfaction and Optimization Problem. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management (CIKM '23). Association for Computing Machinery, New York, NY, USA, 4170–4174. https://doi.org/10.1145/3583780.3615151

Shotaro Ishihara

November 04, 2023
Tweet

More Decks by Shotaro Ishihara

Other Decks in Research

Transcript

  1. 論文紹介:
    Generating News-Centric Crossword
    Puzzles As A Constraint Satisfaction
    and Optimization Problem
    Kaito Majima and Shotaro Ishihara (Nikkei Inc.)
    CIKM 2023 short paper
    https://dl.acm.org/doi/10.1145/3583780.3615151
    紹介者:石原祥太郎 (日経イノベーション・ラボ 主任研究員)
    IR Reading 2023 秋、2023 年 11 月 18 日

    View full-size slide

  2. ● 国際会議 CIKM 2023 の short paper で採択された
    論文の紹介
    ○ 参加報告記事も公開済み
    ○ Python での実装に関しては PyCon APAC 2023
    にも採択 [発表資料]
    ○ 国内では「NLP若手の会(YANS)第17回シンポ
    ジウム」で奨励賞を受賞
    2
    本発表の概要

    View full-size slide

  3. 目次
    5
    ● はじめに
    ● 関連研究
    ● 提案手法
    ● 実験
    ● 定性評価と今後の展望
    ● 結論

    View full-size slide

  4. クロスワードパズル
    6
    ● 教育的ツールとしての役割も
    ● この役割を強めるため
    「ニュース中心のクロスワード
    パズル」を作りたい

    View full-size slide

  5. ニュース中心のクロスワードパズル
    7
    ニュース由来の単語を多く盛り込むことで、人々
    のニュースへの興味を刺激する
    たとえば:
    ● 朝夕刊
    ● 個人の閲覧履歴

    View full-size slide

  6. 問い:どう実現するか?
    8
    ● 自動生成の枠組み?
    ● どんなアルゴリズムが使える?
    ● 定性的評価と定量的評価?

    View full-size slide

  7. 我々の貢献
    9
    ● 自動生成の枠組み?
    ○ 自動生成の一つの枠組みを構築
    ● どんなアルゴリズムが使える?
    ○ 制約充足最適化問題として定式化
    ● 定性的評価と定量的評価?
    ○ 生成確率・時間や得られた知見を報告

    View full-size slide

  8. 目次
    10
    ● はじめに
    ● 関連研究
    ● 提案手法
    ● 実験
    ● 定性評価と今後の展望
    ● 結論

    View full-size slide

  9. パズルの組み合わせ探索
    11
    ● クロスワードパズル生成は NP 困難 [2, 4, 6]
    ● 制約充足最適化問題として解く先行研究 [4]
    は存在
    ○ 我々は、この手法が教育目的に応用できる
    と主張した

    View full-size slide

  10. クロスワードパズルとニュース
    12
    ● クイズの自動生成を実現する枠組みは自明では
    ない [31]
    ● クロスワードパズルはニュースメディアで人気
    だが、教育応用については議論が不十分 [16]

    View full-size slide

  11. 目次
    13
    ● はじめに
    ● 関連研究
    ● 提案手法
    ● 実験
    ● 定性評価と今後の展望
    ● 結論

    View full-size slide

  12. 米インターネット通販最大手の
    アマゾン・ドット・コムは5
    日、ロボット掃除機「_____」の
    米アイロボットを買収すると発
    表した。
    Amazon.com, the largest U.S.
    Internet retailer, announced on
    April 5 that it will acquire iRobot,
    a U.S. company that produces the
    _____ robot vacuum cleaner.
    提案する枠組み
    14
    Wikipedia
    記事の収集 解の抽出 パズルの組み合わせ探索・ヒント生成
    解の集合
    カタカナ変換
    ア ベ ハ ネ ル
    テ ル シ エ イ グ ン
    ク バ ジ マ バ
    シ ク マ ー バ
    バ ツ ハ ル エ
    マ ツ ユ リ ー
    タ ハ リ ベ ラ ル
    ニュース由来の単語の割合 = 15 /19 (=> Target rate; T)
    Clue A:
    449,895 単語
    2,006 単語

    View full-size slide

  13. 記事の収集
    15
    ● 新聞記事 (小規模)
    ● 外部リソース (大規模)

    View full-size slide

  14. 16
    ● 固有表現認識&穴埋め
    (大規模言語モデルを用いた手法も検証中)
    米インターネット通販最大手のアマゾン・ドット・コムは5
    日、ロボット掃除機「_____」の米アイロボットを買収すると
    発表した。
    Amazon.com, the largest U.S. Internet retailer, announced on April
    5 that it will acquire iRobot, a U.S. company that produces the
    _____ robot vacuum cleaner.
    米中間選挙を受けた米メディアの報道は、____系と保守系で論
    調が割れた。連邦議会上院が激戦となるなか、____系メディア
    は民主党が接戦州の一部で議席を確保したと強調した。
    U.S. media coverage of the U.S. midterm elections was divided
    between ____ and conservative media. While the U.S. Senate was
    hotly contested, ____ media emphasized that the Democrats had
    secured seats in some of the closely contested states.
    Clue A:
    Clue B:
    解の抽出とヒント生成

    View full-size slide

  15. ● 最適な選択肢を効率的に探索し、解が見つかっ
    たら処理を終了する (Backtracking と呼ばれる
    手法 [参照])
    ○ 黒マスとスロットの配置は不変
    ○ すべてのスロットに文字が入る
    ○ ニュース由来の単語を少なくとも T % 含む
    パズルの組み合わせ探索
    17

    View full-size slide

  16. 目次
    20
    ● はじめに
    ● 関連研究
    ● 提案手法
    ● 実験
    ● 定性評価と今後の展望
    ● 結論

    View full-size slide

  17. データセット
    21
    ● Nikkei:「日経電子版」から
    ○ 2,006 単語
    ● Wikipedia
    ○ 449,895 単語

    View full-size slide

  18. 実験設定
    22
    ● サイズ:7 * 7
    ● ニュース由来の単語の割合 (T)
    ○ 10〜100 % まで 10 % 刻みで
    ● 黒マスの配置 (P):
    ○ 黒マス数 9〜12 で、それぞれ 10 パターン
    ずつランダムに生成

    View full-size slide

  19. T ごとの生成確率・時間
    23

    View full-size slide

  20. T ごとの生成時間の分布
    24

    View full-size slide

  21. 黒マス数ごとの生成時間の分布
    25

    View full-size slide

  22. 目次
    26
    ● はじめに
    ● 関連研究
    ● 提案手法
    ● 実験
    ● 定性評価と今後の展望
    ● 結論

    View full-size slide

  23. 定性評価
    27
    ● 自然言語処理の研究者やクロスワードパズル
    の制作者などがプロトタイプを評価
    ● 特に、ヒント生成の指摘が多かった
    ○ 品質推定と並び替え
    ○ 質問応答データセットの活用
    ○ 大規模言語モデルの活用

    View full-size slide

  24. 今後の展望
    28
    ● ヒント生成の改善
    ● より大規模なユーザテストも計画中

    View full-size slide

  25. 目次
    29
    ● はじめに
    ● 関連研究
    ● 提案手法
    ● 実験
    ● 定性評価と今後の展望
    ● 結論

    View full-size slide

  26. 30
    ● ニュースへの関心を高めるため、ニュース中心
    のクロスワードパズルを生成する枠組みを提案
    ● より多くのニュース由来の単語を含めるという
    教育目的を、制約充足最適化問題として達成
    ● ニュース由来の単語が少ない条件下 (2,006 <
    449,895) でも、ニュース中心のクロスワード
    パズルが生成できると示し、現在の課題と今後
    の方向性について議論

    View full-size slide