Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
[DEIM2023] 高速な形態素解析器Vibratoの紹介
Search
LegalOn Technologies, Inc
PRO
March 06, 2023
Technology
0
1k
[DEIM2023] 高速な形態素解析器Vibratoの紹介
DEIM2023 にて、LegalOn Technologies Research からの技術報告です。
LegalOn Technologies, Inc
PRO
March 06, 2023
Tweet
Share
More Decks by LegalOn Technologies, Inc
See All by LegalOn Technologies, Inc
リーガルテックにおける検索・推薦技術
legalontechnologies
PRO
4
2k
[NLP2023] 最小コスト法に基づく形態素解析におけるCPU キャッシュの効率化
legalontechnologies
PRO
1
110
生成AIを搭載したプロダクト開発 - 少人数で爆速リリースしてわかったこと -
legalontechnologies
PRO
1
14k
Auto-evaluation of ranking model by LLM
legalontechnologies
PRO
0
960
株式会社LegalOn Technologies 会社紹介資料
legalontechnologies
PRO
7
100k
【LegalOnに聞く】ChatGPTを活用したプロダクト開発〜本番運用のハードルとは〜
legalontechnologies
PRO
0
260
株式会社LegalOn Technologies 検索・推薦チーム紹介資料
legalontechnologies
PRO
0
1.8k
株式会社LegalOn Technologies 開発職向け会社紹介資料
legalontechnologies
PRO
1
34k
[DEIM2022] 高速な単語分割器VaporettoとパターンマッチングマシンDaachorseの紹介
legalontechnologies
PRO
1
670
Other Decks in Technology
See All in Technology
ユーザーの購買行動モデリングとその分析 / dsc-purchase-analysis
cyberagentdevelopers
PRO
2
100
話題のGraphRAG、その可能性と課題を理解する
hide212131
4
1.5k
pandasはPolarsに性能面で追いつき追い越せるのか
vaaaaanquish
4
4.6k
独自ツール開発でスタジオ撮影をDX!「VLS(Virtual LED Studio)」 / dx-studio-vls
cyberagentdevelopers
PRO
1
180
APIテスト自動化の勘所
yokawasa
7
4.2k
なんで、私がAWS Heroに!? 〜社外の広い世界に一歩踏み出そう〜
minorun365
PRO
6
1.1k
Amazon_CloudWatch_ログ異常検出_導入ガイド
tsujiba
4
1.6k
プロダクト成長に対応するプラットフォーム戦略:Authleteによる共通認証基盤の移行事例 / Building an authentication platform using Authlete and AWS
kakehashi
1
150
新R25、乃木坂46 Mobileなどのファンビジネスを支えるマルチテナンシーなプラットフォームの全体像 / cam-multi-cloud
cyberagentdevelopers
PRO
1
130
分布で見る効果検証入門 / ai-distributional-effect
cyberagentdevelopers
PRO
4
700
グローバル展開を見据えたサービスにおける機械翻訳プラクティス / dp-ai-translating
cyberagentdevelopers
PRO
1
150
君は隠しイベントを見つけれるか?
mujyun
0
290
Featured
See All Featured
The Language of Interfaces
destraynor
154
24k
Writing Fast Ruby
sferik
626
61k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
Testing 201, or: Great Expectations
jmmastey
38
7k
Learning to Love Humans: Emotional Interface Design
aarron
272
40k
Intergalactic Javascript Robots from Outer Space
tanoku
268
27k
Happy Clients
brianwarren
97
6.7k
How to train your dragon (web standard)
notwaldorf
88
5.7k
Bash Introduction
62gerente
608
210k
Automating Front-end Workflow
addyosmani
1365
200k
Fashionably flexible responsive web design (full day workshop)
malarkey
404
65k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
107
49k
Transcript
DEIM2023 技術報告 神田峻介(LegalOn Technologies Research) 2023年3月6日 高速な形態素解析器Vibratoの紹介 株式会社LegalOn Technologies
2 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
株式会社LegalOn Technologies レビュー支援ソフトウェア AI契約管理システム 代表: 角田 望 設立: 2017年4月21日 従業員等: 470名※1(役員含) 資本金等: 178.5億円※2(資本準備金等含) ※1: 2022年12月時点 ※2: 2022年6月時点 契約・法令情報メディア 株式会社LegalOn Technologiesは、弁護士の法務知見と自然言語処理技術や機械学習な どのテクノロジーを組み合わせ、法務業界のイノベーションを推進するサービスの開発・提供 をしています。
3 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
LegalOn Technologies Researchメンバー主体で開発している形態素解析器について紹介 ❏ Vibrato: VIterbi-Based acceleRAted TOkenizer ❏ OSSコミュニティ “daac-tools” で開発・管理 本日の発表内容 https://github.com/daac-tools
4 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
以下の2ステップにより入力文から形態素列を得るアルゴリズム 1. 入力文に現れる単語をノードとしたグラフ構造(単語ラティス)を構築 2. 単語本体や単語の並びの出現しやすさを表したコストの和が最小となる経路を探索 最小コスト法による形態素解析 ソフトウェア:MeCab, Kuromoji, Sudachi, Vibrato など
5 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
最小コスト法に基づくOSSの形態素解析器 ❏ 提案手法による時間・メモリの効率化(本日の発表内容) ❏ CPUキャッシュ効率化による高速解析 ❏ コスト計算分割による圧縮モデルオプション ❏ MeCab互換 ❏ MeCabと同じ解析結果をサポート ❏ Pure Rust ❏ Rustプロダクトに自然に導入可能(e.g., Tantivy-vibrato) ❏ ちなみにPython Wrapperもあります https://github.com/daac-tools/python-vibrato Vibratoとは
CPUキャッシュ効率化による高速化
7 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
最小コスト法はランダムアクセスが多い! ❏ 辞書単語列挙(辞書引き)でのダブル配列トライの探索 ❏ コスト参照のための連接表アクセス モデルの肥大化に伴いランダムアクセスによるキャッシュミスがボトルネックに! ❏ mecab-ipadic-neologd: 単語辞書 約460万エントリ ❏ unidic-cwj v3.1.1: 連接表 15388×15626 = 459 MiB Vibratoでは参照の局所性を改善するためのデータ構造を提案 ❏ 文字単位でのダブル配列トライの実装 ❏ 頻度に基づくIDマッピング 最小コスト法による形態素解析の時間的ボトルネック ※unidic-mecab v2.1.2では68MiB程度 ※ipadic-mecab v2.7.0では40万程度
8 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
入力文に現れる辞書単語はトライ木の共通接頭辞検索により列挙 ❏ 多くの形態素解析器はトライの表現にダブル配列を採用 ❏ 定数時間でエッジの探索を実現 エッジの探索は配列上のランダムアクセス ❏ 辞書のサイズが大きくなるとキャッシュミスがボトルネックに! 辞書引きのキャッシュ効率化:背景と問題点
9 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
従来の実装:文字列をバイト列として表現 ❏ 汎用性、実装の容易さが理由 Vibratoの実装:文字列をUnicodeのコードポイント列として表現 ❏ 木の高さを抑えランダムアクセスを削減 辞書引きのキャッシュ効率化:Vibratoのアイデア
10 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
連接コスト:形態素ラティスのエッジのコスト ❏ 左側と右側のノードのIDでアクセスされる連接表に格納される 連接表のキャッシュ効率化:背景と問題点 UniDic v3.1.1では連接表が巨大:15,388 × 15,626 = 459 MiB ➔ 頻繁なアクセスによるキャッシュミスが重大なボトルネックに!
11 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
頻繁に使用されるコストが配列の先頭に集まるようにIDをマッピング ❏ 頻度順に若いIDを割り当て直す ❏ 頻繁に使用されるコストが密集し参照の局所性が改善 ❏ 頻度は訓練コーパスを解析し算出 連接表のキャッシュ効率化:Vibratoのアイデア 1.5万中上位40件の 使用率が50% ※訓練コーパス:BCCWJ
12 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
文書コーパス:BCCWJ v1.1 ❏ 速度評価用:サブコーパスからランダムに抽出した10万文 ❏ マッピング訓練用:コアデータ6万文 高速化の実験結果
13 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
他の形態素解析器との速度比較 IPADICで 2.1x 高速 UniDicで 2.3x 高速 文書コーパス:BCCWJ v1.1 ❏ 速度評価用:サブコーパスからランダムに抽出した10万文 ❏ マッピング訓練用:コアデータ6万文
スコア計算の分割による連接表の省メモリ化
15 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
素性の設計によっては連接表が大規模になりモデルサイズが肥大化する ❏ unidic v2.1.2: 5,981 × 5,981 = 68 MiB ❏ unidic v3.1.1: 15,388×15,626 = 459 MiB 連接表の構築はスコアの事前計算を解析時に立て替えることで回避可能 ❏ ただしメモリと解析時間のトレードオフ Vibratoのアイデア ❏ 連接表の肥大化に寄与しないスコアのみを事前計算 ❏ 解析速度を大きく損なわずに連接表を省メモリ化 最小コスト法による形態素解析の空間的ボトルネック
16 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
Step1: 人手で作った素性テンプレートに基づいて素性列を抽出 Step2: 内積 wTΦ を連接スコアとして計算 背景: 連接スコアの計算 法律 の POS1/POS1 POS1,POS2/POS1 POS1/POS1,POS2 素性テンプレート 名詞/助詞 名詞,一般/助詞 名詞/助詞,格助詞 素性列 h(法律,の) Step1. 素性列を抽出 Φ = (0,0,…,1,…,1,…,1,…,0,0) w = (2,1,…,3,…,4,…,6,…,6,3) 名 詞 /助 詞 名 詞 ,一 般 /助 詞 名 詞 /助 詞 ,格 助 詞 h(法律,の) = 3 + 4 + 6 = 13 Step2. スコアを計算 ※ 連接スコア = -1*連接コスト Φ: 素性ベクトル (multi-hot vector) w: 重みベクトル
17 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
解析時の重みの足し算を回避するため、事前計算し連接表に保存しておく 背景: 連接表の構築 POS1/POS1 POS1,POS2/POS1 POS1/POS1,POS2 素性テンプレート 名詞/助詞 名詞,一般/助詞 名詞/助詞,格助詞 素性列 Rid(の) = 助詞-助詞-助詞,格助詞 Lid(法律) = 名詞-名詞,一般-名詞 左右それぞれの素性列の連結が ID 13 Lid(法律) Rid(の) h(法律,の) = 3 + 4 + 6 = 13 問題点:詳細に素性テンプレートを設計すると、IDが増え連接表が肥大化! ❏ 例えば、UniDic v3.1.1 (L1正則化) で 13,403 × 13,689 = 350 MiB
18 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
素性テンプレートの一部のみを事前計算し連接表に格納 ❏ 素性列の組合せ数が減るので、連接表の行数・列数も減る ❏ 事前計算しない素性に対応するスコアは解析時に陽に計算 圧縮のアイデア:スコアの部分的事前計算 POS1/POS1 POS1,POS2/POS1 POS1/POS1,POS2 素性テンプレート 名詞/助詞 名詞,一般/助詞 名詞/助詞,格助詞 素性列 Rid(の) = 助詞-助詞,格助詞 Lid(法律) = 名詞-名詞 IDがシンプルになって 組合せ数が減少 9 Lid(法律) Rid(の) h(法律,の) = 3 + 4 + 6 = 9
19 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
事前計算しない素性テンプレート数は時間とメモリのトレードオフ ❏ より多く選べば連接表は小さくなるが、解析時の計算が多くなる 事前計算する素性テンプレートの選択戦略 Vibratoの戦略 ❏ 連接表のサイズに大きく影響を与える素性テン プレートを貪欲法により選択 UniDic v3.1.1での実験結果(右図) ❏ 91の素性テンプレートから5個を取り除くだけ で、連接表は10%程度まで軽量化
20 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
辞書 ❏ UniDic v3.1.1 モデル訓練用コーパス ❏ BCCWJコアデータ6万文 ❏ 人手で短単位アノテーション ❏ L1正則化 速度評価用コーパス ❏ サブコーパス10万文 (ランダムに抽出) 実験:時間とメモリのトレードオフ 8.5倍省メモリ 2.1倍 低速化 ダブル配列 + SIMD による高速スコア計算バージョン
21 当該資料の利用により直接または間接に生じた損害や損失等について、株式会社 LegalOn Technologiesは一切の責任を負いません。 ©LegalOn Technologies, Inc. all rights reserved.
形態素解析器Vibratoの技術仕様を紹介 ❏ CPUキャッシュ効率化による高速解析 ❏ コスト計算分割による圧縮オプション 詳細な解説がEnginnering Blogにあります! https://tech.legalforce.co.jp/ 一週間後の言語処理学会でも発表します! まとめ LegalOn Technologiesでは、SREやバックエンドエンジニア、検索システム、研究開発に興味のあるインター ン生など様々なポジションを募集しています。 興味を持たれた方は是非お声がけください! PR