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

Slackの絵文字サジェストを機械学習でリバースエンジニアリング

 Slackの絵文字サジェストを機械学習でリバースエンジニアリング

Keisuke OGAKI

July 08, 2022
Tweet

More Decks by Keisuke OGAKI

Other Decks in Programming

Transcript

  1. 学習データ作成 length = 3 candidate_characters = string.ascii_lowercase + string.digits +

    ' ' for query_characters in itertools.combinations_with_replacement(candidate_characters, length): query = ''.join(query_characters) editor = browser.find_element(By.CLASS_NAME, 'ql-editor') editor.send_keys(query) l = browser.find_element_by_id('chat_input_tab_ui') candidates = l.find_elements_by_tag_name('li') result = [candidate.text for candidate in candidates] f.write(json.dumps(dict(key=query, result=result))+'\n') 3文字までの英数字の組み合わせの全通り seleniumで直接入力し、サジェスト結果をそのまま保存 {'aaa': ['kaaba'], 'aab': ['kaaba', 'tanabata_tree'], 'aac': ['abacus', 'parachute'], 'aad': ['green_salad'], 'aae': [], 'aaf': ['falafel'], 'aag': [],
  2. アルゴリズムの一致度の評価はどうやる? query -> answerが1:1ではないので、precision@k, recall@kではなく、平均順位を評価指標とする {'aaa': ['kaaba'], 'aab': ['kaaba', 'tanabata_tree'],

    'aac': ['abacus', 'parachute'], 'aad': ['green_salad'], 'aae': [], 'aaf': ['falafel'], 'aag': [], mean(1,2,3,5) = 2.75 • 最小値は2.5なので、0.25分間違えてる ◦ oboに対してtoolboxが不正解なの なんで...謎アルゴリズム これを評価セットのkey全てで順位を取る (最小値)
  3. 一旦それっぽいアルゴリズムを考えてみる 理論最小値: 7.70 def distance(query, target): if not set(query).issubset(target): return

    99999 else: return target.find(query[0]) 文字列がサブセットになっているか 59.65 マッチ部の最小長さ+出現位置 def distance2(query, target): if not set(query).issubset(target): return 9999999999 else: pattern = '.*?'.join(query) matches = re.findall(pattern, target) if not matches: return 999999999 else: return min(len(found) for found in matches)*100+target.find(query[0]) 17.29 def distance4(query, target): if not set(query).issubset(target): return 9999999999 else: pattern = '.*?'.join(query) matches = re.findall(pattern, target) if not matches: return 999999999 else: return min(len(found) for found in matches)*1000+len(target)*10+target.find( matches[0]) マッチ部の最小長さ+文字列長+出現 位置 14.94
  4. 学習できる形に落とす やりたいこと: actualがTrueのものを上位に集める “obo/snowboarder” “obo/horse” 9.998831e-01 7.690672e-12 なるべく1に近いスコア な るべく0に近いスコア

    になるように学習 モデル (LSTM, Transformer) • key/queryと、区切り文字を適当にきめて文字列で入れることで二変数・三変数関数を雑に表現できるの はNLPのおもしろいところ ◦ もちろん別々にエンコードして明確に 2変数にしてもいいですが • 今回は1/0を当てる問題にしているが、ランキング学習をするという手もある ◦ snowboarderはhorseより順位が上である、というのを学習させる ◦ 特に上位の並びを当てるのはこちらの方がよくなるはず
  5. さらなる高みへ: 速度改善 keyが変わるごとに、全てのcandidateと の組み合わせを実行しなきゃ行けない、 手元のMacだと1891絵文字の探索で平 均1秒、線形なので会社の全絵文字 10000だと5,6秒かかりそう “obo/snowboarder” “obo/horse” 9.998831e-01

    7.690672e-12 モデル (LSTM, Transformer) for key in tqdm(keys_test): for candidate in more_itertools.chunked(candidates, n=100): xs = key + '/' + candidate pred = torch.nn.Sigmoid()(model(xs)).to('cpu').numpy()
  6. さらなる高みへ: 速度改善 “obo” “horse” 9.998831e-01 7.690672e-12 QueryEncoder モデル (LSTM, Transformer)

    TargetEncoder モデル (LSTM, Transformer) “snowboarder” 内積 なるべく1に近いスコア な るべく0に近いスコア になるように学習 target_feature = model.model2(candidates).to('cpu').numpy() #事前計算 query_feature = model.model1(keys_test).to('cpu').numpy() score=query_feature.dot(target_feature.T) • targetは事前にエンコードしておけるので、検索時にはクエリのエンコー ドと行列積1回: 平均0.018s • エンコード以外はベクトルの内積だけなので、例えば ESなど汎用的な 検索エンジンを利用可能 for文が消える
  7. 結果 平均順位 時間 [ヒューリスティック] マッチ部の最小長さ+文字列長+ 出現位置 14.94 (+7.24) 0.008s [学習]

    TwinModel 46.01(+) 0.018s [学習] LSTM, 2layer, 100D 10.49 (+2.79) 1s 理論最小値 7.70
  8. どうして難しいのか? obo/snowboarder o.*?b.*?o match: owbo obo o.*?b.*?o ???? snowboarder 難1:

    内積で表現できる形 式にエンコード 難2: どんなクエリにも対 応可能なエンコード (例えば)1層目でクエリを 組み立てて2層目でマッチ すればOK