FILE HISTORY
`US 6,757,718
`
`6,757,718
`PATENT:
`INVENTORS: Halverson, Christine
`Julia, Luc
`Voutsas, Dimitris
`Cheyer, Adam
`
`TITLE:
`
`Mobile navigation of network-based
`electronic information using spoken input
`
`APPLICATION
`NO:
`FILED:
`ISSUED:
`
`US2000608872A
`
`30 JUN 2000
`29 JUN 2004
`
`COMPILED:
`
`23 MAR 2018
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 1
`
`

`

`UTILITY Patent Appi
`~ OIP:.P.ATENT-DATiE.
`
`l.,
`
`..
`
`k NED
`
`O.
`
`I . a __
`
`i .. -
`
`EXA4MINER
`
`j
`
`...
`
`PTO-2040
`12/99
`
`O9.!OS~92
`
`I b
`
`+
`
`*
`
`. +:.'1
`
`
`
`+" :::
`
`.. lii( V
`
`I
`
`:,=
`
`3
`
`sUiII CLASSIFICATION
`
`1'1
`
`NOTICE OF ALLOWANCE MAILED
`
`S . 1 ' "
`- '
`"
`
`.. : .,'. .+
`W:ARNING:
`t'e"
`
`information disclosed herein may be restricted Unauthorized disclosure.may be prohibited by the United States Code 'itle 35, Sections 122, 18'1 and368.
`.m.Ie
`Possession outside the U.S. Patent & Trademark Office Is restricted to authorized employees and contractors only.
`
`..
`
`' - -
`
`-
`
`-
`
`-
`
`.
`
`.
`
`1 "
`
`Form PTO-436A
`(Rev. 6199)
`
`FILED WITH: F] DISK (CRF) F" FICHE E] CD-ROM
`(Attached in pocket on right inside flap)
`
`ISSUE
`
`E IN FILE
`
`',,.
`
`(FACE)
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 2
`
`

`

`6,757,718
`
`MOBILE NAVIGATION OF NETWORK-BASED ELECTRONIC
`INFORMATION USING SPOKEN INPUT
`
`Transaction History
`
`
`
`Transaction Description
`Date
`Preliminary Amendment
`06-30-2000
`Preliminary Amendment
`06-30-2000
`Initial Exam Team nn
`06-30-2000
`IFW Scan & PACR Auto Security Review
`07-24-2000
`08-31-2000 Correspondence Address Change
`09-01-2000 Notice Mailed--Application Incomplete--Filing Date Assigned
`11-15-2000 Application Dispatched from OIPE
`11-15-2000 Application Is Now Complete
`11-30-2000 Case Docketed to Examiner in GAU
`03-05-2001 Case Docketed to Examiner in GAU
`04-20-2001 Non-Final Rejection
`04-24-2001 Mail Non-Final Rejection
`04-30-2001
`Information Disclosure Statement (IDS) Filed
`04-30-2001
`Information Disclosure Statement (IDS) Filed
`05-21-2001 Correspondence Address Change
`09-21-2001 Response after Non-Final Action
`10-01-2001 Date Forwarded to Examiner
`10-01-2001 Change in Power of Attorney (May Include Associate POA)
`10-01-2001 Correspondence Address Change
`10-01-2001 Change in Power of Attorney (May Include Associate POA)
`10-09-2001
`Final Rejection
`10-10-2001 Mail Final Rejection (PTOL - 326)
`01-08-2002 Examiner Interview Summary Record (PTOL - 413)
`01-10-2002 Response after Final Action
`01-16-2002 Mail Examiner Interview Summary (PTOL - 413)
`01-17-2002 Date Forwarded to Examiner
`01-28-2002 Mail Advisory Action (PTOL - 303)
`01-28-2002 Advisory Action (PTOL-303)
`02-08-2002 Request for Continued Examination (RCE)
`02-08-2002 Request for Extension of Time - Granted
`02-08-2002 Workflow - Request for RCE - Begin
`02-11-2002 Date Forwarded to Examiner
`02-11-2002 Disposal for a RCE / CPA / R129
`02-19-2002 Mail Non-Final Rejection
`02-19-2002 Non-Final Rejection
`03-26-2002 Case Docketed to Examiner in GAU
`03-28-2002 Case Docketed to Examiner in GAU
`07-18-2002 Date Forwarded to Examiner
`07-18-2002 Response after Non-Final Action
`07-18-2002 Request for Extension of Time - Granted
`07-29-2002
`Information Disclosure Statement (IDS) Filed
`07-29-2002
`Information Disclosure Statement (IDS) Filed
`09-05-2002 Case Docketed to Examiner in GAU
`10-01-2002 Non-Final Rejection
`10-04-2002 Mail Non-Final Rejection
`12-23-2002 Examiner Interview Summary Record (PTOL - 413)
`01-06-2003 Response after Non-Final Action
`01-08-2003 Date Forwarded to Examiner
`01-09-2003 Mail Examiner Interview Summary (PTOL - 413)
`03-10-2003
`Formal Drawings Required
`03-10-2003 Notice of Allowance Data Verification Completed
`03-10-2003 Case Docketed to Examiner in GAU
`03-11-2003 Mail Notice of Allowance
`03-11-2003 Mail Formal Drawings Required
`03-13-2003 Dispatch to Publications
`05-06-2003
`Issue Fee Payment Verified
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 3
`
`

