Beyond query expansion論文

タイトル

Beyond query expansion - expanding documents for fluid keyword search

Beyond query expansion - expanding documents for flexible search

Beyond query expansion - augmenting documents for fluid keyword search

Beyond query expansion - augmenting documents for flexible search

Beyond query expansion - information retrieval by document expansion

Document expansion - beyond query expansion

Beyond query expansion - making everything searchable

Beyond query expansion - making everything easily accessible

Beyond query expansion - making documents searchable

コマンドラインのヘルプではなく、キーワード検索全般に関係する話にする

IUI2021@テキサス 10/2締切(abstract) あたりを狙う?

本締切は10/9

https://new.precisionconference.com/iui21a/author/subs/1258

SIGIR2020は開催が7月末だった / 締切は12月ぐらい?

query expansionという言葉を使うならこちらの方が良い

Abstract

Although intelligent text search algorithms are widely available these days, documents are still hard to find in many cases. It is usually hard to find useful information in help systems and manual pages, even when required information exists in the documents.

Searches fail mainly because of the "vocabulary problem," where users cannot find the right search keyword. When a user wants to "remove a file," and there is a manual entry for "deleting a file," users may not be able to know how to remove a file until he finds the right keyword "delete" for the search.

To solve the problem, various query expansion techniques are widely used on the Web. When a user types "remove" in the search box, the system automatically expands the keyword and suggests using "remove/delete" instead. Query expansion works effectively for simple cases, but it does not work well when the concept in the users' mind is very different from the text in the manual document. For example, if a user wants to "clean up the desktop," he cannot find an appropriate manual entry that only describes how to "delete icons" or "align icons" on the desktop.

We propose a new approach document expansion for finding help documents and manual entries. We provide flexible explanations for each document using regular expression patterns. For the above example, we give an expression like (delete|remove) (a file|data) and use the expanded text like delete a file, remove data for keyword search. Also, a pattern like (delete|remove) #{file} is expanded to delete Makefile, delete search.c, etc. depending on the existing files, so that a user can enter del ma to get delete Makefile and immediately execute it.

We have been using this document expansion technique called ExpandHelp for several years, and the system is working on various commercial Web services. In this paper, we describe the idea and implementation of ExpandHelp and show how it works in the wild.

異なる言語でもだいじょうぶ!

Translation paradigm

概要

ExpandSearchを提案する

検索対象をいろいろExpandすることによってうまく検索できるようにするシステム

Introduction

People are frequently searching information using keywords on Google and other systems, but keyword search is still not an easy task, because it is fundamentally difficulto to find appropriate information that does not contain the keyword given by the user.

Webでもパソコンでも情報検索はキーワード検索が主流だが、キーワード検索は昔も今も難しい

根本的に、本文に含まれていない文字列の検索が難しいからである

On the help system of MacOS Catalina (v10.15.5), we cannot tell how to remove a file

https://gyazo.com/eaa80e41ddc3d3620fae133007274573

We can find how to set the clock, but the user has to know that setting the clock and changing date is the same thing.

https://gyazo.com/0cd679128d8f69eb2a8a966d6466a8a4

We can find information on Google because...

For example we can find how to XXXX by using YYYY, because somebody on the net has written an article on XXXX using the keyword YYYY.

Googleとかで意外とみつかる気がするのは、Web上のメジャーな情報はいろんな人がいろんな言葉で情報をアップしてるからだろう (出典)

機能を検索したとき、トップに出るのはメーカーのサイトではない

情報が無いからではなく、キーワードがマッチしないからだと思われる

We can find the information on XXXX because XXXX is fairly popular, but finding information of less popular things is more difficult.

メジャーじゃないシステムや特殊な状況のヘルプなどの場合、文書もユーザも少ないから苦労する

キーワードが少しでも違うとみつからない

開発者の用語とユーザの用語が違うことの違いの問題がさらにひどい

When we want to find the user's console of Google Chrome extension, we cannot find it on Google search, because the official name of the feature is "Google dashboard."

e.g. メジャーじゃないxxxxxシステムのyyyyy機能

Google Chrome Extensionのconsoleとかみつからない (dashboardだとみつかる)

(他の例も)

FAQs provided by service providers are not usually considered useful because the terms used by the people on the service are usually different from the word that user can think of.

いわゆるFAQは大抵不十分(出典)

特殊なサービスの特殊な機能について書かれてることが多いからだろう

メジャーなサービスであっても、ググって本家FAQが出てくることなど無い

