CreateField Blog

オープンソースを使って個人でWebサービスを開発・運営していたブログ

特許データで学習させたSpherical Text Embeddingの結果を眺める

はじめに

これは、情報検索・検索エンジン Advent Calendar 2019 の 22日目の記事です。

かなり遅れてしまいましたが、Advent Calendar 2019の記事を書きます。

意味的に類似するドキュメントを検索するために活用される技術の1つとして、Word Embeddingがあります。 今回は、Word Embedding系の技術で最近提案されたSpherical Text Embedding - JoSE(Joint Spherical Embedding)を特許データで試してみます。

  • 論文

https://arxiv.org/pdf/1911.01196.pdf

  • スライド

https://yumeng5.github.io/files/Spherical-Text-Embedding.pdf

Spherical Text Embedding について

Spherical Text Embeddingは、周囲の単語だけでなく、段落/文書全体とも意味的に一貫しているべきという理論にもとづき、球面埋め込み空間を利用して学習して、単語、文書の分散表現を得る手法のようです。

以下は、論文中より単語類似度の精度比較です。Word2VecやfastTextより精度が良い結果が得られているそうです。

f:id:naoa_y:20191224213003p:plain
Spherical Text Embedding https://arxiv.org/pdf/1911.01196.pdf より抜粋

学習時間も早くリーズナブルそうです。

f:id:naoa_y:20191225122227p:plain
Spherical Text Embedding https://arxiv.org/pdf/1911.01196.pdf より抜粋

GitHubに実装が公開されています。文ベクトルの出力オプションもありそうです。

github.com

$ ./src/jose
Parameters:
        -train <file> (mandatory argument)
                Use text data from <file> to train the model
        -word-output <file>
                Use <file> to save the resulting word vectors
        -context-output <file>
                Use <file> to save the resulting word context vectors
        -doc-output <file>
                Use <file> to save the resulting document vectors
        -size <int>
                Set size of word vectors; default is 100
        -window <int>
                Set max skip length between words; default is 5
        -sample <float>
                Set threshold for occurrence of words. Those that appear with higher frequency in the
                training data will be randomly down-sampled; default is 1e-3, useful range is (0, 1e-3)
        -negative <int>
                Number of negative examples; default is 2
        -threads <int>
                Use <int> threads; default is 20
        -margin <float>
                Margin used in loss function to separate positive samples from negative samples; default is 0.15
        -iter <int>
                Run more training iterations; default is 10
        -min-count <int>
                This will discard words that appear less than <int> times; default is 5
        -alpha <float>
                Set the starting learning rate; default is 0.04
        -debug <int>
                Set the debug mode (default = 2 = more info during training)
        -save-vocab <file>
                The vocabulary will be saved to <file>
        -read-vocab <file>
                The vocabulary will be read from <file>, not constructed from the training data
        -load-emb <file>
                The pretrained embeddings will be read from <file>

Examples:
./jose -train text.txt -word-output jose.txt -size 100 -margin 0.15 -window 5 -sample 1e-3 -negative 2 -iter 10

試行結果

30万件約20GBの特許データで学習させてみました。

単語ベクトルの類似結果を見てみます。

query: 自動車
---
('乗用車', 0.8404606580734253), 
('車両', 0.8378781080245972), 
('車輌', 0.7979249358177185), 
('自動二輪車', 0.7885137796401978), 
('自転車', 0.782609224319458), 
('オートバイ', 0.7789096236228943), 
('航空機', 0.7780036330223083), 
('電気自動車', 0.7770860195159912),
('二輪車', 0.7740814685821533),
('乗り物', 0.7717453837394714),
('車載', 0.7691519260406494),
('鉄道車両', 0.7605024576187134), 
('乗物', 0.7498664855957031)
...
]
query: プリンタ
----
[
('印刷装置', 0.8641186952590942),
('画像形成装置', 0.8083310723304749),
('印刷', 0.7867810726165771),
('プリント', 0.7860059142112732),
('MFP', 0.7771070599555969),
('画像形成', 0.7665582895278931),
('複写機', 0.7597976922988892),
('インクジエツト記録装置', 0.7596516609191895),
('画像形成部', 0.7595673203468323),
('スキヤナ', 0.7568787932395935),
...
]
query:  レーザ
[
('レーザ光', 0.7883974313735962),
('レーザビーム', 0.7772529721260071),
('フアイバーレーザ', 0.7631707191467285),
('CO2レーザ', 0.7576791048049927),
('レーザー装置', 0.7439086437225342),
('レーザー光', 0.7391970753669739),
('レーザービーム', 0.7351175546646118),
...
]
query: 携帯電話
-----
[
('スマートフオン', 0.9211865663528442),
('携帯情報端末', 0.8552143573760986),
('携帯電話機', 0.8257875442504883),
('テレビ', 0.8204030990600586),
('タブレツト端末', 0.8194489479064941),
('ノートパソコン', 0.8147341012954712),
('タブレツトPC', 0.8041720986366272),
('携帯', 0.7919098138809204),
('スマートウオツチ', 0.7867792844772339),
('スマートホン', 0.7841475009918213), 
...
]
[
query: アルコール
----
('グリセリン', 0.7986409664154053),
('エタノール', 0.7715713977813721),
('脂肪酸', 0.7600075006484985),
('エステル', 0.7566314935684204),
('エーテル', 0.7565040588378906),
('脂肪族アルコール', 0.7549535036087036),
('プロピレングリコール', 0.7479276061058044),
('多価アルコール', 0.7424640655517578),
('アルキルエーテル', 0.7266831994056702),
...
]

単語ベクトルとしては、それなりの結果がでているように見えますが、過去に試した他のWord embeddingsに比べると、感覚的には、若干いまいちのように感じます。(試したときの学習量の違いかもしれません)

また、文書ベクトルの類似結果を見てみます。今回は何も考えず、全文を入力させています。なお、特許の全文はかなり長いです。