`

`05-06-2003 Workflow - Drawings Finished
`05-06-2003 Workflow - Drawings Matched with File at Contractor
`05-06-2003 Workflow - Drawings Received at Contractor
`05-06-2003 Workflow - Drawings Sent to Contractor
`05-06-2003
`Issue Fee Payment Received
`03-25-2004 Workflow - File Sent to Contractor
`03-25-2004 Receipt into Pubs
`03-25-2004 Receipt into Pubs
`03-29-2004 Receipt into Pubs
`05-03-2004 Receipt into Pubs
`05-27-2004 Application Is Considered Ready for Issue
`06-01-2004 Receipt into Pubs
`06-10-2004
`Issue Notification Mailed
`06-29-2004 Recordation of Patent Grant Mailed
`06-29-2004
`Patent Issue Date Used in PTA Calculation
`08-16-2006 ENTITY STATUS SET TO UNDISCOUNTED (INITIAL DEFAULT SETTING OR
`STATUS CHANGE)
`File Marked Found
`04-05-2016
`File Marked Found
`01-18-2017
`File Marked Found
`04-12-2017
`File Marked Found
`06-20-2017
`File Marked Found
`06-21-2017
`File Marked Found
`09-20-2017
`File Marked Found
`09-22-2017
`Petition Requesting Trial
`12-20-2017
`Petition Requesting Trial
`12-21-2017
`Petition Requesting Trial
`01-12-2018
`02-20-2018 Correspondence Address Change
`
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 4
`
`

`

`PATET APPLICATION
`~0960872
`
`I
`
`E>
`
`*
`
`,~~~
`
`COTENTS
`Date Rec ve
`
`or
`
`.
`
`.
`
`n A I ation
`
`papers.4
`
`INITIAL
`
`II
`
`INIL
`
`Date Received
`(Inci. C. of v)
`or
`Date Mailed
`
`~~4
`
`cj
`~~
`
`I~~-~ 52. _
`-
`_______ ~~53. _________
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`...j.~
`.__._._.__._._._.
`
`.O
`
`5.
`
`A
`
`~
`
`__
`
`____
`
`________
`
`n ~~ ~AA.A,~~Ii~4~/'
`
`__U_
`
`__________________
`
`0.
`61. ______________
`
`__
`
`_
`
`I~i~k~~ ~m~u 962.
`
`__
`
`..
`
`6.
`
`-.
`
`%rL
`
`70.
`
`-
`
`.
`
`71. 6. ___________
`
`K.
`
`_ _ _ __ _ _ _-
`
`__
`
`_ __ _ _ __ _ __ _ _
`
`73._
`
`74.
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`.
`
`_
`
`.4
`
`.
`
`. ~~~~75.__
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`___
`
`_ _ _ _ _
`
`______ 78._
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`__________
`
`__________
`
`.
`
`.*
`
`79._
`
`80. _
`
`81 . .
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`-: ..
`
`.
`
`.(LEFT
`
`~~~~~..82.__
`OUTSIDE)*
`
`.. ~.
`
`_ _
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`_
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 5
`
`

`

`•ISSUE SLIP STAPLE AREA (for additional cross referenes)
`
`POSITION
`
`INITIALS
`
`ID NO.-
`
`DATE
`
`I..
`
`N-
`*1' * *I
`
`FEE DETERMINATION
`O.I.P.E. CLASSIFIER
`FORMALITY REVIEW
`RESPONSE FORMALITY REVIEW,
`
`.jj
`
`.
`
`j
`
`I z i___
`/
`7 T
`)
`
`"
`
`'
`
`j.,,t
`
`____________
`
`,C
`v)t'
`
`INDEX OF CLAIMS
`Non-elected
`N
`.......... Rejected
`'
`Interference
`
`.w........ d
`= 1 .....
`.................................
`Appeal
`(Through numeral)... Cance.6l,-:.
`A .................................
`O bjected
`0 .....................
`-...........
`R estricte:d"
`.................................
`
`-
`
`IClaiml . '.
`
`Date
`
`Claim
`
`Date
`
`102
`103
`104
`105
`
`106
`
`108
`
`109
`110
`111
`
`112
`113
`114
`115
`116
`117
`118
`119
`120
`121
`i22
`123
`124
`125
`126
`127
`1281
`11291
`130
`131
`I32
`13,
`13.
`
`1
`1_1_1
`
`13,
`137
`
`138
`
`1
`
`139
`140
`141
`142
`143
`144-
`
`145
`
`146:1 ii
`
`14 7
`
`14
`
`41
`
`I
`
`j
`
`,
`
`3.
`
`5
`
`.4; 59
`• '-60.-
`
`.p61
`
`.".
`
`"
`
`. 63.
`
`6
`
`* 3 67
`S68
`If 69
`1 70
`
`(1 72
`t( q73
`07s
`
`9A. 76
`77
`
`;*79.
`-380.
`I " '81
`
`84
`
`86-1
`
`87
`•88
`89
`
`, ' .
`
`_
`
`1 11
`
`90
`91,
`921
`931
`941
`1 11
`951- 1 1
`961
`
`9 8 ''
`991
`
`" '
`
`If more than 150 claims or 10 actions
`staple additional sheet here
`
`(LEFT INSIOE).
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 6
`
`

`

`
`
`«4‘1"
`
`:39
`
`it
`
`K'.
`
`A ll .
`
`(RIGHT OUTSIDE)
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 7
`
`

`

`&~~-
`
`2
`
`March 12, 2003
`
`Dear Mr. Jean,
`
`Attached please find the results of your search request for application #09/608,872. I searched
`Dialog's foreign patent files, technical databases, product announcement files and general files.-
`
`Please let me know if you have any questions.
`
`Regards,
`
`4B30/308-7800
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 8
`
`

`

`Results
`
`Rulshttp://portal.acmorg/results.cfmn?coUlct' &d=ACM&CFII)=347231I8&CFI'OKEN=3300
`
`> login
`> home > about > feedback
`US Patent & Trademark Office
`
`Nothing Found
`
`Your search for [receiving and spoken and request and mobile and information
`and portable and remote control<AND>((journal<IN> pubtype) )] did not
`return any results.
`
`You can try to rerun it within the Portal.
`
`You may revise it and try your search again below or click advanced search for
`more options.
`
`i
`and mobile and information and
`i
`portable and remote
`control<AND>(.(journal<IN> pubtype) i
`
`£
`
`within thFoundcarct
`l[Advanced Search] [Search
`
`Hetp/Tips]
`
`Co..r:plet.e Search~ .Help anid Tips
`
`....
`
`. I
`
`signifythsar of a
`
`Thee chracendatxroenbcuete dlmtdtkn hs r
`
`................................................................
`...........................
`
`the........
`. . . . .............................
`."..
`
`....
`
`
`
`................ . . . .
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 9
`
`

`

`WVEST Refine Search
`
`http://westbrs:8002/bi/cgi-bin/PreSear
`
`Set Name Ouerv
`side by side
`DB=USPTPGPB,JPAB,EPABDWPI, TDBD; PLUR= YES," OP=ADJ
`network same navigation and (mobile or portable) and (spech or
`spoken) same request$3
`network same navigation and (mobile or portable) near3 appliance and
`(speech or spoken) same request
`
`L3
`
`Li
`
`network same navigation and (mobile or portable) near3 appliance and
`(speech or spoken) near4 request
`
`Hit Count. Set Name
`tesult set
`
`56
`
`2
`
`1
`
`L3
`
`L2
`
`L.
`
`END OF SEARCH HISTORY
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 10
`
`

`

`EST Refim Search
`
`~ST efie Serchhttp://westbrs:8002/bir/cgi-bin/PreSear
`
`L5
`
`Set Nam Ouer
`side by side
`DB = USPT, PGPB, JPAB, EPAB, D WPI, TDBD; pL UR= YES, OP=ADJ
`L6
`L4 and ((portable near2 remote control$3) or (set adj3 box near4
`television))
`L4 and ((portable near2 remote control$) of ($box near4 tee ,ision))
`network same navigation and (mobile or portable) and (speech or
`spoken) same request$3
`network same navigation and (mobile or portable) near3 appliance and
`(speech or spoken) same request
`network same navigation and (mobile or portable) near3 appliance and
`(speech or spoken) near4 request
`
`L3
`
`LI
`
`6523061.pn....
`
`END OF SEARCH HISTORY
`
`Hit Count Set Name
`result set
`
`2
`
`2
`
`84
`
`4
`
`V6
`
`1,5
`
`IA
`
`L3
`
`I
`
`Ll
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 11
`
`

`

`(12) United States Patent
`Halverson et al.
`
`US0067577181i
`
`l
`
`(H) Patent No.:
`(45) Date of Patent:
`
`US 6,757,718 BI
`Jun. 29, 2004
`
`(54) MOBILE NAVIGATION OF NETWORK-
`BASE]) ELECTRONIC INFORMATION
`USING SPOKEN INPUT
`
`(75)
`
`Inventors:
`
`Christine Halverson, San Jose, CA
`(US); Luc Julia, Menlo Park, CA (US);
`DIlminis Voutsas, Thessaloniki (GR);
`Adam Cheyer. Palo Alto, CA (US)
`
`(73) A/signee:
`
`SRI lnternational, Menlo Park, CA
`(US)
`
`* ) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) bydays.days.
`
`(21) Appl. No.: 09/608,872
`
`(22) Filed:
`
`Jun. 30, 2000
`
`Related U.S. Application Iata
`
`(63) Continuation of application No. (9/524,095. filed on Mar.
`13. 20(. which is a continuaion in part of application No.
`09/225.198, filed on Jar. 5. 1999.
`(60) Provisional application N,. 60/124,720, filed on Mar. 17.
`1999. provisional application No. 60/124.719. filed on Mar.
`17, I9l)9, and provisional apIication No. 601124,718,
`led
`on Mar. 17, 1990,
`Int. CI. 7
`(51)
`(52) U.S. CI
`
`. . . . . . . . . . . . . . . . . . . . . . G06F 15/16
`.................. 709/218; 709/202; 709/-17;
`709/219; 700/227; 704/257
`(58) Field of Search ........
`.............. 709/202, 218,
`709/217, 219, 227; 707/5, 3, 4; 704/257,
`270.1, 275, 246
`
`References Cited
`
`U.S PAIENT I)OCUMENTS
`
`5197.005 A
`5,386,556 A
`SA34C,777 A
`5.5t9.608 A
`5,608.624 A
`
`3/1993 Shwartz et a] ..... ........
`364/419
`395/60a
`1/1995 Hedin c .ol........
`7/1995
`tviiw
`....
`....... 364/419.13
`5/1996 Kupiec
`.........
`364/419 08
`3/1997 Luciw
`.............
`395794
`
`5.721,938 A
`5.729659 A
`5>748,174 A
`5,774,859 A
`,7q4.050 A
`5,802,52o A
`5.8051775 A
`,85.002 A
`t,890,123 A
`5,963,941 A
`
`............ 395/754
`2/1998 Stuckey
`3/19
`395/2.79
`o
`5/1998 Johnson
`395/759
`6/1998 !louser ct a' ._..........
`704275
`8/1998 Dahlren et al........ 395/708
`9/1998 Fawett
`al ..............
`707//la
`W1998 1 eman et 01 -............ 395/12
`IZ/1998 Arastrong .............. 704/270
`3/1999 Brown ot a' ......
`1... 704/275
`10/1999 Liddy et a. .................. 707/5
`
`(List continued on next page.)
`
`FOREIGN PATENT DOCUMENTS
`0 867 861
`99/50826
`1W/05638
`
`9/1998 .........
`10/11 9
`......
`/20(00(
`
`(0L//06
`3/00
`
`pp
`WO
`WO
`
`OTHER PUBLICATIONS
`[ntl AppI No. PCT/US01/
`International Search Report,
`07987,
`Stent, Amanda et al., *The CommandFalk Spoken Dialogue
`System", SRI Interational.
`
`(List continued on next page.)
`
`Priary Examincr-4rant, B Jean
`(74) Attorneiy Agent, or
`-irn-M oser, Palterson &
`Sheridan, LLP; Kin-Wah Tong
`
`(57)
`
`ABSTRACT
`
`A syslem, method, and article of manufacture are provided
`for navigating an electronic data sourae by means of spoken
`language where a portion of the data link between a mobile
`information appliance of the user and the data source utilizes
`wireless communication. When a spoken input request is
`received from a user who is using the mobile information
`appliance, it is interpreled The resulting interpretation of the
`request is thereupon used to automatically cornstruct an
`operational navigation query to retrieve the desired infor
`mation from one or more electronic network data sources,
`which is transmitted to the mobile information appliance
`
`27 Claims, 7 Drawing Sheets
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 12
`
`

`

`US 6,757,718 BI
`Page 2
`
`U.S. PATENT DOCUMEN TS
`6,003,072 A
`6.016,476 A
`6.026,388 A
`6,102,030 A
`6.173,279 BI
`6,192.33 BI -
`6.314,365 Bt
`6.317,684 BI
`6,349.257 BI
`6,353661 lIt
`
`70J/218
`t2/1999 Oerritsen et at ............
`1/21,00 Maeset a
`........... 7051
`2M2000 Liddy et al ............
`707/1
`8/2000 Brown et al ..
`...... 7475
`1/2001 Levin et at ............... 707/5
`Iasto cta.......
`...
`2/20301
`704/257
`11/2001 Smith ...................... 340/t88
`11/2001 Roeseler et a........
`340/990
`223002 Lim et a.
`...........
`340/56
`3/2002 Bailey. III ....
`.... 379/88,17
`
`OTHER PUBLICATIONS
`
`Moore, Robert et al, "Commandilalk: A Spoken-Language
`Inlerface for Battlefield Simulations", Oct, 23, 1997, SRI
`International.
`
`Dowding, John al al., "Inlerpreting Language in Context in
`CommandTalk", Feb. 5, 1999, SRI lnternational.
`
`hlp://wvw.ai.sri.com/-oaa/infowiz .himl, InfoWiz: An Ani-
`mated Voice Interactive Information System, May 8, 2000.
`
`Dowding, John, "Interleaving Syntax and Semantics in an
`Efficient Bottom up Parser", SRI International.
`
`inguislic and Stalistical
`Moore, Robert et al., "Combining
`Knowledge Sources in Natural-Language Processing for
`ATIS", SRI International.
`
`Dowding, John el al, "Gemini: A Natural Language System
`For Spoken-language Understanding", SRI International.
`
`* cited by examiner
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 13
`
`

`

`U.S. Patent
`
`Jun. 29,2004
`
`Sheet 1 of 7
`
`US 6,757,718 Bi
`
`102
`
`[A0n
`
`110
`
`Fig. la
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 14
`
`

`

`U.S. Patent
`
`Jun. 29,2004
`
`Sheet 2 of 7
`
`US 6,757,718 Bi
`
`10n
`
`1 iOn
`
`300 (see Fig. 3)
`
`Fig. l b
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 15
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 3 of 7
`
`US 6,757,718 Bi
`
`202n
`
`af 1o__2
`
`300 (see Fig. 3)
`210
`
`Fig. 2
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 16
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 4 of 7
`
`US 6,757,718 Bi
`
`REQUEST PROCESSING LOGIC 300
`
`SPEECH RECOGNITION
`ENGINE
`
`NATURALLANGUAGE
`PARSER
`
`Fig. 3
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 17
`
`

`

`U.S. Patent
`
`Jun. 29, 2004
`
`Sheet 5 of 7
`
`US 6,757,718 Bi
`
`402 RE
`
`404
`
`405
`
`IDE
`
`406 FCOir
`
`4'
`
`408
`
`Fig. 4
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 18
`
`

`

`U.S. Patent
`
`Jun. 29,2004
`
`Sheet 6 of 7
`
`US 6,757,718 Bi
`
`(from step 406, Fig. 4)
`
`SCRAPE THE ONLINE SCRIPTED FORM TO
`EXTRACT AN INPUT TEMPLATE
`
`INSTANTIATE THE INPUT TEMPLATE USING 522
`INTERPRETATION OF STEP 404
`
`(to step 407, Fig. 4)
`
`Fig.
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 19
`
`

`

`U.S. Patent
`US. Patent
`
`Jun. 29, 2004
`Jun. 29, 2004
`
`Sheet 7 of 7
`Sheet 7 0f 7
`
`US 6,757,718 Bi
`us 6,757,718 B1
`
`mzoxumdkI
`
`szmuiOFFXmF
`
`szgmo>mm;
`am.mm<mfi<o
`
`a‘_.Zm_©<
`
`HZmO(%IomMQw
`mdozw4<owOr—Ia
`Hzmo<.
`
`
`
`._.Zw04xMO<DOZ<4
`
`FZde‘
`
`mO._.<._._..:o<n_
`
`
`
`>u_._.OZ._<mD.tqZ
`
`lacom
`
`._.Zm_0<
`
`
`
`Wflflflflwmfiw29:200me
`
`Iommaw
`
`mmw:
`
`modimmlrg
`
`mHmed
`
`Owe;
`
`mmd‘md‘kdd
`
`FZMOd‘
`
`dwlm
`
`Petitioner Microsoft Corporation — EX. 1008, p. 20
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 20
`
`
`
`
`

`

`US 6,757,718 B1
`
`MOBILE NAVIGATION OF NETWORK-
`BASED EIEiCTRONIC INFORMATION
`USING SPOKEN INPUT
`
`This application is a continuation of an application 5
`entitled NAVIGATING NEIWORK-BASED ELEC-
`TRONIC INFORMATION USING SPOKEN NATURAL
`LANGUAGE INPUT WITH MULTIMODAL ERROR
`FEEDBACK which was filed on Mar. 13, 2000 under Ser.
`No. 09524,095 and which is a Continuation In Part of 10
`co-pending U.S. patent application Ser. No. 09/225,198.
`filed Jan. 5, 1999, Provisional U.S. patent application Sc,
`No, 60/124,718, filed Mar. 17,1999, Provisional U.S patent
`application Ser. No. 60/124.720, filed Mar. 17, 1999, and
`Provisional U.S. patent application Scr, No. 60/124,719, L,
`filed Mar, 17, 1999, from which applications priority is
`claimed and these application are incorporated herein by
`reference.
`
`BACKGROUND OF THE INVEN
`
`ION
`
`20
`
`'The present invention relates generally to the navigation
`of electronic data by means of spoken natural language
`requests, and to feedback mechanisms and methods for
`resolving the errors and ambiguities that may be associated 25
`with such request,.
`As global electronic connectivity continues to grow, and
`the universe of electronic data potentially available to users
`continues to expand, there is a growing need for information
`navigation technology that allows relatively naive users to o
`navigate and access desired data by means of natural lan-
`guage input. In many of the most important markets-
`including the home entertainment arena, as well as mobile
`computing spoken natural language
`input is highly
`desirable, if not ideal. As just one example, the proliferation 35
`of high-bandwidth communications infrastructure for the
`home entertainment market (cable, satellite, broadband)
`enables delivery of movies-on-demand and other interactive
`multimedia content to the consumer's home television set,
`For users
`to take full advantage of this content stream 40
`ultimately requires interactive navigation of content data-
`bases in a manner that is too complex for user-friendly
`selection by means of a traditional remote-control clicker.
`Allowing spoken natural language requests as the input
`modality for rapidly searching and accessing desired content 45
`is an important objective for a successful consumer enter-
`tainment product in a context offering a dizzying range of
`database content choices, As further examples, this same
`need to drive navigation of (and transaction with) relatively
`complex data warehouses using spoken natural language 50
`requests applies equally to surfing the Internet/Web or other
`networks for general information, multimedia content, or
`c-commerce transactions,
`In general, the existing navigational systems for browsing
`electronic databases and data warehouses (search engines, 5,
`menus, etc.), have been designed without navigation via
`spoken natural language as a specific goal. So today's world
`is full of existing electronic data navigation systems that do
`not assume browsing via natural spoken commands, but
`rather assume text and mouse-click inputs (or in the case of 60
`TV remote controls, even less), Simply recognizing voice
`commands within an extremely limited vocabulary and
`grammar-the spoken equivalent ofbutton/click input (e.g.,
`speaking "channel 5" selects TV channel 5)-is really not
`sufficient by itself to satisfy the objectives described above a5
`In order to deliver a true "win" for users, the voice-driven
`front-end must accept spoken natural language input in a
`
`manner that is intuitive to users For example, the from-end
`should not require learning a highly specialized command
`language or format. More fundamentally, the front-end must
`allow users to speak directly in terms of what the user
`ultimately wants -eg.,
`I d like to see a Western film
`directed by Clint Eastwood" -as
`opposed to speaking in
`terms of arbitrary navigation structures (eg, hierarchical
`layers of menus, commands, etc.) that are cssenlially arti-
`facts reflecting constraints of the pre-eisting text/click
`navigation system. At the same time, the front-end must
`recognize and accommodate the reality that a stream of
`naive spoken natural language input will, over time, typi-
`cally present a variety of errors and/or ambiguities: e.g.,
`garbled/unrecognized words (did the user say Eastwooud" or
`"Easter"?) and under-constrained requests ("Show me the
`Clint Eastwood movie'). An approach is needed for han-
`dling and resolving such errors and ambiguities in a rapid,
`user-friendly, non -firtstrating manner.
`What is needed
`is a methodology and apparatus
`for
`rapidly constructing a voice-driven
`front-end alop an
`existing, non-voice data navigation system, whereby users
`can interact by means of intuitive natural language input not
`strictly conforming to the step-by-step browsing architecture
`of the existing navigation system, and wherein any errors or
`ambiguities in user input are
`rapidly and conveniently
`resolved. The solution to this need should be compatible
`with the constraints of a muli-user, distributed environment
`such as the Internet/Web or a proprietary high-bandwidth
`content delivery network, a solution contemplating one at-
`a-time user interactions at a single location is insufficient, for
`example.
`
`SUMMARY OF TIlE INVENIION
`The present invention addresses the above needs by
`providing a system, method, and article of manufacture for
`mobile navigation of network-based electronic data sources
`in response to spoken input requests. When a spoken input
`request is received from a user using a mobile information
`appliance that communicates with a network server via an at
`least partially wireless communications system,
`it is
`interpreted, such as by using a speech recognition engine to
`extract speech data from acoustic voice signals, and using a
`language parser to linguistically parse the speech data. The
`interpretation of the spoken request can be performed on a
`computing device locally with the user, such as the mobile
`information appliance, or remotely from the user. The resul-
`ing interpretation of the request is thereupon used to auto-
`malically construct an operational navigation query to
`retrieve the desired information from one or more electronic
`network data sources, which is then transmitted to a client
`device of the user. If the network data source is a database,
`the navigation query is constructed in the format of a
`database query language.
`Typically, errors or ambiguities emerge in fhe interpreta-
`ion of the spoken request, such that the system cannot
`instantiate a complete, valid navigational template. [his is to
`be expected occasionally, and one preferred aspect of the
`invention is the ability to handle such errors and ambiguities
`in relatively graceful and user-friendly manner. Instead of
`simply rejecting such input and defaulting to traditional
`input modes or simply asking the user to try again, a
`preferred embodiment of the present
`invention seeks to
`converge rapidly toward instantiation of a valid navigational
`template by soliciting additional clarification from the user
`as necessary, either before or after a navigation of the data
`source, via multimodal input, i.e., by means of menu selec-
`tion or other input modalities including and in addition to
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 21
`
`

`

`US 6,757,718 B
`
`spoken input. This clarifying, multfimodal dialogue takes
`advantage of whatever partial navigational information has
`been gleaned Iron
`the initial interpretation of the user's
`spoken request. [his clarilication process continues until the
`system converges toward an adequately instantiated navi-
`gational tepulate, which is in turn used to navigate the
`network-based data and retrieve the user's desired informa-
`lhe retrieved information is transmitted across the
`tion.
`network and presented to the user on a suitable client display
`device
`In a further aspect of the present invention, the construc-
`tion of the navigation query includes extracting an input
`template for an online scripted interface to the data source
`and using the input template to construct the navigation
`query. The extraction of the input template can include
`dynamically scraping the online scripted interface.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The invention, together with further advantages thereof,
`may best be understood by reference to the following
`description taken in conjunction with the accompanying
`drawings in which:
`FIG. la illustrates a system providing a spoken natural
`language interface
`for network-based
`information
`navigation,
`in accordance with an embodiment of the
`present invention with server-side processing of requests;
`FIG. lb illustrates another system providing a spoken
`natural language interface for network-based information
`navigation,
`in accordance with an embodiment of the
`present invention with clien-side processing of requests;
`FIG. 2 illustrates a system providing a spoken natural
`language interface
`for network-based
`information
`navigation,
`in accordance with an embodiment of the
`present invention for a mobile computing scenario;
`FIG. 3 illustrates the functional logic components of a
`request processing module in accordance with an embodi-
`ment of the present invention;
`FIG. 4 illustrates a process utilizing spoken natural lan-
`guage for navigating an electronic database in accordance
`with one embodiment of the present invention;
`FIG. 5 illustrates a proces for constructing a navigational
`query for accessing an online data source via an interactive,
`scripted (e.g., CGI) f1r; and
`FIG, 6 illustrates an embodiment of the present invention
`uilizing a community of distrihuted, collaborating elec-
`tronic agents
`
`DETAILED DESCRIPTION OF TIlE
`INVENTION
`
`1. System Architecture
`a Server-End Processing of Spoken Input
`FIG. la is an illustration of a data navigation system
`driven by spoken natural language input, in accordance with
`one embodiment of the present invention, As shown, a user's
`voice input data is captured by a voice input device 102,
`such as a microphone. Preferably voice input device 102
`includes a button or the like that can be pressed or held-
`down to activate a listening mode, so that the system need
`not coninu ally pay attention to, or be confused by, irrelevant
`background noise. In one preferred embodiment well-suited
`for the home entertainment setting, voice input device 102
`is a portable remote control device with an
`integrated
`microphone, and the voice data is transmitted from device
`102 preferably via infrared (or other wireless) link to com-
`munications box 104 (eg., a set-top box or a similar
`
`communications device that is capable of retransmitting the
`raw voice data and/or processing the voice data) local to the
`user's environment and coupled to communications network
`106, The voice data is Ien transmitted across network 106
`5 to a remote server or servers 108. The voice data may
`preferably be transmitted in compressed digitized form, or
`alternatively--particularly where bandwidth constraints are
`significant-in analog format (eg.. via frequency modulated
`transmission), in the latter case being digitized upon arrival
`to at remote server 108.
`At remote server 108, the voice data is prcessed by
`request processing logic 300 in order to understand the
`user's request and constmuct an appropriate query or request
`for navigation of remote data source 110, in accordance with
`is the interpretation process exemplified in FIG 4 and FIG, 5
`and discussed in greater detai below. For purposes of
`executing this process, request processing logic 300 com-
`prises functional modules including speech recognition
`engine 310, natural language (Ni.) parser 320, query con-
`20 struction logic 330, and query refinement logic 340, as
`shown in FIG. 3. Data source 110 may comprise database(s),
`Internel/web site(s), or other electronic information
`repositories, and preferably resides on a central server or
`servers which may or may not be the same as server 108,
`25 depending on the storage and bandwidth needs of the
`application and the resources available to the practitioner.
`Data source 110 may include multimedia content, such as
`movies or other digital video and audio content, other
`various forms of entertainment data, or other electronic
`3o information. The contents of data source 110 are
`navigated-i.e., the contents are accessed and searched, for
`retrieval of the particular information desired by the user
`using the processes of FIGS. 4 and 5 as described in greater
`detail below.
`Once the desired information has been retrieved from data
`source 110. it is electronically transmitted via network 106
`to the user for viewing on client display device 112. In a
`preferred embodiment well-suited for the home entertain-
`ment setting, display device 112 is a television monder or
`41) similar audiovisual entertainment device, typically in sta-
`for comfortable viewing by users. In
`tionary position
`addition, in such preferred embodiment, display device 112
`is coupled to or integrated with a communications box
`(which is preferably the same as communications box 104,
`45 but may also he a separate unit) for receiving and decoding!
`formatting the desired electronic information that is received
`across communications network 106.
`Network 106 is a two-way electronic communications
`network and may be embodied in electronic communication
`50 infrasinicure
`including coaxial (cable
`television) lines.
`DSL. fiber-optic cable,
`traditional copper wire (twisted
`pair), or any other type of hardwired connection. Network
`106 may also include a wireless conneccm such as a
`satellite-based connection, cellular connection, or other type
`5, of wireless connection. Network 106 may be part of the
`Internet and may support TCPIIP communications, or may
`be embodied in a proprietary network, or in any other
`electronic communications network infrastructure, whether
`packet-switched or connection-oriented. A design conxsider-
`at ion is that network 106 preferably provide suitable band-
`width depending upon the nature of the content anticipated
`for the desired application.
`b. Client-End Processing of Spoken Input
`FIG. lb is an illustration of a data navigation system
`05 driven by spoken natural language input, in accordance with
`a second embodiment of the present invention. Again, a
`user's voice input data is captured by a voice input device
`
`35
`
`Petitioner Microsoft Corporation - Ex. 1008, p. 22
`
`

`

`US 6,757,718 B1
`
`102, such as a microphone. In the embodiment shown in
`FIG. 1b, the voice data is transmitted from device 202 to
`requests processing logic 300, hosted on a local speech
`processor, for processing and interpretation. In the preferred
`embodiment illustrated in FIG. lb, the local speech proces-
`sor is coinveniently integrated as part ofcommunications box
`104, although implementation in a physically separate (but
`communicatively coupled) unit is also possible as will be
`readily apparent to those of skill in the ar. The voice data is
`processed by the components of request processing logic
`300 in order to understand the user s request and construct
`an appropriate query or request for navigation of remote data
`source 110, in accordance with the interpretation process
`exemplified in FIGS. 4 and 5 as discussed in greater detail
`below
`The resulting navigational query is then transmitted ekc-
`ironically across network 106 to data source 110, which
`preferably reides on a central server or servers 108. As in
`FIG In, data source 110 may comprise databases, Internet/
`web site(s), or other electronic information repositories, and
`preferably may include multimedia content, such as movies
`or other digital video and audio content, other various forms
`of entertaiment data, or other electronic information. The
`contents of data source 110 are then navigaledf-i.e., the
`contents are accessed and searched, for retrieval of the
`particular information desired by the use r-preerably using
`the process of FIGS. 4 and 5 as described in greater detail
`below. Once the desired information has been retrieved from
`data source 110, it is electronically transmitted via network
`106 to the 'set for viewing on client display device 112.
`In one embodiment in accordance wit FIG. lb and
`well-suited for the home entertainment setting, voice input
`device 102 is a portable remote control device with an
`i