誰かが言い替えたものがヒットするのが普通 (出典)

Even finding the users' old documents can be sometimes difficult, because people might want to use different keywords for the same thing. He might try to find a file on "ZZZ" and fail, because he used the term "WWW" instead before.

自分のメモですら後でみつけられなくて困ることも多い

微妙に利用単語が違うとみつからない

良いファイル名をつけたつもりでも後から検索できないことがある

Various techniques have been proposed to solve this vocabulary problem.

But not very successful.

母語が違うときはさらに大変である

頭の中の単語を英語に変換する必要がある

常にTranslationや言い替えが必要だといっていいだろう

(いったん文書がみつかれば、それを理解することはできるが、そもそもみつけるのが難しいのである)

クエリや検索技術を工夫して解決しようとする方法が多い

原文はいじれないから

いろんな言い回しで検索する研究は大昔からある

If the system knows that removing a file and deleting a file is the same, the system can try to find something using the keyword "delete", even when the user specified the keyword "remove".

シソーラスを使うことがすぐ考えられる

This kind of technique is called Query expansion, and simle query expansion is possible if proper dictionary is provided.

Query Expansion

クエリに工夫する方法

シソーラス的検索の一般化

検索対象の本文は変わらないから不十分

クエリだけ拡張してもしょうがない

本文に固有名詞的なものが少ない場合はみつけにくい

e.g. 「良い論文を書く方法」「査読を通す方法」「インパクトある論文を書く方法」

「レビュワーを説得する技術」 vs 「良い論文を書く方法」

ユーザが指定するあらゆるキーワードを拡張するのは不可能である

John F. Kennedy

翻訳してから検索するのも一種のQUery Expansionである

日本語を入力すると英語のWikipediaがみつかることもある => これは違う原理

Query expansion is effective when simple substitution of keywords are satisfactory enough.

Using 'delete' in addition to 'remove' works...

However, it does not work for finding a document for vague topics.

For example, if you want to find a document that describes "how to write a good paper",

you will have little chance finding a document related to the topic.

Maybe it would be better to use keywords like "how to persuade reviewers".

However, expanding a phrase like "write a good paper" to "persude reviewers" is impossible.

別の言い替え文書(Tipsとか逆引き辞典)を用意

便利だがメジャーなものに限られる

もと文書と全然違うところで作り直しは大変すぎるが、逆引き本は売れている

hands-on と言うのだろうか?

ちょっと違う

handbook かな?

firsthand

Similarly,

When we want to find a library function of a programming language, query expansion does not work.

For example, when we want to write a poker game and want to select five cards from the deck,

what library should we use?

you want to selet randomly two items from an array in Ruby,

you can use the sample() method.

However, "randomly selecting items" and "sample" are so different, it is very hard for users to

find the method unless the manual contains words like "randomly select"

「配列からランダムに要素をふたつ取得」 = a.sample(2)

sampleという単語はなかなか出てこないのではないか

pick upとかselectとかchooseとか言ってしまいそう

It is even more difficult if the user wants to find information that is not easily described with keywords.

When a user wants to know what the icons on the Mac desktop mean, he might want to to

search by saying "What is the symbol with three curved lines wifi.icon on my computer display?

(folding fan, two black 90-degree arcs above a black circcle)

特殊な言葉が使われていない場合は検索が難しい

「Macの画面の上の方の宇宙船みたいな記号」では駄目

「メニューバーの音声アイコン」だとみつかるかもしれないが

他の言語の場合でも同じである

原文を拡張する感じにして、簡潔なインタフェースを用意して任意のキーワードを使えるのが良い

There should be better way to make everything more searchable by casual computer users.

Solutions

To solve the vocabulary problem, we propose the combination of three techniques.

1. Using ExpandSearch

The main idea for solving the problem is

providing regular expressions (REs) for each document so that a wide variety of user queries can match one of the expanded strings.

When we want to provide a manual that describes how to delete a file,

we provide a RE like (delete|remove) (a file|data)

and generate all the text that match this RE.

In this case, we can epand this RE into delete a file, delete data, remove a file and remove data.

and use all these strings for the search.

Users can find this document by using fleible query like delete file or remove data.

We can add descriptions in other languages, like (ファイル|データ)を(消す|(消去|削除)する)

A user can use a phrase like 'ファイルを消去する' to find the manual page.

2. Approximate pattern matching

People make spelling errors all the time, and approximate pattern matching algorithm works quite effectively for almost all search activities.