query: 自動車 要約 課題 ポート噴射弁 筒内噴射弁 燃料 供給 する 燃料供給装置 振動 大きく なつ 音 発生 する の 抑制 する 解決 手段 燃料供給装置 燃料タンク 燃料タンク 燃料 ポート噴射弁 接続 さ れ 通路 供給 する ポンプ 通路 設け られ 逆止弁 通路 逆止弁 ポート噴射弁 側 燃料 加圧 し 筒内噴射弁 接続 さ れ 通路 供給 する ポンプ 有する ポート噴射弁 供給 する 燃料 燃圧 目標 燃圧 なる よう ポンプ 制御 する エンジン 運転開始時 目標 燃圧 所定 燃圧 設定 し その後 エンジン 回転数 燃料供給装置 共振 領域 外 なつ とき 目標 燃圧 所定 燃圧 低い 所定 燃圧 切り替える 選択 図 図3
----
0.8253768086433411, 自動車 要約 課題 エンジン ポート噴射弁 筒内噴射弁 燃料 供給 する 燃料供給装置 振動 し 音 発生 する の 抑制 する 解決 手段 燃料供給装置 燃料タンク 燃料タンク 燃料 ポート噴射弁 接続 さ れ 通路 供給 する ポンプ 通路 設け られ 逆止弁 通路 逆止弁 ポート噴射弁 側 燃料 加圧 し 筒内噴射弁 接続 さ れ 通路 供給 する ポンプ 有する ポート噴射弁 供給 する 燃料 目標 燃圧 基づく 目標回転数 ポンプ 回転 する よう ポンプ 制御 する もの 目標 燃圧 低下 応じ ポート噴射弁 供給 する 燃料 燃圧 ポート 側 燃圧 低下 し いる 際 ポート 側 燃圧 脈動 程度 所定 程度 以上 とき 所定 程度 未満 とき 目標回転数 大きく する 選択 図 図3...
0.8230206966400146,  ハイブリツド自動車 要約 課題 粒子状物質除去フイルタ 再生 行なう 機会 多く する 解決 手段 排気 系 粒子状物質 除去 する 粒子状物質除去フイルタ 有する エンジン 走行 用 >動力 出力 する モータ 所定 車速 未満 エンジン 間欠 運転 許可 し 運転者 要求 する 要求 パワー 走行 する よう エンジン モータ 制御 する 制御装置 備える ハイブリツド自動 車 粒子状物質除去フイルタ 粒子状物質 堆積量 堆積量 以上 推定 し とき 車速 所定 車速 小さい 所定 車速 以上 所定 車速 未満 状態 所定 時間 継続 し とき エンジン 間欠 運>転 禁止 する 選択 図 図2
0.8182553648948669, 車両用制御装置 要約 課題 モータ 温度 許容上限温度 超える こと 抑制 し モータ 走行 走行 する 機会 多く する 解決 手段 エンジン 停止 さ れ モータ 回転数 所定回転数 以下 モータ 出力 さ れる トルク 所定トルク 以上 状態 時間 以上 経過 し とき モータ モータ ロツク状態 判定 し 時間 長い 時間 以内 モータ モータ ロツク状態 判定 さ れ 回数 所定 回数 以上 なつ とき エンジン 始動 する これ モータ 温度 許容上限温度 超える こと 抑制 し モータ 走行 走行 する 機会 多く する こと できる 選択 図 図4 ...
query: プリンタ 要約 課題 同じ プリンタメカ 形成 さ れ 幅 異なる 記録 紙 対応 し プリンタ 各々 記録 紙 印刷 さ れ いる 黒 マーク 検出 する こと できる プリンタ 提供 する 解>決 手段 印字ヘツド 記録 紙 印字 なさ れる プリンタ 搬送 さ れる 前記 記録 紙 案内 する ガイド 前記 記録 紙 検出 する センサ 前記 センサ 実装 さ れる 基板 有し 前記 ガイド 前記 センサ 露出 さ せる ため 複数 穴 設け られ おり...
----
0.762130081653595,  電子機器 要約 課題 コスト プリント基板上 回路素子 発生 さ せる ノイズ 伝搬 効果 的 抑える こと できる 電子機器 提供 する 解決 手段 表面 グラウンドパターン 形成 さ れ プリント基板 プリント基板 表面 対向 する よう 配置 さ れる シールド部材 備える シールド部材 グラウンドパターン 対向 し プリント基板 側 突出 し 帯状 領域 有し 当該 帯>状 領域 内 設け られ 複数 ねじ 穴 それぞれ 通る ねじ プリント基板 締結 さ れ シールド部材
0.7610459327697754, 画像形成装置 要約 課題 発光素子 受光素子 迷光 抑制 し 発光素子 受光素子 配置 自由度 高める こと 目的 する 解決 手段 光センサ 被検知領域 光 出射 する 発光素子 被検知領域 反射 さ れ 光 受光 する 受光素子 被検知領域 拡散反射 さ れ 光 受光 する 受光素子 素子 設け られる 基板 備える 基板 被検知領域 対向 する 面 当該 面 被検知領域 反対 側 面 B 面 面 B 貫通 する 貫通 部 C 有する 素子 うち 2つ 素子 基板 面 配置 さ れ...
0.7596758604049683.  プリント 基板接続構造 要約 課題 実装 面積 極小 し プリント基板 間 任意 トポロジ 安定 接続 する こと できる プリント 基板接続構造 提供 する 解決 手段 プリント 基板接続構造 接触 型 コネクタ 接触 型 コネクタ 挟ん 配置 さ れ 接触 型 コネクタ 接続 さ れる プリント基板 接触 型 コネクタ 挿入 さ れ 接触 型 コネクタ 高さ 対応 する 厚み 有>する フレーム 有し いる 選択 図 図1 請求項 接触 型 コネクタ 前記 接触 型 コネクタ 挟ん 配置 さ れ 前記 接触 型 コネクタ 接続 さ れる プリント基板 前記 接触 型 コネクタ 挿入 さ れ 前記 接触 型 コネクタ 高さ 対応 する 厚み 有する フレーム 有する プリント 基板接続構造 請求項 前記 フレーム 

