Unified ranking with entropy-weighted information for phrase-based semantic auto-completion

Patent metadata

Field	Value
Publication number	US-9582608-B2
Application number	US-201414298720-A
Country	US
Kind code	B2
Filing date	Jun 6, 2014
Priority date	Jun 7, 2013
Publication date	Feb 28, 2017
Grant date	Feb 28, 2017

Abstract

Methods, systems, and computer-readable media related to a technique for combining two or more aspects of predictive information for auto-completion of user input, in particular, user commands directed to an intelligent digital assistant. Specifically, predictive information based on (1) usage frequency, (2) usage recency, and (3) semantic information encapsulated in an ontology (e.g., a network of domains) implemented by the digital assistant, are integrated in a balanced and sensible way within a unified framework, such that a consistent ranking of all completion candidates across all domains may be achieved. Auto-completions are selected and presented based on the unified ranking of all completion candidates.

First claim

What is claimed:

1. A method of providing cross-domain semantic ranking of complete input phrases for a digital assistant, comprising:
receiving a training corpus comprising a collection of complete input phrases that span a plurality of semantically distinct domains;
for each of a plurality of distinct words present in the collection of complete input phrases, calculating a respective word indexing power across the plurality of domains based on a respective normalized entropy for said word, wherein the respective normalized entropy is based on a total number of domains in which said word appears and how representative said word is for each of the plurality of domains;
for each complete input phrase in the collection of complete input phrases, calculating a respective phrase indexing power across the plurality of domains based on an aggregation of the respective word indexing powers of all constituent words of said complete input phrase;
obtaining respective domain-specific usage frequencies of the complete input phrases in the training corpus; and
generating a cross-domain ranking of the collection of complete input phrases based at least on the respective phrase indexing powers of the complete input phrases and the respective domain-specific usage frequencies of the complete input phrases.

2. The method of claim 1 , further comprising:
providing the cross-domain ranking of the collection of complete input phrases to a user device, wherein the user device presents one or more auto-completion candidates in response to an initial user input in accordance with at least the cross-domain ranking of the collection of complete input phrases.

3. The method of claim 1 , wherein calculating the respective word indexing power across the plurality of domains for each word w i of the plurality of distinct words further comprises:
calculating the respective normalized entropy ε i ; for the word w i based on a respective formula

ɛ
i

=

-

1

log
⁢

⁢
K

⁢

∑

k
=
1

K

⁢

⁢

c

i
,
k

t
i

⁢
log
⁢

c

i
,
k

t
i

,

wherein K is a total number of domains in the plurality of domains, c i,k is a total number of times w i occurs in a domain d k of the plurality of domains, and t i =Σ k c i,k is a total number of times w i occurs in the collection of complete input phrases, and wherein the respective word indexing power of the word w i is (1−ε i ).

4. The method of claim 1 , wherein calculating the respective phrase indexing power across the plurality of domains for each complete input phrase P j of the collection of complete input phrases further comprises:
distinguishing template words from normal words in the complete input phrase P j , a template word being a word that is used to represent a respective category of normal words in a particular complete input phrase and that is substituted by one or more normal words when provided as an input to the digital assistant by a user;
calculating the respective phrase indexing power, for the complete input phrase P j based on a respective formula

μ

j
⁢

=

b
T

⁢

n
T

⁡

(
j
)

+

1

n
N

⁡

(
j
)

+

n
T

⁡

(
j
)

⁡

[

∑

i
=
1

n
N

⁡

(
j
)

⁢

⁢

(

1
-

ɛ
i

)

Assignees

• Apple Inc

Inventors

• Bellegarda Jerome R

Classifications

• G06F40/274

  Converting codes to words; Guess-ahead of partial word inputs · CPC title

• G06F16/90324 Primary

  using system suggestions · CPC title

• G06F40/242

  Dictionaries · CPC title

• G06F40/30

  Semantic analysis · CPC title

• G06F40/253

  Grammatical analysis; Style critique · CPC title