Using the ExpandHelp algorithm, all the expressions are expanded in advance,

so simple approximate pattern matching algorithms can be applied for the search.

For example, a query like del dta can be used

3. Document expansion by users

As we have shown before, one of the big reasons why we fail to find a document is that

the user's search keyword does not exist in the document.

Providing entries for ExpandHelp can solve the problem, but

If the author of the does not provide the data, it would be nice if other users can add

the ExpandHelp entries.

This strategy is very similar to writing a hands-on document for an existing document,

but adding ExpandHelp entries is much easier than authoring a document from scratch.

Examples

Helpfeel services

We have been applying ExpahdSearch for various customer support services on existing Web services.

The help system based on ExpandSearch is called Helpfeel, and

Helpfeel is a FAQ engine that supports users who do not have enough vocabulary for the Web services they want to use.

(ここでどこかのサポートシステムを示す)

Figure xxx shows an example Helpfeel page that supports finding FAQs for PayPay Free market run by Yahoo! Japan.

We provide the description on the Scrapbox wiki service,

https://paypayfleamarket.yahoo.co.jp/help/

https://gyazo.com/3d964512606a5e25646104a738ab104e

HelpLine

Some Unix command line tools have many options and features, and difficult to understand in many cases.

Many programmers are recently using the git version control system, but the concept of git is difficult, and

the command line options are extremely complicated.

The total number of git manuals on unix is .....

We created the GitHelp system using ExpandHelp, so that git users can easily

remember command options and use it without perfectly remembering the git commands.

HelpLine

HelpLine is

for Cmd line

for omnibox

OmniHelp

OmniHelp is an implementation of ExpandHelp that runs on Chrome browser.

The URL window on Chrome is called omnibox,

Implementation

解決策

解決策1: 展開ヘルプで徹底的に拡張/曖昧検索

検索対象側で、いろんなクエリに対応できるような工夫をしておく

あらゆるクエリにマッチするように、いろんな表現を用意しておく

Query をExpandするわけではなく、あらゆるQueryに対応できるように本文をExpandする

本文になければ、いくらQueryをExpandしてもみつからないから

クエリパタンで(dashboard|console) などと指定するのではなく、本文に両方書いておく

RegExpによる展開とAsearchによる曖昧検索

いろんな表現を用意しておけばいろんな表現で検索できるのはあたりまえだが、用意する手間は減らせる

解決策2: ユーザが勝手に検索対象をExpandする

逆引き辞典式

既存のキーワード検索インタフェースをユーザが拡張する

自分で登録 (scrapbox, 拡張機能)

consoleでも検索できるようにする

自分のデータには記述するし、他人のデータにも記述する

これらをExpandSearchと呼ぶ

フツーの検索システムの上に皮をかぶせる形で実装する

ExpandSearchの実例

まず実例を紹介する。実装はあとで。評価実験にもなっている。

実例1 ExpandHelpの実際の利用

ScrapboxというWiki上にいろんな表現を用意しておく

Helpfeel

PayPayフリマなどですごく効率があがった

実際これによりヘルプ問い合わせは劇的に減る (出典: Helpfeel)

実例2 検索インタフェースの融合

マイHelpfeel

検索をひとつの方法に統合する

検索方法が複数だと面倒臭い

ググって出なければ逆引き辞典を検索する、みたいなのは面倒

同じ検索インタフェースでいろんなところを探すほうが簡単である

どこにメモしたか忘れて困ることがなくなる

自分のデータが増えていく状況のグラフを書ける!

実例3

gitのヘルプ - コマンドラインで動くもの

パラメタを指定して実行につなげることすらできる

実装

ExpandHelpのアルゴリズム

正規表現の拡張とパラメタ代入

HelpLineの実装

omniboxを利用するとか

考察 Discussions

検索システムを選んでから検索キーワードを入力するのに慣れてしまっている

この必要がないことを知ると驚きがある

検索されやすいように工夫するとか馬鹿げてると思うかもしれないか、ググって出なきゃ無いのと同じだということを考えると、ある程度工夫することは意味があるし、自分が後でさがすときにも役に立つわけである

ゲームのように記述を増やす工夫もできるかもしれない

タイトルに迷ったら両方書くみたいな

どこにある情報でもひとつのインタフェースでみつかるのは強烈に嬉しい

説得ポイント

ExpandHelp

自分が入力したキーワードが検索結果に出現する嬉しさ

検索方法の統合

ヘルプシステムの実績