多少の類似性はとれていそうですが、長文として特徴を捉えられているかというと微妙な感じですね。もう少し検証が必要そうです。

おわりに

今回は時間がなかったのでテスト的に30万件20GBのデータで試しましたが、今後、1000万件以上、600GB以上の全特許データに適用させて、もうちょっとちゃんとした検証をしたいと思います。 現在、その他には、BERTの特徴量抽出ベースでの類似検索も検討しています。

検証して精度が出るようであれば、今後、私が個人で開発し、事業化した自社サービス https://patentfield.com に適用していきます。

弊社のPatentfieldのサービスでは、全文検索エンジンにGroongaを採用しており、ベクトル検索エンジンや機械学習エンジンも独自に内部に組み込んで、大量のデータであっても全てをメモリに乗せる必要なく、高速且つ柔軟に検索に組み合わせて利用できるようにしています。

Patentfieldでは、創業から3期が経過し、顧客法人数100社を超え、売上もだいぶ立ち上がってきました。来年はさらに加速度的に大きくしていきます。弊社での開発に興味があれば、お気軽にご連絡下さい。

お問合せ・お申込み | Patentfield

HerokuでWordPressを動かす方法

はじめに

WordPressはずいぶん前から流行っているPHP製のCMSで、ちょっとしたコーポレートサイトやブログサイトを非技術者でもある程度管理しやすいように作るにはいまだに便利です。

ただ、Ruby on RailsなどモダンなWeb開発手法に慣れていると、FTPでデプロイとかサーバー上のファイルを直接更新みたいなことはできるだけしたくないもんです。

2018年2月現在で、さくっとHerokuで動かせてGitHubで管理できるWordPress開発環境を構築する方法をまとめておきます。

なお、以下はmacOS Sierraでの作業手順です。

使えそうなものを探す

何事も何かを実装する前には、まず、GitHubで、最近の環境で、参考にできそうなもの、利用できそうなものを探します。

下記のものがよさげなので、こちらを使って作業を開始します。

GitHub - PhilippHeuer/wordpress-heroku: This project is a template for installing and running WordPress 4.9.x on Heroku.

WordPressをモダンな開発環境でいい感じにできる Bedrockっていうものがあるんだ、ふーんって思っておきます。

roots.io

ローカル開発環境構築

  • Composerのインストール
brew install homebrew/php/composer
  • MySQLのインストール
brew install mysql
mysql.server start
mysql_secure_installation # 適当にrootのパスワードを設定などする
sudo ln -s /usr/local/opt/mysql/homebrew.mxcl.mysql.plist /Library/LaunchAgents/
  • Redisのインストール
