{"id":13703,"date":"2021-06-14T12:15:02","date_gmt":"2021-06-14T19:15:02","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/cse\/?p=13703"},"modified":"2021-06-15T11:29:16","modified_gmt":"2021-06-15T18:29:16","slug":"entity-disambiguation-using-search-engine","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/ise\/entity-disambiguation-using-search-engine\/","title":{"rendered":"Entity Disambiguation Using Search Engine"},"content":{"rendered":"

Background<\/span>\u00a0<\/span><\/h3>\n

Entity disambiguation or resolving misspelled\/ambiguous tokens has always been an interesting subject with its own challenges. With the rise of digital assistant devices such as Microsoft Cortana, Google Home, Amazon Alexa etc., the overall accuracy of the device has become important. The communication quality with a device contains the capability to understand huma<\/span>n\u2019s<\/span>\u00a0intent, distinguishing correct entities with their correct spelling form and finally fulfilling the human\u2019s request with an appropriate response.\u00a0 Similarly, with the challenges in optical character recognition (OCR) results the best recognition results can only be achieved if the source image is of decent quality<\/span>.\u00a0<\/span><\/b>\u00a0<\/span><\/p>\n

Challenges and Objectives<\/span>\u00a0<\/span><\/h3>\n

A common challenge when mapping an entity name from a document (electronic or scanned), a written or a transcribed spoken sentence to its canonical form in a system of record, is in handling variations in spelling, spelling mistakes, errors due to OCR transcription of a poor-quality scan, or differences in entity form between a transcription of speech to the canonical form. These variations require sub-token matching, word breaking or collation of sib-tokens to increase the likelihood of matching when searching for the most relevant canonical form of the entity.<\/span>\u00a0<\/span><\/p>\n

Having misspelled entities\u00a0means\u00a0we may not be able to fulfill the initial speech request. Therefore, either we should resolve the misspelled entities to their correct form, before attempting to query a data source or we should prepare the target data source to fulfill the queries with misspelled entities with\u00a0a higher\u00a0accuracy rate.<\/span>\u00a0<\/span><\/p>\n

Solution<\/span>\u00a0<\/span><\/h3>\n

This document proposes a methodology to disambiguate misspelled entities by comparing the search retrieval performance with different custom search analyzers in a search engine. Hence, even if the query provided contains some misspelled entities, the search engine can respond to the request with higher precision and recall than the default settings. This method can be applied to any search engine service capable of adding custom search analyzers.\u00a0<\/span>\u00a0<\/span><\/p>\n

In this document we experiment with a speech-to-text scenario. Similar approaches can be applied to OCR and any machine entity extraction system. The implemented solution can be found in EntityDisambiguation <\/a><\/span>repository.<\/span>\u00a0<\/span>\u00a0<\/span><\/p>\n

Architecture\u00a0deep-dive<\/span>\u00a0<\/span><\/h3>\n

In this section, we will discuss the motivation behind the proposed solution. Consider a speech-to-text scenario where a user is interacting with a device and asking to make a phone call.\u00a0The figure below indicates the overall architecture\u00a0from\u00a0the\u00a0user speech,\u00a0to searching\u00a0the data source and responding\u00a0to the user\u2019s request.<\/span>\u00a0<\/span><\/p>\n

\u00a0<\/span>User: Hey device, call\u202f\u201cJ<\/span>ea<\/span><\/b>n\u202fH<\/span>e<\/span><\/b>ng\u201d\u202f\u00a0<\/span>\u00a0<\/span><\/p>\n

Device: Sorry I cannot find \u201cJ<\/span>oh<\/span><\/b>n\u202fH<\/span>a<\/span><\/b>ng\u201d\u202f<\/span><\/p>\n

\"Image<\/a><\/p>\n

The speech is converted to text and then it will be sent to a natural language understanding service such as LUIS. We assume that our LUIS (Language Understanding Intelligent Service) model is trained well, and we will expect that it can identify the intent and extract the entities. It can identify that \u201ccall Jea<\/strong>n He<\/strong>ng\u201d is a \u201ccall\u201d intent with an accuracy score of 0.88. It also can identify that \u201cJea<\/strong>n He<\/strong>ng\u201d part of this query is a \u201cpersonName\u201d. However, when we query the search engine for \u201cJea<\/strong>n He<\/strong>ng\u201d, it\u2019s possible to miss to retrieve this record from the data source since what exists in the search index is \u201cJoh<\/strong>n Ha<\/strong>ng\u201d and not \u201cJea<\/strong>n He<\/strong>ng\u201d.<\/span>\u00a0<\/span><\/p>\n

{\r\n  \"query\": \"call jean hang\",\r\n  \"topScoringIntent\": {\r\n    \"intent\": \"Call\",\r\n    \"score\": 0.8851808\r\n  },\r\n  \"intents\": [\r\n    {\r\n      \"intent\": \"Call\",\r\n      \"score\": 0.8851808\r\n    },\r\n    {\r\n      \"intent\": \"None\",\r\n      \"score\": 0.07000262\r\n    }\r\n  ],\r\n  \"entities\": [\r\n    {\r\n      \"entity\": \"jean heng\",\r\n      \"type\": \"builtin.personName\",\r\n      \"startIndex\": 5,\r\n      \"endIndex\": 13\r\n    }\r\n  ]\r\n}<\/pre>\n
Sample response from LUIS. Intent can be <\/span>identified<\/span>\u00a0with high confidence (0.88)<\/span>\u00a0and the entity\u00a0<\/span>is<\/span>\u00a0a\u00a0<\/span>personName<\/span>. However, as the name is misspelled, when we query our DataSource (search engine) the name cannot be\u00a0<\/span>found.<\/span><\/span>\u00a0<\/span><\/p>\n
Methodology<\/span>\u00a0<\/span><\/h3>\n
This section presents an overview of the proposed methodology to improve the research retrieval for misspelled entities namely personName. Different search analyzers<\/a> benefit from different tokenizers and token filters. A tokenizer<\/a><\/span>\u00a0divides the continuous text into a sequence of tokens, such as breaking a sentence into words and a token filter is used to filter out or modify the tokens generated by a tokenizer<\/span>. Hence, different search analyzers may behave differently, and their performance may\u00a0vary to misspelled person\u2019s names. Our approach is to measure the performance of the search engine in the retrieval of the misspelled\u00a0person’s name\u00a0when the search engine uses specific or multi-search analyzers.\u00a0 We begin by\u00a0creating a search index using different search analyzers. Then we will\u00a0ingest the\u00a0person\u2019s\u00a0name into the created search index.\u00a0<\/span>\u00a0<\/span><\/p>\n
\u00a0<\/span><\/p>\n
Analysis of the\u00a0Search\u00a0Index\u00a0Schema\u00a0<\/span>\u00a0<\/span><\/h3>\n
In this section we will be creating a search schema for our search index. We first started by identifying several search analyzers<\/a><\/span>. Then we will identify the fields of the search index needed in this experiment.<\/span>\u00a0<\/span><\/p>\n
Analyzers\u00a0<\/span>\u00a0<\/span><\/h3>\n
An analyzer is a component of the full-<\/span>\u00a0<\/span>text search engine responsible for processing text in query strings and indexed documents. Different analyzers manipulate text in diverse ways depending on the scenario. By default, Azure search uses Standard Lucene<\/a> for both parsing the records\/documents as well as parsing a query. We will be creating several custom search analyzers that we think may be the best candidates for the experiment.<\/span>\u00a0<\/span><\/p>\n
\u00a0<\/span>In the next section, we will run our experiments by sending a query to the search index for all the combinations of the created search analyzers to verify which analyzer can improve the name retrieval.\u00a0Most of the custom analyzers\u00a0benefit\u00a0from\u00a0case-folding<\/a><\/span>\u00a0to resolve similar terms\u00a0that have\u00a0different case\u00a0folding. Additionally, they use\u00a0ASCI\u00a0folding<\/a> to convert numeric, alphabetic and symbolic\u00a0Unicode\u00a0characters to\u00a0ASCII\u00a0representation of that token.\u00a0Analyze REST API<\/a><\/span>\u00a0can be used to verify how each\u00a0<\/span>analyzer\u00a0analyzes<\/span>\u00a0text. In this document, we chose\u00a0`Person Name`\u00a0as our experimented entity and we are creating Search Analyzers in the subsequent section.<\/span>\u00a0<\/span><\/p>\n
In our experiment we used the following search analyzers<\/span>: Phonetic<\/a>, Edge-N-Gram<\/a>, Microsoft<\/a>, Letter<\/a>, CamelCase, URL-Email<\/a> and default Analyzer (Standard Lucene<\/a>).<\/span>\u00a0<\/span><\/p>\n
Search\u00a0Index Fields<\/span>\u00a0<\/span><\/h3>\n
Now that we have created our search analyzers, we will create our search index. We will be adding several fields, each of them corresponding to a search analyzer. The following table represents the fields added to the search index.<\/span>\u00a0<\/span><\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n
Field\u202f<\/span>\u00a0<\/span>\u00a0<\/span><\/td>\nAnalyzer\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
phonetic\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nphonetic-analyzer\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
edge_n_gram\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nedge-n-gram-analyzer\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
microsoft\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nEn.microsoft\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
letter\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nletter-analyzer\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
ngram\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nngram-analyzer\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
camelcase\u202f\u00a0<\/span>\u00a0<\/span><\/td>\ncamel-case-pattern-analyzer\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
stemming\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nstemming-analyzer\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
url_email\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nurl-email-analyzer\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
standard_lucene\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nstandard.lucene\u202f<\/span>\u00a0<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
<\/pre>\n
Data Ingestion<\/span>\u00a0<\/span>\u00a0<\/span><\/h3>\n
We used\u00a0the\u00a0midterm election\u00a0candidates search results\u00a0dataset<\/a><\/span>\u00a0and ingested 400 names into the search index. For every record,\u202fa\u202fname\u202fwas added to every field.\u202fHowever,\u202ffor\u00a0every\u202ffield\u202fwe specified a\u202fdifferent\u202fanalyzer.\u00a0The\u00a0JSON (Java Script Object Notation)\u00a0shown below\u00a0is<\/span>\u00a0<\/span>result of\u202fa search to the search index with the query:\u00a0\u201cJean Heng\u201d.\u202fThe data\u00a0ingested\u00a0into the search index will be used in the next section to verify the search retrieval precision and recall for different analyzers.<\/span>\u00a0<\/span><\/p>\n
{\r\n  \"@search.score\": 4.589165,\r\n  \"stndard_lucene\": \"Jean Heng\",\r\n  \"phonetic\": \"Jean Heng\",\r\n  \"edge_n_gram\": \"Jean Heng\",\r\n  \"letter\": \"Jean Heng\",\r\n  \"ngram\": \"Jean Heng\",\r\n  \"camelcase\": \"Jean Heng\",\r\n  \"steming\": \"Jean Heng\",\r\n  \"url_email\": \"Jean Heng\",\r\n  \"text_microsoft\": \"Jean Heng\"\r\n}<\/pre>\n
Experiment<\/span>\u00a0<\/span><\/h3>\n
In the previous section, we created a search index with 400 names in the index.\u202fIn this section<\/span>,<\/span>\u00a0we will run some experiments to measure the\u00a0highest\u00a0performing\u00a0analyzer(s) for the name field.\u202fWe can hopefully\u00a0improve the search\u202fretrieval,\u00a0even for misspelled names such as \u201cJoh<\/strong>n Ha<\/strong>ng\u201d\u00a0we\u00a0should be able to\u00a0retrieve \u201cJea<\/strong>n He<\/strong>ng\u201d from the search engine<\/span>.\u202f<\/span>\u00a0<\/span><\/p>\n
Measuring the retrieval performance\u00a0<\/span>\u00a0<\/span><\/h3>\n
To measure the search accuracy, we need to know how the search engine\u202fcan retrieve a search result if a misspelled name is passed as a\u202fquery; it is\u202fimportant\u202ffor us that the\u202fretrieved\u202fresult is accurate.\u202fThe following table contains the confusion matrix measures we will need to\u202fcalculate\u00a0the\u202fsearch performance<\/span>.<\/span>\u00a0<\/span><\/p>\n\n\n\n\n\n\n
TP\u00a0<\/span>\u00a0<\/span><\/td>\nTrue\u202fPositive\u00a0<\/span>\u00a0<\/span><\/td>\nGiven a misspelled name is searched,<\/span>\u00a0<\/span><\/p>\n
a\u00a0name\u202fis\u00a0found\u202fand it matches the expected\u00a0name.\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
FP\u00a0<\/span>\u00a0<\/span><\/td>\nFalse\u202fPositive\u00a0<\/span>\u00a0<\/span><\/td>\nGiven a misspelled name is\u202fsearched,<\/span>\u00a0<\/span><\/p>\n
a\u00a0name\u00a0is\u00a0found but it does not match the expected\u202fname.\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
TN\u00a0<\/span>\u00a0<\/span><\/td>\nTrue Negative\u00a0<\/span>\u00a0<\/span><\/td>\nGiven a non-existent\u202fname is searched,\u202fno name\u202fis\u00a0found.\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
FN\u00a0<\/span>\u00a0<\/span><\/td>\nFalse Negative\u00a0<\/span>\u00a0<\/span><\/td>\nGiven a misspelled name is searched,\u202fno name\u00a0is\u00a0found.<\/span>\u00a0<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\nWith\u00a0<\/span>TP, FP, TN and FN\u00a0<\/span>defined,\u00a0<\/span>we can calculate both recall and precision<\/span><\/span>\u00a0using the following formulas<\/span>:<\/span><\/span>\u00a0<\/span><\/span><\/p>\n
\"Image<\/a>
Precision (top) and Recall (bottom) formulas<\/figcaption><\/figure><\/p>\n
Since both precision and recall are crucial factors of the search retrieval, we will be using<\/span>\u00a0the<\/span>\u00a0F1 score which takes both precision and recall measures into account. The F1 score is the harmonic meaning of the precision and recall, where an F1 score reaches its best value at 1 (perfect precision and recall) and worst at 0. The following formula is how\u00a0<\/span>we calculate<\/span>\u00a0the F1 score<\/span>.<\/span><\/span>\u00a0<\/span><\/p>\n
\"Image<\/a>
F1 Score formula<\/figcaption><\/figure><\/p>\n
Misspelled\u00a0Names and Expected\u00a0Names<\/span>\u00a0<\/span><\/h3>\n
In the previous section, we ingested 400 names into our search engine. In this section<\/span>,<\/span>\u00a0we will create a dataset having 450 {misspelled, expected} tuples. The first 400 tuples\u00a0corresponded\u00a0to those existing in our search index. The last 50 tuples do not exist in our search index and will be used to have\u00a0impact\u00a0on TN (true negative) measures of the experiment.<\/span>\u00a0<\/span><\/p>\n
\u00a0<\/span><\/p>\n
Generate Misspelled\u00a0Names<\/span>\u00a0<\/span><\/h3>\n
The most accurate method to generate misspelled names is to use telemetry data<\/span>19<\/span>\u00a0from the system you are working with. For instance, find what was not correctly spelled in the logs and capturing them to be used for the experiment. If you do not have access to telemetry data\u00a0to create misspelled names, you can use\u00a0the\u00a0Azure speech-to-text\u00a0API.\u00a0The following algorithm illustrates a flowchart on how to generate a dataset of misspelled and expected names from a corpus of the names using speech to text API.<\/span>\u00a0<\/span><\/p>\n
Begin \r\n\r\nmisspelled_nams     empty list \r\n\r\nexpected_names      empty list \r\n\r\nnames               names_corpus \r\n\r\nWhile more data is needed for the experiment, do \r\n\r\n      Call speech API providing a name from names \r\n\r\n      If the response from API is equal to the correct name \r\n\r\n                 Continue \r\n\r\n      Else \r\n\r\n                 Insert misspelled name into misspelled_nams \r\n\r\n                 Insert correct name into expected_names \r\n\r\nEnd<\/pre>\n
Finally, we will make a dataset of names<\/span>, l<\/span>ike<\/span><\/span>\u202f<\/span><\/span>in the\u00a0<\/span>table\u202f<\/span>below,\u00a0<\/span>where the first 400 records in the expected name column\u00a0<\/span>are\u00a0<\/span>ingested in<\/span>to<\/span><\/span>\u00a0<\/span><\/span>A<\/span>zure\u00a0<\/span>S<\/span>earch<\/span><\/span>\u00a0<\/span>(<\/span><\/span>as discussed in\u00a0<\/span>the previous<\/span>\u00a0section<\/span><\/span>)<\/span>.<\/span><\/span>\u00a0<\/span><\/p>\n\n\n\n\n\n\n\n\n\n\n
#\u202f<\/span>\u00a0<\/span>\u00a0<\/span><\/td>\nExpected\u00a0name\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nMisspelled\u202fname\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
1\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nTobye\u202fSchimpke\u202f\u00a0<\/span>\u00a0<\/span><\/td>\ntobe\u202fshimpok\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
2\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nSidney\u202fMcElree\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nSidney Mc. Elree\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
…\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
400\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nKimmie Fridlington\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nKim Fridlington\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
401\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nNOT_FOUND\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nNetta Niezen\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
…\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n\u202f\u00a0<\/span>\u00a0<\/span><\/td>\n<\/tr>\n
450\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nNOT_FOUND\u202f\u00a0<\/span>\u00a0<\/span><\/td>\nAluin\u00a0Donnett\u202f<\/span>\u00a0<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
 <\/p>\n
Feature\u00a0Selection<\/span>\u00a0<\/span><\/h3>\n
Having 9 different\u00a0fields,\u00a0each of them using different analyzers\u00a0without considering the empty<\/span>\u202f<\/span><\/b>set,\u00a0we\u202fwill have\u202f511\u202fcombinations\u00a0of the fields to query against in our experiment.\u202fWe also have\u00a0\u00a0\u00a0400\u202fdocuments\u202fin our search engine. To\u202fcover all possible\u00a0scenarios,\u00a0we should make 400\u202f\u00d7 511 = 204,400 calls to the\u00a0Azure\u00a0Search.\u202f\u202fWe can also use\u202fone of the\u202ffeature elimination\u202ftechniques [5]\u202fto speed up experiment execution time.\u202fFor\u202finstance,\u202fwe can run our experiment in several phases.\u202fIn each phase<\/span>,<\/span> we will\u202fremove fields where their F1 score is significantly lower than in other fields.\u202fAs we run our experiment, we will remove more subsets of the fields set.\u202fUsing a superset of all the fields with 511 subsets, or any feature\u202felimination\u202ftechnique, we will have a list of features\u202fwith each element containing field(s)\u202f(e.g., features = [\u201cngram\u201d, \u201cphonetic,\u202fngram\u201d, \u2026.\u201dphonetic,\u202fngram,\u202fstemming\u201d\u202f\u2026\u202f]<\/span>\u202f\u202f\u00a0<\/span><\/b>\u00a0<\/span><\/p>\n
\u00a0<\/span><\/p>\n
F1 Scores Calculation<\/span>\u00a0<\/span><\/h3>\n
Having a dataset of\u202f`missplled_names`,\u202f`expected_names`\u202f(created in section\u202f4.2.1) and\u202f<\/span>a list\u00a0<\/span>of features (created in previous section),\u00a0now we can calculate the F1 Score for each of those features.\u202fFor every feature in\u202fthe list\u202fof features and for every\u202f`misspelled_name`\u202fin\u202four\u202fdataset, we will do the following steps:<\/span>\u00a0<\/span><\/p>\n
    \n
  1. S<\/span>end a query to our\u00a0<\/span>search\u00a0<\/span>index\u00a0<\/span>with the following payload:<\/span><\/span>\n
    {\r\n  \"queryType\": \"full\",\r\n  \"search\": \"MISSPELLED NAME\",\r\n  \"searchFields\": \"FEATURE\/S\"\r\n}<\/pre>\n<\/li>\n
  2. Take the response having the most ranking and\u00a0<\/span>c<\/span>ompare it against<\/span>\u00a0<\/span>the\u202fcorresponding\u202f<\/span>`<\/span>expected_name<\/span>`<\/span><\/li>\n
  3. Mark the result based on the\u00a0<\/span>following<\/span>:\u202f\u00a0<\/span><\/span>\u00a0<\/span>\n