brew install redis
 ln -sfv /usr/local/opt/redis/*.plist ~/Library/LaunchAgents
 launchctl load ~/Library/LaunchAgents/homebrew.mxcl.redis.plist

基本的に以下を見てやればいいだけです。

https://github.com/PhilippHeuer/wordpress-heroku/wiki/Deployment

git clone https://github.com/PhilippHeuer/wordpress-heroku
cd wordpress-heroku
composer install
mysql -uroot -p

some_databaseは適当に変えます。

mysql > create database `some_database`;

https://roots.io/salts.htmlEnv Formatのキーをコピーして、.envというファイルに以下を設定します。 passwordsome_databaseは、適当に変えます。

# DB Connection
CUSTOM_DB_URL=mysql://root:password@127.0.0.1:3306/some_database

# Redis
REDIS_URL='redis://127.0.0.1:6379'

# WP Settings
WP_ENV=development
WP_HOME=http://localhost:8080
WP_SITEURL=${WP_HOME}/wp

# Generate your keys here: https://roots.io/salts.html
AUTH_KEY='generateme'
SECURE_AUTH_KEY='generateme'
LOGGED_IN_KEY='generateme'
NONCE_KEY='generateme'
AUTH_SALT='generateme'
SECURE_AUTH_SALT='generateme'
LOGGED_IN_SALT='generateme'
NONCE_SALT='generateme'
  • 起動

macOSでは80番ポート使うのにroot権限が必要そうだったので8080で立ち上げます。

php wp-cli.phar server --host=0.0.0.0 --port=8080 --path=web

http://localhost:8080にアクセスして、適当にサイト名やパスワードを入れるとローカルでwordpressの画面にアクセスできるようになります。

Herokuにデプロイ

Herokuのアプリを作成します。ダッシュボードからでも良いです。

heroku create ${APP_NAME}

上記と同じようにhttps://roots.io/salts.htmlからキーをコピーして、herokuの環境変数に設定します。

heroku config:set \
AUTH_KEY='generateme' \
SECURE_AUTH_KEY=''generateme \
LOGGED_IN_KEY='generateme' \
NONCE_KEY='generateme' \
AUTH_SALT='generateme' \
SECURE_AUTH_SALT='generateme' \
LOGGED_IN_SALT='generateme' \
NONCE_SALT='generateme' \
--app ${APP_NAME}

アドオンを追加していきます。

heroku addons:create sendgrid:starter --app ${APP_NAME}
heroku addons:create scheduler:standard --app ${APP_NAME}
heroku config:set DISABLE_WP_CRON='true' --app ${APP_NAME}
heroku addons:open scheduler --app ${APP_NAME}
heroku addons:create jawsdb:kitefin --app ${APP_NAME}
heroku addons:create papertrail:choklad --app ${APP_NAME}
heroku addons:create heroku-redis:hobby-dev --app ${APP_NAME}

Herokuのファイルシステムではdynoが再起動されると、更新されたファイルが消えます。そのため、画像などのメディアは、Amazon S3のクラウドストレージにアップロードさせます。S3へのアクセス権限を持つアクセスキーをAWS_S3_URLの環境変数に指定します。

AWS_S3_URLは、s3://${アクセスキー}:${シークレットキー}@s3-${リージョン}.amazonaws.com/${バケット名}の形式を想定しているようです。

2018年2月1日現在のソースでは、シークレットキーにスラッシュが含まれている場合、parseに失敗したので、例えば、 https://github.com/PhilippHeuer/wordpress-heroku/pull/27/files のようにして回避しました。*1

heroku config:set \
AWS_S3_URL='s3://${アクセスキー}:${シークレットキー}@s3-${リージョン}.amazonaws.com/${バケット名}' \
--app ${APP_NAME}

これでHeroku側の設定は終わったので、gitのremoteに登録してプッシュすれば、デプロイは完了です。

heroku git:remote -a ${APP_NAME}
git push heroku master

後は、https://${APP_NAME}.herokuapp.com/ にアクセスして、初期インストールすれば、データベースが構築されます。

この状態だとcloneしてきた元のリポジトリのままなので、適当に自分たちのアプリ用に管理しやすいように整えてGitHub管理しましょう。

あと、composerがとても遅いので以下などを参考にして整えたほうがいいと思います。

qiita.com

最後に

次はプラグインあさったり、独自テーマを作ったりしていこうと思います。

ところで、私は、知的財産の商業化に関するスタートアップ IP Nexus(https://www.ipnexus.com)に関連するプロジェクトや特許の検索・分析プラットフォーム(https://patentfield.com)の開発などをしています。

今回のようなWebっぽいことからデータベース、検索、言語処理や機械学習などオールラウンドにしていますが、もっと検索、言語処理や機械学習などの方の作業の比重を大きくしたいです。

ということで、Web開発を手伝ってくれる人がいたら嬉しいです。データ分析や機械学習の方に興味があるという方でも有りです。ただし、現状、Web開発の比重の方がかなり大きいです。

興味があれば、Twitter(@naoa_y)かメール(naoya at patentfield.com)までご連絡ください。

*1:なお、今思うとS3が独自ドメインだとパースできない気がしますが、まあ必要になったら適宜対応すればよさそうという感じです。

JSでWebに注釈をつけるAnnotatorで専用のサーバープログラムを使わなくてもannotationを保存、復元する方法

Webページにコメントなどの注釈をつけることができるJavascriptのライブラリannotatorがあります。

こちらの注釈の保存は、基本的には以下のPython製のバックエンドを利用することが想定されています。

https://github.com/openannotation/annotator-store

他には、ブラウザのローカルストレージに保存するプラグインもあります。 https://github.com/aron/annotator.offline.js

しかし、別サーバーを立てて管理はしたくなく、自前のWebサーバーでユーザーごとに紐付けて管理したいことがあると思います。

以下のようにannotationCreatedイベントのannotationからhighlightsのDOMを除外してどこかに保存し、@annotator.loadAnnotations(annotations)すれば、annotationを復元できそうだなぁってところまで調査しました。

    Annotator.Plugin.StoreLogger = (element) ->
      pluginInit: ->
        annotation = Cookies.get("annotator_test")
        if annotation?
          annotation = JSON.parse(annotation)
          @annotator.loadAnnotations([annotation])
        @annotator.subscribe('annotationCreated', (annotation) ->
          storable = jQuery.extend({}, annotation)
          delete storable.highlights
          Cookies.set("annotator_test", JSON.stringify(storable))
          console.info 'The annotation: %o has just been created!', annotation
        ).subscribe('annotationUpdated', (annotation) ->
          console.info 'The annotation: %o has just been updated!', annotation
        ).subscribe 'annotationDeleted', (annotation) ->
          console.info 'The annotation: %o has just been deleted!', annotation

    content = $('.target').annotator()
    content.annotator('addPlugin', 'StoreLogger')

後は適当に調整して、RailsにCRUD生やせば、ユーザーごとのannotationを管理できそうです。

が、デザインの変更やコンテンツの変更などでDOMがずれるとannotationを復元できなそうなので、今のところ、採用は見合わせることにしました。

一応のメモ書きで残しておきます。

Mroonga 7.06からMySQLのgenerated column/MariaDBのvirtual columnが利用可能に

全文検索エンジンGroongaMySQLストレージエンジンであるMroongaのソースをいじる機会があったので、ついでにMySQLのgenerated columnMariaDBvirtual column(computed column)の対応をしました。
次回リリースのMroonga 7.06からはgenerated columnを作ってそれに全文インデックスを使って高速に全文検索できるようになります。

MySQL5.7ではJSON型に対してFulltextインデックスを作るのが許可されていないのですが、generated columnJSON関数を使うことにより、JSONの中の特定の値に対して、全文検索を行うことができるようになります。

たとえば、JSON型のカラムにログを蓄積しておき、必要になったタイミングで特定の値のみをgenerated columnを作って全文検索を行ったりできます。 OAuthのAPI取得結果をJSONで入れておいて、後で必要になったら名前とかプロフィールを引っ張りだして検索するとか。

mysql> CREATE TABLE logs (
    ->   id INT,
    ->   record JSON,
    ->   message VARCHAR(255) GENERATED ALWAYS AS (json_extract(`record`, '$.message')) STORED,
    ->   FULLTEXT INDEX(message) comment 'tokenizer "TokenBigramSplitSymbolAlphaDigit"'
    -> ) ENGINE=Mroonga DEFAULT CHARSET=utf8mb4;
Query OK, 0 rows affected, 1 warning (0.01 sec)

mysql>
mysql> INSERT INTO logs(id, record) VALUES (1, '{"level": "info", "message": "start"}');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO logs(id, record) VALUES (2, '{"level": "info", "message": "restart"}');
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO logs(id, record) VALUES (3, '{"level": "warn", "message": "abort"}');
Query OK, 1 row affected (0.00 sec)

mysql>
mysql> SELECT * FROM logs WHERE MATCH(message) AGAINST("ar" IN BOOLEAN MODE);
+------+-----------------------------------------+-----------+
| id   | record                                  | message   |
+------+-----------------------------------------+-----------+
|    1 | {"level": "info", "message": "start"}   | "start"   |
|    2 | {"level": "info", "message": "restart"} | "restart" |
+------+-----------------------------------------+-----------+
2 rows in set (0.04 sec)

Inplace alter tableの対応もいれれたので、既存のテーブルに対しても追加するカラムに対する値のコピーの負荷のみでスキーマ変更ができます(ALTER TABLE ADD col GENERATED ALWAYS..で自動的に値はコピーされる)。

検索時に毎回関数を評価しなくていいように、2つの日付のうち、最先の日のカラムを作っておくとかもできるかな。

mysql> CREATE TABLE Docs (
    ->   id INT,
    ->   app_date DATE,
    ->   priority_date DATE,
    ->   earliest_date DATE GENERATED ALWAYS AS (LEAST(app_date,priority_date)) STORED,
    ->   INDEX(earliest_date)
    -> ) ENGINE=Mroonga DEFAULT CHARSET=utf8mb4;
Query OK, 0 rows affected (0.01 sec)

mysql>
mysql> INSERT INTO Docs(id, app_date, priority_date) VALUES (1, "2017-01-01", "2016-12-24");
Query OK, 1 row affected (0.00 sec)

mysql> INSERT INTO Docs(id, app_date, priority_date) VALUES (2, "2017-02-01", "2016-11-24");
Query OK, 1 row affected (0.00 sec)

mysql>
mysql> EXPLAIN SELECT * FROM Docs WHERE earliest_date > "2016-12-23";
+----+-------------+-------+------------+-------+---------------+---------------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type  | possible_keys | key           | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+-------+---------------+---------------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | Docs  | NULL       | range | earliest_date | earliest_date | 4       | NULL |    1 |   100.00 | Using where |
+----+-------------+-------+------------+-------+---------------+---------------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

mysql> SELECT * FROM Docs WHERE earliest_date > "2016-12-23";
+------+------------+---------------+---------------+
| id   | app_date   | priority_date | earliest_date |
+------+------------+---------------+---------------+
|    1 | 2017-01-01 | 2016-12-24    | 2016-12-24    |
+------+------------+---------------+---------------+
1 row in set (0.01 sec)

なお、MySQL5.7では、VIRTUALなgenerated columnには、Fulltextインデックスが許可されていないので、インデックスを作りたい場合は、 STOREDで作る必要があります。 MariaDBのInnoDBラッパーモードであれば、たぶんVIRTUALでもFulltextインデックスが作れると思います。 また、ストレージモードのVIRTUALカラムに対するインデックスは対応していません。

Mroongaを脱却してGroonga直接構成にしようと思ったりもしていましたが、MySQL Routerを使うと、mroonga_commandUDFでも向き先をちゃんと変更してくれたり、mroonga_commandのエスケープの問題も少し緩和されたようなので、まだしばらくMroonga構成で行こうと思っています。

特許の検索・分析サービスPatentfieldをリニューアルしました

はじめに

私は、2015年1月よりIP Nexusというスタートアップに所属しています。

仕事でPG書いたことがない人間が知財のWeb系のスタートアップに転職した話 - CreateField Blog

IP Nexusのメンバーは、投資銀行での経歴をもつ米国とドイツの知財訴訟弁護士や米国特許商標庁の元特許審査官の経歴をもつ弁護士など、知財に関する専門知識と知財専門家や投資家などとのグローバルなネットワークに強みを持っています。

そこで、IP Nexusは、2016年後半より大学や研究機関、個人発明家の知的財産である研究内容や発明(シーズ)を商業化、事業化につなげるお手伝いをはじめました。資金調達、法人化、商品開発などをハンズオンでお手伝いしています。

実際に、今、とある海外の個人発明家がもつ特許ポートフォリオをもとに、世界で商業化させるプロジェクトが走っており、現在、日本では京都大学のインキュベーション施設にオフィスを借りてオペレーションを開始しています。

このプロジェクトに注力するようになり、少しシステム開発に余力ができたため、元々私が個人で開発していた特許の検索サービスPatentfieldをフルリニューアルして、新たに事業として立ち上げることになりました。

独学で特許の全文検索サービスを開発しました - CreateField Blog

prtimes.jp

こちらは、基本的にシステム開発部分は私一人で8ヶ月ぐらいかけてリニューアルしました。

なぜやるか

特許権は、新規な技術の公開を代償に独占排他権を付与させるものですが、日本において公開された特許情報は一部の知財専門家以外にはあまり広く活用、認知されていないと感じています。

本来、公開技術情報はもっと使いたおされなければ、特許制度が産業の発達に寄与することはできず、むしろ阻害要因になるという考えさえあります。

たとえば、事業を行っていて、いきなり第三者からその機能は特許があるとイチャモンをつけられると、特許制度自体にとても悪いイメージを持つ事業者は多いのではないでしょうか。*1

現状、日本においては、公開技術情報の活用度合いと独占排他権のバランスが著しく悪いと考えています。 その関係を少しでも是正すべく、特許情報、発明情報の活用をより普及させることができる特許検索・分析ツール、プラットフォームを提供したいと考えています。

主な機能

Patentfieldでは、主に以下のような機能があります。

  • 最新の審査・審判経過情報を含む100種類以上の多様な検索項目と、ブーリアン検索、近傍検索、曖昧検索、前方一致検索など多様な検索手法による高速且つ柔軟な特許検索・分析
  • 機械学習を活用したセマンティックサーチ・類似検索
  • 出願人、被引用件数および特許分類など最大で120種類以上の特許データの属性情報を可視化
  • 40種類以上の特許審査・審判結果および経過情報によるカスタマイズ可能なパテントスコア
  • パテントスコアまたは出願件数による特許ランキング
  • 引用分析(サイテーションマップ)
  • 競合引用分析
  • Emailアラート
  • PDF一括ダウンロード
  • エクセルエクスポート

特許出願後の審査、審判手続きに基づいた絞込やスコアリング、集計など非常に高速かつ柔軟に検索・分析を行えます。

検索・分析機能は、すべてカラムストア機能付きの全文検索エンジンGroongaを拡張して利用しています。

曖昧検索や検索の高速化、バグ修正など一般的に利用できる部分は随時オープンソースとしてコントリビュートしました。

ミドルウェアの基礎的な部分のオープンソース開発に携わることにより、一部にとっては不利になる実装であっても 特許検索・分析のシチュエーションでは有利になるといった改修や機能拡張を、自分自身でC/C++で実装することができるようになりました。

セマンティックサーチ

Patentfieldでは、単純なキーワード検索の他にセマンティックサーチの機能も提供しています。

たとえば、以下の3つの文書は、人間が見れば、1.と3.の文書はほぼ同じ内容であり、2.の文書は他とは違うことが理解できます。 しかし、単純にそれぞれのキーワードに別の単語IDを割り振って、類似度を計算すると、1.の文書に対し、2.と3.の文書は同じ類似度になってしまいます。

  1. 情報処理装置/は/、/A/の/処理/を/行う
  2. 情報処理装置/は/、/B/の/処理/を/行う
  3. コンピュータ/は/、/A/の/処理/を/行う

セマンティックサーチでは、あらかじめ、機械学習によって「情報処理装置」と「コンピュータ」が同じぐらいの意味であることを学習させて、その学習結果にもとづき、類似検索を行います。 これにより、1.の文書に対しては、2.の文書よりも3.の文書のが似ているといった検索が可能となります。

この他、高速化など色々やっているのですが、それについては、そのうち解説するかもしれません。

今後について

収録国の拡充、UIの改善、検索精度・速度の改善、分析手法の拡充、知財訴訟データとの連携などたくさんやりたいことがあります。

現在は、京都大学 吉田キャンパス内にオフィスを借りて仕事をしており、つい先日、京都大学の学生さんのバイトを数名採用したところです。

デザイナーやエンジニアの方で特許や知財に関して興味がある方は、是非お気軽にお問い合わせ下さい。

*1:特にソフトウェア関係においては。

Groonga 6.0.2から多段ドリルダウンが利用可能に

GroongaはC/C++で書かれた国産の全文検索エンジンライブラリです。 サーバとしても組み込みのライブラリとしても利用することが可能です。

Groongaでは従来よりドリルダウン機能(ファセット)が提供されていましたが、 ドリルダウン機能の結果をつかってさらにドリルダウンするといったことはできませんでした。

Groonga6.0.2よりドリルダウン結果を使った多段のドリルダウンが利用できるようになりました。

これにより、たとえば、以下のようなユースケースで役に立つと思います。

  • タグのメタデータでのグループ
  • 大分類、中分類、小分類での段階的グループ

タグのメタデータのグループ結果

Groongaでは、以下のようにタグやカテゴリデータを別テーブルにして持つことができます。 この別テーブルにメタデータを追加で持たせることにより、さらに、そのメタデータで集計することができます。

たとえば、本の著者データに、著者の性別や、年齢、住所などを持たせて、それごとに集計することができます。

table_create Authors TABLE_PAT_KEY ShortText
[[0,0.0,0.0],true]
column_create Authors sex COLUMN_SCALAR ShortText
[[0,0.0,0.0],true]
table_create Books TABLE_HASH_KEY ShortText
[[0,0.0,0.0],true]
column_create Books authors COLUMN_VECTOR Authors
[[0,0.0,0.0],true]
load --table Books
[
{"_key": "Hello Groonga", "authors": ["Taro", "Hanako"]},
{"_key": "The first step for Groonga", "authors": ["Taro"]},
{"_key": "Mastering Groonga", "authors": ["Taro", "Hanako"]}
]
[[0,0.0,0.0],3]
load --table Authors
[
{"_key": "Taro", "sex": "Male"},
{"_key": "Hanako", "sex": "Female"}
]
[[0,0.0,0.0],2]
select Books \
  --drilldown[authors].keys authors \
  --drilldown[authors].output_columns _key,_nsubrecs \
  --drilldown[sex].table authors \
  --drilldown[sex].keys sex \
  --drilldown[sex].output_columns _key,_nsubrecs
[
  [
    0,
    0.0,
    0.0
  ],
  [
    [
      [
        3
      ],
      [
        [
          "_id",
          "UInt32"
        ],
        [
          "_key",
          "ShortText"
        ],
        [
          "authors",
          "Authors"
        ]
      ],
      [
        1,
        "Hello Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ],
      [
        2,
        "The first step for Groonga",
        [
          "Taro"
        ]
      ],
      [
        3,
        "Mastering Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ]
    ],
    {
      "authors": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "Taro",
          3
        ],
        [
          "Hanako",
          2
        ]
      ],
      "sex": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "Male",
          1
        ],
        [
          "Female",
          1
        ]
      ]
    }
  ]
]

メタデータを他のテーブルにして一元管理できて便利ですね。

大分類、中分類、小分類でのグループ

たとえば、日本->東京->新宿区など、階層的な分類を行うことができます。

table_create Addresses TABLE_PAT_KEY ShortText
[[0,0.0,0.0],true]
column_create Addresses country COLUMN_SCALAR ShortText
[[0,0.0,0.0],true]
table_create Authors TABLE_PAT_KEY ShortText
[[0,0.0,0.0],true]
column_create Authors address COLUMN_SCALAR Addresses
[[0,0.0,0.0],true]
table_create Books TABLE_HASH_KEY ShortText
[[0,0.0,0.0],true]
column_create Books authors COLUMN_VECTOR Authors
[[0,0.0,0.0],true]
load --table Books
[
{"_key": "Hello Groonga", "authors": ["Taro", "Hanako"]},
{"_key": "The first step for Groonga", "authors": ["Taro"]},
{"_key": "Mastering Groonga", "authors": ["Taro", "Hanako"]}
]
[[0,0.0,0.0],3]
load --table Authors
[
{"_key": "Taro", "address": "日本東京都"},
{"_key": "Hanako", "address": "アメリカニューヨーク州"}
]
[[0,0.0,0.0],2]
load --table Addresses
[
{"_key": "日本東京都", "country": "日本"},
{"_key": "アメリカニューヨーク州", "country": "アメリカ"}
]
[[0,0.0,0.0],2]
select Books \
  --drilldown[authors].keys authors \
  --drilldown[authors].output_columns _key,_nsubrecs \
  --drilldown[address].table authors \
  --drilldown[address].keys address \
  --drilldown[address].output_columns _key,_nsubrecs \
  --drilldown[country].table address \
  --drilldown[country].keys country \
  --drilldown[country].output_columns _key,_nsubrecs
[
  [
    0,
    0.0,
    0.0
  ],
  [
    [
      [
        3
      ],
      [
        [
          "_id",
          "UInt32"
        ],
        [
          "_key",
          "ShortText"
        ],
        [
          "authors",
          "Authors"
        ]
      ],
      [
        1,
        "Hello Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ],
      [
        2,
        "The first step for Groonga",
        [
          "Taro"
        ]
      ],
      [
        3,
        "Mastering Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ]
    ],
    {
      "authors": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "Taro",
          3
        ],
        [
          "Hanako",
          2
        ]
      ],
      "address": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "日本東京都",
          1
        ],
        [
          "アメリカニューヨーク州",
          1
        ]
      ],
      "country": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "日本",
          1
        ],
        [
          "アメリカ",
          1
        ]
      ]
    }
  ]
]

全てのレコードでグループ

これはオマケですが、今までレコード単一でしか、グループできませんでしたが、全てのレコードでグループすることができるようになりました。

私は円グラフを書くためにベクターカラムのグループ結果のレコード数の総数が欲しくてこの機能をつくりました。

table_create Authors TABLE_PAT_KEY ShortText
[[0,0.0,0.0],true]
column_create Authors sex COLUMN_SCALAR ShortText
[[0,0.0,0.0],true]
table_create Books TABLE_HASH_KEY ShortText
[[0,0.0,0.0],true]
column_create Books authors COLUMN_VECTOR Authors
[[0,0.0,0.0],true]
load --table Books
[
{"_key": "Hello Groonga", "authors": ["Taro", "Hanako"]},
{"_key": "The first step for Groonga", "authors": ["Taro"]},
{"_key": "Mastering Groonga", "authors": ["Taro", "Hanako"]}
]
[[0,0.0,0.0],3]
load --table Authors
[
{"_key": "Taro", "sex": "Male"},
{"_key": "Hanako", "sex": "Female"}
]
[[0,0.0,0.0],2]
select Books \
  --drilldown[authors].keys authors \
  --drilldown[authors].output_columns _key,_nsubrecs \
  --drilldown[authors_sum].table authors \
  --drilldown[authors_sum].output_columns _key,_sum \
  --drilldown[authors_sum].calc_target _nsubrecs \
  --drilldown[authors_sum].calc_types SUM
[
  [
    0,
    0.0,
    0.0
  ],
  [
    [
      [
        3
      ],
      [
        [
          "_id",
          "UInt32"
        ],
        [
          "_key",
          "ShortText"
        ],
        [
          "authors",
          "Authors"
        ]
      ],
      [
        1,
        "Hello Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ],
      [
        2,
        "The first step for Groonga",
        [
          "Taro"
        ]
      ],
      [
        3,
        "Mastering Groonga",
        [
          "Taro",
          "Hanako"
        ]
      ]
    ],
    {
      "authors": [
        [
          2
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_nsubrecs",
            "Int32"
          ]
        ],
        [
          "Taro",
          3
        ],
        [
          "Hanako",
          2
        ]
      ],
      "authors_sum": [
        [
          1
        ],
        [
          [
            "_key",
            "ShortText"
          ],
          [
            "_sum",
            "Int64"
          ]
        ],
        [
          "_all",
          5
        ]
      ]
    }
  ]
]

おわりに

多段のドリルダウンについて紹介しました。

今後は、フィルター結果でのドリルダウンや、レンジなどで集計できたりすると、さらに集計の幅が広がりそうでよさそうですね。

Groongaのパトリシアトライを使って高速なあいまい検索を実装した

はじめに

あいまい検索はたとえば、編集距離を求めることによって実現することができます。

レーベンシュタイン距離(レーベンシュタインきょり、英: Levenshtein distance)は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離(へんしゅうきょり、英: edit distance)とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。

レーベンシュタイン距離 - Wikipedia

最もベーシックな動的計画法によって編集距離を求める場合、計算量はO(nm)であり、レコード郡から編集距離が近いものだけを列挙する場合、さらにレコード数分の比較が必要になり計算量がとても大きくなってしまいます。

文字列の比較自体は、ビット演算を用いることによりそこそこ高速化できますが*1、この場合でもレコード数に対しては線形的に演算量が増えてしまいます。

色々調べていると、トライの構造を利用することにより、結構簡単に演算量を抑えられることがわかりました。 Fast and Easy Levenshtein distance using a Trie

そこで、この方法を全文検索エンジンGroongaのパトリシアトライで使えるようにして、高速なあいまい検索を実装してみました。

pat: Add grn_pat_fuzzy_search() by naoa · Pull Request #460 · groonga/groonga · GitHub

fuzzy_search関数(Groonga 6.0.0から)

fuzzy_search(column, query,
{"max_distance": 1, 
 "prefix_length": 0,
 "max_expansion": 0,
 "with_transposition": true}
)

{}は省略可能

  • option
property description default
max_distance 抽出する最大編集距離、これが小さいほど高速化が見込める 1
prefix_length 共通接頭辞の文字数、これを増やすとかなりの高速化が見込める 0
max_expansion 最大拡張数、文字数が短い場合などでキーが増えすぎるの抑制できる 0
with_transposition 文字の並び替えをコスト1として計算する false

パトリアトライを使って高速なあいまい検索をする場合、対象のカラムにTABLE_PAT_KEYのインデックスを張るか、TABLE_PAT_KEY_keyである必要があります。インデックスがない場合は、シーケンシャルにレコードごとに編集距離を求めます。

ユースケース

名称や住所など表記ゆれが含まれやすいケースであいまいにマッチさせることができます。

> select companies --filter 'fuzzy_search(_key, "MICROSOFT")' 
  --output_columns '_key,_score' --output_pretty yes
[
  [
    0,
    1456591234.55597,
    0.0919983386993408
  ],
  [
    [
      [
        14
      ],
      [
        [
          "_key",
          "ShortText"
        ],
        [
          "_score",
          "Int32"
        ]
      ],
      [
        "MICROSOFT",
        2
      ],
      [
        "MICCROSOFT",
        1
      ],
      [
        "MICOSOFT",
        1
      ],
      [
        "MICDROSOFT",
        1
      ],
      ...
    ]
  ]
]

スコアは最大編集距離 - 実際の編集距離 + 1です。完全に一致したものは最大編集距離+1、最も遠いものが1になります。他のマッチングスコアとなじませるために編集距離と大小関係を逆転させています。

高速化のポイント

高速化の主要なポイントは以下の2つです。

  1. できるだけ同じ接頭辞の部分の計算結果を使い回す
  2. 求めたい最大編集距離のパラメータを渡すことにより、最大編集距離以下にならないことが確定した時点でその子ノードの探索、編集距離演算をスキップする

共通接頭辞の演算結果使い回し

動的計画法では、2つの文字列をマトリックスのx軸とy軸にマッピングし、行ごとに

  • 左隣+1(挿入)
  • 上+1(削除)
  • 左斜め上+1(置換)
  • 左斜め上と等しい場合、左斜め上+0

の最小値を計算していって最後に最も右下の値をとりだすことにより、編集距離を計算できます。

入力keyがdateでパトリシアトライのキーがdataだとすると以下のようにして1が求められます。

d a t e
0 1 2 3 4
d 1 0 1 2 3
a 2 1 0 1 2
t 3 2 1 0 1
a 4 3 2 1 1

パトリシアトライでは辞書順にキーを取り出すことができます。dataの次がdatabだったすると以下のようにして2が求められます。

d a t e
0 1 2 3 4
d 1 0 1 2 3
a 2 1 0 1 2
t 3 2 1 0 1
a 4 3 2 1 1
b 5 4 3 2 2

ここで、dataまでの1~4行は上の表と同じでまったく変更が必要ありません。そのため、この途中の行の計算結果を使い回すことができます。 これで5行の計算から1行の計算だけに抑えることができます。*2

最大編集距離以上になる子ノードの枝刈り

パトリシアトライでは各ノードが共通の接頭辞でまとめられており、子ノードの編集距離は概ね親ノードの編集距離より大きくなります。

https://upload.wikimedia.org/wikipedia/commons/a/ae/Patricia_trie.svg

基数木 - Wikipedia

具体的には動的計画法では1行ごとに左隣、上、斜めだけしか見てないということから、子ノードの編集距離が親ノードの最終行の最小値未満になることはありません。そこで、求めたい最大編集距離のパラメータを渡すことにより、子ノードの探索をがっつりとやめることができます。*3

例えば、最大編集距離1が与えられた場合、上記のようにdatabで最終行の最小値は2ですので、次にどんな文字が来ようと、編集距離は1にはなり得ません。

さらにdatabaやdatabaseという子ノードがあっても、これらの探索、編集距離の演算をスキップすることができます。

これらにより、特にmax_distanceが十分に小さい範囲ではとても高速に編集距離が近いキーが列挙できます。

実験結果

日本語wikipediaのタイトル30万件と実際に使っている英語DBの全文検索用の語彙表でキー数が1785万件(これは多すぎでもうちょっと丁寧にトークンをフィルターすべきな気がしますが)でmax_distanceと文字数を変化させた実行時間を以下に示します。 それぞれ100件の実行時間の平均値で単位は秒(sec)です。

比較対象として、レコードごとに動的計画法で同じものを求めた結果(edit max_d=1)を示しています。

  • CPU Intel(R) Xeon(R) CPU E5620 @ 2.40GHz

日本語wikipediaタイトル キー数30万件

image 1

n_chars pat max_d=1 pat max_d=2 pat max_d=3 pat max_d=5 pat max_d=10 edit max_d=1
1 0.0372 0.066 0.0818 0.117 0.1312 0.1691
5 0.0801 0.1269 0.1703 0.2084 0.2328 0.52
10 0.1282 0.2465 0.2705 0.3091 0.381 0.9158
20 0.2055 0.3312 0.4291 0.5307 0.5319 1.6355
30 0.3007 0.4634 0.5278 0.6064 0.6419 2.3025

English lexicon キー数1785万件

image 2

n_chars pat max_d=1 pat max_d=2 pat max_d=3 pat max_d=5 pat max_d=10 edit max_d=1
1 0.012 0.028 0.233 2.099 6.334 13.712
5 0.007 0.103 0.782 3.62 11.075 44.911
10 0.021 0.171 1.168 6.293 16.482 80.639
20 0.01 0.149 1.701 10.762 32.621 152.047
30 0.019 0.23 2.674 15.95 53.588 223.545

max_distanceが1や2では、枝刈りがかなり効いて文字数やキー数が増えても実行時間が大きく増えないことがわかります。

日本語の方がキー数が大分すくないのにmax_distance=1や2のときに時間がかかっているのは、日本語の方が文字種が多いからだと思われます。英語だとアルファベットと記号、数字ぐらいしか使われていません。

max_distanceが大きく、キー数が増えすぎると結構遅くなってしまうので、最初にprefixで絞れるオプションも入れています。prefix_lengthを1だけでもいれるとキー数1785万件、文字数10、max_distanceが5で1.5sec(prefix_length=0の場合、11sec)ぐらいで求めることができました。

参考

http://stevehanov.ca/blog/index.php?id=114 https://murilo.wordpress.com/2011/02/01/fast-and-easy-levenshtein-distance-using-a-trie-in-c/

*1:ビットパラレルを使ってGroongaで高速な編集距離関数の検証 - CreateField Blog

*2:1文字ごとにノードを構成する単純なトライであれば、1つ前の最後の1行だけを保持しておくだけで実装することもできます。パトリシアトライでは複数文字単位で遷移しちゃうのでマトリックスを保持しています。

*3:枝刈りの条件をもう少し厳しくできる気がしているのですが、今のところうまい方法は思いついていません。