WWWMMWWH IWWWWWWW
`
`U800?539656B2
`
`(12) United States Patent
`Fratkina et at.
`
`[10) Patent No.:
`(45) Date of Patent:
`
`US 7,539,656 I32
`May 26, 2009
`
`(54) SYSTEM AND METHOD FOR PROVIDING AN
`INTELLIGENT MULTI-STEP DIALOG WITH
`A USER
`
`we
`W0
`
`W0-99.-'t8526
`“IO—2000077690 A}
`
`4.1999
`|2.-"200[I
`
`OTHER PUBLICATIONS
`
`(75}
`
`Inventors: Rays li‘ratkina. Hayward. CA (US):
`Monica Anderson. San Jose. (.‘A (US):
`Mark A. Angel. C upertino. CA (US):
`Max Coppcrman. Santa Cruz. CA (US):
`Scott B. Huffman. Redwood City. CA
`(US); David Kay. I..os Gates. (TA (US):
`Robert Stern. Cupertitto, (‘A (US)
`
`(73) Assignee: Consona (IRM Ine._. Indianapolis. IN
`(US)
`
`( * ) Notice:
`
`Subject to any disclaimer. the term oi'thjs
`patent is extended or adjusted under 35
`U.s.(:. 1540;) by 1207 days.
`
`(21) Appl. No.: 09fl98,964
`
`(22)
`
`(65)
`
`Filed:
`
`Mar. 6, 2001
`
`Prior Publication Data
`
`US 200110049688 A]
`
`Dec. 6, 2001
`
`Related US. Application Data
`
`(60) Provisional application No. 60f 187.472. filed on Mar.
`6. 2000.
`
`(51)
`
`Int. (‘1.
`(2006.01)
`G06)” I300
`(2006.01)
`G0617 17/30
`(2006.01)
`GflfiN 5/00
`706145: 7078; 7071104.]
`(52) U.S.(Il.
`[58) Field ofClassifieation Search
`T063115
`Sec application file for complete search history.
`
`(56)
`
`References Cited
`U.S. RATENT DOCUMENTS
`
`4.918,621 A
`
`41990 Nada-eta].
`
`364.5513
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`W0
`
`W0-97-“38378
`
`[0" | 99’!
`
`The impact ofa simulation-based learning design project on student
`learning Chtmg. G.K.W.K.; Harmon. TC; Baker. F..I..; Education.
`IEEE Transactions on vol. 44. Issue 4. Nov. 300] pp. 300-398 Digital
`Object Identifier 10.l l09.-" |3.65789.*
`
`(Continued)
`
`Primary Examiner—Michael B Holmes
`(74) Attorney. Agent, or Firm—Ice Miller LLP
`
`(57)
`
`ABS'I‘RAC'I‘
`
`A method and system are disclosed [or retrieving inlonnation
`through the use of a multi—stage interaction with a client to
`identify particular knowledge content associated with a
`knowledge map. The present invention is an application pro-
`gram running on a server accessed via tlte world-Wide web or
`other data network using standard Internet protocols. a web
`browser and web server software. In addition to an automated
`portion. the present invention allows a human dialog designer
`to model the way the system elicits information. giving a
`human feel to the dialog and a better customer experience. In
`operation. users start a dialog by directing their web browser
`to a designated web page. This web page asks the user some
`initial questions that are then passed to a dialog engine. The
`dialog engine then applies its methods and algorithms to a
`knowledge map. using dialog control int'onnation‘t and the
`user’s responses to provide feedback to the user. The listed-
`back may include follow-up questions. relwant documents.
`and instructions to the user (e.g._. instructions to contact a
`human customer service representative). This dialog engine
`response is rendered as a web page and returned to the user’s
`web browser. The user can then respond further to the follow-
`up questions he or she is presented. and the cycle repeats. The
`invention can be implemented so that it can interact with
`customers through a wide variety ofcotmnunication channels
`including the Internet. wireless devices (e.g._.
`telephone.
`pager, etc ) handheld devices such as a Personal Data Assis-
`tant (FDA), email, and via a telephone where the automated
`system is delivered using an interactive voice response (IV'R)
`andfor spasm-recognition system.
`
`15 Claims, 19 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ELASTIC - EXHIBIT 1006
`
`ELASTIC - EXHIBIT 1006
`
`

`

`US 7,539,656 B2
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`Computing. 2007. GCC 2007. Sixth International Conference on
`Aug. 16-18. 2007 pp. 693-700 Digital Object Identifier 10.1109.-"
`GCC.2007.53.*
`“(Kanisa) lntelligized Business Processes”. (1998). 12 pgs.
`“About the Information Manifold“. web page. 1 pg.
`“Facts Connect Care by ProAmerica—Frequently Asked Ques—
`tions”. (1998). 3 pgs.
`“IBM intelligent Miner for Data". (1998). 10 pgs.
`“IBM Intelligent Miner for Data. Version 2.1”. 2 pgs.
`“IBM‘s Data Mining Technology". 1: 1996). 25 pgs.
`“Industry Solutions: Markets and Applications". (Nov. 1998). 3 pgs.
`“Kana Communications— Success Story: eBay”. (Nov. 1998). 4 pgs.
`“Kana Communications Success Story: Netscape”. 4 pgs.
`“ProAmerica Connect Care—The First Customer Care Software”.
`12 pgs.
`“ProAmerica Redefines Customer Care with Visual Warehouse".
`IBM. (Feb. 1998). 2 pgs.
`“Quality Connect". web page. (Nov. [998). 2 pgs.
`“Sales Connect". web page. (Nov. 1998). 2 pgs.
`“SCM—Theory of Customer Care. ProAmcIica“. (1996). 1v28.
`“Support Connect". web page. (Nov. 1998). 4 pgs.
`“Survey Connect”. “-96 page. (Nov. 1998).
`1 pg.
`“The Kana Customer Massaging System". (Nov. 1998). 2 pgs.
`“Using the Intelligent Miner in a Simple Scenario”. Persian 2.1.7.
`78:14. (Apr. 1998). 1-35.
`“Web Connect”. web page. (Nov. 1998}. 2 pgs.
`Buckley. James P.. “A Hierarchical Clustering Strategy for Very
`Large Fuzzy Databases“. [SEE Int-'1‘ Conf on systems. Man and
`Qrbei'nencs. 4. (1995). 35733578.
`Chakrabarti. Soumen. et al.. “Scalable Feature Selection. Classifica-
`tion and Signature Generation for Organizing Large Text Databases
`into Hierarchical Topic Taxonomies”. The VLDB Journal. 7. (1998).
`163-178.
`I.i. Wen-Syan. et at. “PowerBooiunarks: A System for Personaliz-
`able Web Information Organization. Sharing. and Management".
`Proe. AC‘M SIGMOD Int"! . Can}? on Management of Data. 28.
`(1999). 565-567.
`Magennis. Mark. et .11.. “The Potential and Actual Eflectivcness of
`Interactive Query Expansion”. Amara! Int’t‘. ACN—SIGIR Cont: on
`Roman-Ii and Development in liy’arnian‘on Retrieval. (1997).324-
`332.
`Stodder. David. et a].. “Toward Universal Business Intelligence: An
`Interview with Janet Perna“. (l997).6 pgs.
`'I‘kach, Daniel 5.. “Intbrmation Mining with the IBM Intelligent
`Miner Family". An IBM Sofiware Solutions- wane Paper. (1998).
`1—29.
`Wong. Jacqueline W.. ct .11.. “Action: Automatic Classification for
`Full-Text Documents". Association quompnn’ng Machinery SIGIR
`Forum. 30. (1996].26-41.
`http:.-7web.archive.orgt'webr'
`archive”.
`“Amazoncom
`web
`1999101309l817."http:.-'tamazon.coin. Web page from Oct. 13. 1999;
`Copyright 1996-1999; retrieved Jan. 7. 2007. 2.
`“eBay - Your Persona] Trading Community”. httpn'twebarehiveorgt
`wets-r 199901 17033 1S9i’pagcs.ebay.com-“aw-“indexhtml.
`Pagc
`last
`updated Jan. 16. 1999. Copyright 1995-1998. relrievedJan. 12.2007.
`1 pg.
`“131’ Office Action“. EPC Patent Application No. 009398900 dated
`Jul. 29. 2004.
`“InQuira Information Manager Data Sheet". Infin'mntion Manager
`for Ian‘ra 7. (2005). 2 pages.
`“Non—Final OII'lce Action". Mailed Apr. 12. 2007 for U.S. App]. No.
`101889.888. 12 pgs.
`“Non-l‘inal Oflicc Action". Mailed Oct. 31. 2002 for US. App]. No.
`093594.083. [7 1333.
`“Notice of Allowability". Mailed Apr. 18. 2003 for US. App]. No.
`091594.083. 6 pgs.
`“Notice of Allowance". Mailed Mar. 14. 2007 for 11.5. App]. No.
`10.-'610.994._ 10 pgs.
`“Notice of Allowance”. Mailed Jim. 19. 2006 for 11.8. App]. No.
`l0.-"610.994. 25 pgs.
`“Notice of Allowance". Mailed Mar. 14. 2003 for US. App]. No.
`091594.083. ll pgs.
`
`5.034.898 A
`5.309.359 A
`5.377.103 A
`5.404.295 A
`5.412.804 A
`5.568.640 A
`5.600.831 A
`5.625.748 A
`5.655.116 A
`5.659.725 A
`5.671.333 A
`5.724.571 A
`5.768.578 A
`5.794.050 A
`5.809.499 A
`5.845.270I A
`5.878.423 A
`5.887.120 A
`5.895.466 A
`6.006.218 A
`6.035.305 A 7‘
`6.055.540 A
`6.061.675 A
`6.151.584 A
`6.167.370 A
`6.169.992 Bl *
`6.185.550 Bl
`6.199.034 B1
`6.347.313 Bl
`6.347.317 Bl
`6.359.633 Bl
`6.360.213 B1
`6.411.962 Bl
`6.430.558 Bl
`6.434.550 Bl
`6.438.579 131
`6.446.061 Bl
`6.460.029 Bl
`6.460.034 Bl
`6.493.697 Bl “
`6.538.560 Bl
`6.549.949 131*
`6.556.671 Bl
`6.581.056 RI
`6.598.018 Bl
`6.636.853 Bl
`6.643.640 B1
`6.687.696 B2
`6.732.088 Bl
`6.766.320 B1
`6.980.984 131*
`7.206.778 32’“
`2002-"0027567 Al
`200210103798 A1
`200570055321 A1
`200770033221 A]
`
`364-"513
`
`..
`
`
`
`
`7071104.]
`
`71199] Ltl eta].
`5:"1994 Katz et a].
`1231994 Lamberti el al.
`411995 Katz et a].
`511995 Krishna
`1011996 Nishiyarna eta].
`395.:600
`2.-'1997 Levy el al.
`. 3957602
`
`411997 McDonough et a]
`.. 39572.6
`. 395-"601
`811997 Kirketa].
`
`. 395-"600
`811997 Levy et a1.
`9-1997 Catlett et a].
`395720
`.3957605
`3-’l998 Woods
`
`611998 Kirk eta].
`3953611
`811998 Dahlgren et a1.
`3953708
`911998 Wong et a].
`707.56
`1271998 Schatzetal.
`706111
`37’1999 Anderson et al.
`31999 Wical
`411999 Goldberg et a1.
`lZ-"l999 Breese et a].
`312000 Streveyetal.
`{2000 Snow-eta].
`5:"2000 Wical
`1112000 Papierniak et a1.
`1212000 Tsourikov et a1.
`172001 Beal] el al. .............. 707.5103 R
`21200] Snow et a].
`37200] Wical
`2:"2002 Ma eta].
`2.12002 Singhal
`372002 Balasubramaniam et a1.
`3:"2002 WagstalTet a.].
`612002 Kupiec
`72002 Delano
`812002 Warneret a1.
`812002 iIosken
`912002 Deer-rectal.
`1012002 Fries eta].
`1072002 Wical
`1212002 Stieret a].
`312003 Stobbeeta].
`412003 Bowman-1111103.]:
`412003 Beauvois
`12003 Rao
`712003 Junqua
`10.52003 Stephens. Jr.
`1 112003 Getchius et a].
`212004 Hofmann et a1.
`512004 Glance
`12004 Wang et a].
`1212005 Huffman et a1.
`412007 Bodeeta].
`32002 Niamir
`812002 A616] et al.
`312005 Fratkina et 3].
`2.12007 Copperman et a1.
`
`70713
`
`706.-"50
`
`709E236
`
`70713
`707I'5
`
`O'I‘I-II-SR PUBI .IC18'I‘lONS
`
`Symbolic interpretation of artificial neural networks 'I‘al'ia. 1.A.;
`Ghosh. 3.; Knowledge and Data Engineering. IEEE Transactions on
`vol. 11. Issue 3. May-Jun. 1999 pp. 448-463 Digital Object Identifier
`10.1109.-"69.774103."
`Urganiulional Experience Management Through Knowledge
`Maps - An Ontological Approach Neshatian. Ks Khanat. M..
`Khamaneh. 8.8.; World Automation Congress, 2006. WAC ‘06 Jul.
`24—26. 2006 pp. 1—8 Digital Object Identifier [0.] 109-'WAC .2006.
`376046.‘
`Building Knowledge Flow of ’I‘cxtua] Topics for the e-Science
`Knowledge Grid Luo. Xiangfeng; Yu. Zhian; Grid and Cooperative
`
`

`

`US 7,539,656 B2
`Page 3
`
`“Supplemental Notice oi‘Allowability". Mailed feb. 26. 2007 forUS.
`App]. No. I0.-"610.994. 20 pgs.
`“Wtil 2000077690 Search Report”. PCT Search Report oflnterna-
`tiona] Application No. PCTiUSODt'IGMti.
`Downey. S. . "Using virtual reality to construct knowledge". l‘totttiet's'
`in Education Conference (I). (1908), 392.
`Eppler. M. J .. "Making Knowledge visible through intranet knowl-
`edge maps: concepts, elements, cases Eppler", System Sciences; Pro-
`ceedings of the 34th Annual Hawaii international Con erenee.
`(2001), 1-10.
`K110. R.. et 31.. “Difficulty Analysis for ieamers in problem solving
`process based on the knowledge map”. Advanced Learning Territ-
`nologies. {2003). 386-381
`Mularz. D.. or 211.. “Integrating concept mapping and semantic Web
`technologies for knowledge management”, i5tn International Work—
`shop on Database and Exfxn't Systems Applications, 2004. Proceed—
`ings.. (2004) . 449-453.
`
`Pele. K. 1.. "Knowledge system of engineering and technology man-
`agement”.
`lecnnolog> Management; the New international Lan-
`guage. (1991). 550-553.
`Rouse. W. B. . et al.. “Knowledgemaps for knowledge mining: applic-
`tion to R&Ditechnology management“. {BEE Transactions on Sys-
`tems, Man and Cybernetim, Part C: Applications and Reviews. (_ Aug.
`1998). 309-317.
`Saad. .v‘\.. et al.. “A knowledge visualisation too] for teaching and
`learning computer engineering knowledge. concepts. and skills".
`32ndAnnnal Frontiers in Education. 2002. FIE 2002., ( 2002). T2F -
`7-T2F-10.
`Silva. P. C. "Fuzzy congitive maps over possible worlds”. Proceed—
`ings ofi995 lEEE international Conference on Fuzzy .Svstems, £995.
`fitternational Joint Conference of the Font-tit lEEE international
`Conference on l'iizzy Systems and The Second International Hts: .-
`Engineering Symposium. (Mar. 1995). 555-560.
`
`* cited by examiner
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheetl of 19
`
`US 7,539,656 B2
`
`10
`
`
`
`EJ-
`
`34
`
`18
`
`“HI-Ii]
`
`GATEWAY
`
`
`
`32
`
`PUBLIC
`NETWORK
`
`/ \
`
`25
`
`32
`
`24
`
`L
`
`24 l
`
`22
`
`COMPANY
`EXTRANET
`
`7
`
`32
`
`32
`
`7
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 2 of 19
`
`US 7,539,656 B2
`
`2.12
`
`101
`
`1 ‘3
`
`106
`
`DISPLAY
`
`108
`
`MEMORY
`
`132
`
`1 30
`
`
`
`BROWSER
`PROGRAM
`
`OPERATING
`SYSTEM
`
`1 1O
`
`KEYBOARD
`
`USER INTERFACE
`ADAPTOR
`
`1 1 1
`
`POINTINC
`DEVICE
`
`1 14
`
`1 15
`
`I/O
`ADAPTOR
`
`DISK
`STORAGE
`
`120
`
`34
`
`COMM
`ADAPTOR
`
`32
`
`FIG. 2
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 3 of 19
`
`US 7,539,656 B2
`
`24
`
`201
`
`206
`
`208
`
`213
`
`202
`
`DISPLAY
`ADAPTOR
`
`23mm“
`
`D-ALOG .PERATING_NGLNE .TEM
`
`
`HALIC6.NOEAEDGE“CONTROL
`
`INFORMATHN
`
`D'SPW
`
`212
`
`KEYBOARD
`211
`POINTING
`
`DEVICE
`
`USER INTERFACE
`
`ADAPTOR
`
`214
`
`215
`
`I/O
`ADAPTOR
`
`DISK
`STORAGE
`
`220
`
`ADAPTOR
`
`32
`
`FIG. 3
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 4 of 19
`
`US 7,539,656 B2
`
`
`
`
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 5 of 19
`
`US 7,539,656 132
`
`8K
`
`E???ma
`
`QEo.Ho:wm_:E
`
`
`
`lllllllll2828:2an
`
`869”.ngA90\vmm_Ao_ovm5.wwmflc_Aav
`
`L83302.AcoflvaEEtzx:oumAEoEmav
`
`
`A38co:E_axo\me\_n\m_ABou8:93wa
`
`
`AEE<v$mBEboc_E:maAE._BVmEAn_v
`
`A88:38.8?mw\n\oABoucozoobv
`
`
`GEE/XE;.o___msmmcofiav
`
`55:88QESEE8:238:
`
`mod628$lemod;>Eozox5.
`
`
`
`mad563(le
`
`med”.58.;
`
`ERGI452
`
`m>:<mpm_z_s_e<
`
`8362
`
`avE288%:
`
`m.o_u._
`
`mxz:
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 6 of 19
`
`US 7,539,656 132
`
`
`
`
`
`wzflmomaEEEQ025013.539:mo»$50293
`
`\\0%gI-Em8%
`
`8qu6&on
`
`own
`
`momfluoE
`
`”5:5:
`
`memowas
`
`Em.
`
`w.07..
`
`own
`
`oE.
`
`EEGuzzémao
`
`
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 7 of 19
`
`US 7,539,656 B2
`
`V
`
`mA”AAAIM/AAA.
`
`.
`
`///
`
`%
`
`flI1”
`AA/AA/AAA
`
`UA//AAAAI AAA/AAAVA/A/
`
`AAA/é?
`A@0
`
`0
`
`0
`
`AA
`
`A/Av
`
`£4}.11”
`IA_AAfl//V%
`ooAAAAAAA
`
`FIG. 7
`
`AAA/Ago
`
`7....
`
`0TJ
`
`I
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 8 of 19
`
`US 7,539,656 132
`
`NOT-UNDER (c)
`
`
`
` oo#4//.’,40%,0‘0Vfl/I\7/1/1|//70000‘0/@/00‘070
`
`FIG. 8
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 9 of 19
`
`US 7,539,656 B2
`
`PATH-IF—TACGED (
`7/
`
`)
`
`x%
`
`UNDER—IF—TAGGED
`
`//////////EI//fit7z/@1-
`léf/I49WI[”4
`
`0
`
`FIG. 9
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 10 0f19
`
`US 7,539,656 B2
`
`1030
`
`1040
`
`creoteGool
`i
`
`SCRAMBLED
`
`node=breokfast;
`
`
`
`BREAKFAST
`
`DINNER
`
`FIG. 10
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 11 0f19
`
`US 7,539,656 B2
`
`DIALDG STATE
`
`QUESTIONS GENERATED
`DURING DIALOG AND USER
`ANSWERS (SELECTIONS)
`
`ITERATION N
`
`WHICH OF THE FOLLOWING
`lI‘I‘OULD YOU LIKE TO GET?
`
`SCRAMBLED
`
`—u
`
`ITERATION N+1
`
`HOW WOULD YOU LIKE
`YOUR EGGS PREPARED?
`
`W
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 12 0f19
`
`US 7,539,656 B2
`
`DIALOG STATE
`
`BREAK FAST
`
`
`
`
`
`
`
`
`
`
`QUESTIONS GENERATED
`DURING DIALOG AND USER
`ANSWERS (SELECTIONS)
`
`ITERATION N
`
`ARE YOU ON ANY DIET?
`
`3m mun
`
`u'
`
`WHICH OF THE FOLLOWING
`WOULD YOU LIKE TO GET?
`
`
`
`
`
`
`
`
`—u
`
`
`
`ITERATION N+1
`
`II (breakfast, confirmed)
`I
`
`createGool
`I
`
`node=poncakes;
`
`
`HOW WOULD YOU
`LIKE YOUR PANCAKES?
`
`fl
`
`_ W
`
`WITH SYRUP
`ITHOUT SYRUP
`
`ITERATION N+2
`
`BREAKFAST
`
`
`
`
`BREAKFAST
`WITH SYRUP
`
`
`
`WITHOUT
`SYRUP
`
`PANCAKES
`
`FIG. 12
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 13 0f19
`
`US 7,539,656 B2
`
`Follow-up Questions
`
`-
`
`SYSTEM ASKS USER FOLLOW—UP QUESTIONS BASED ON ACTIVE GOALS
`
`-
`-
`
`-
`
`CO: CLARIFYING QUESTION
`DO: DOCUMENT QUESTION
`
`TEXT QUESTION
`
`'
`
`SYSTEM CAN OFFER USER A CACHED QUESTION
`
`-
`
`PQ: PARAMETERIZED QUESTION
`
`FKl 13
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 14 of 19
`
`US 7,539,656 B2
`
`
`
`
`
`.mwflaocoxmpmaymacawmmoonocmogmm:may
`
`.:.o_u._
`
`
`
`mzwoamflom>fluomywucH
`
`om:x\2:
`
`ZO_._.Omr_m_m\fEOZOxE.
`
`
`
`zO_._.Um_._mmawhmajo
`
`om:
`
`ow:\\Om:
`
`HZm—szlmmmmHmDJU
`
`ow:
`
`
`
`HZmEmZEm—m\rmuDO
`
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 15 0f19
`
`US 7,539,656 B2
`
`TQ — Text Question
`
`WHAT NND 0F BREAKFAST FOOD WOULD YOU UKE TO HAVE TDDAN
`
`(PLEASE TYPE IN)
`
`Scrambled eggs
`
`.
`
`-
`
`TAXONOHY NAVIGATION QUESTION
`
`USER TYPES IN TEXT THAT WILL BE AUTOCONTEXTUALIZED TO
`A PLACE IN THE TAXONOMY
`
`FR; 15
`
`DQs — Document Driven Question
`
`THE FOLLOWING DISHES ARE LEFT IN THE KITCHEN.
`PLEASE CHOOSE THE ONE(s) YOU WOULD LIKE To GET:
`
`Scrambled eggs
`
`Poached eggs
`
`
`
`Pancakes without syrup
`
`-
`
`.
`
`'
`
`ANOTHER KIND OF FOLLOW—UP QUESTION
`
`BASED ON THE SET OF KCs REMAINING
`
`SELECTION OF TAXONOMY—WIDE ALTERNATIVES
`
`FKl 16
`
`PQ — Parameterized Question
`
`KANISTAURANT IS FAMOUS FOR ITS CHERRY PIES.
`WOULD YOU LIKE TO TRY A PIECE?
`
`'
`
`.
`
`SHORTCUT OUT OF DIALOG
`
`A GUESS ABOUT LIKELY USER INTENTIONS
`
`- FREQUENTLY ASKED
`
`-.IUPORTANT
`
`FKS. 17
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 16 0f19
`
`US 7,539,656 B2
`
`USER POSES QUESTION
`
`T0 DIALOG ENGINE
`
`DIALOG ENGINE
`
`GREATES INITIAL GOALS
`
`I820
`
`1830
`
`DIALOG ENGINE POSES
`
`FOLLOW-ON QUESTION T0 USER
`
` 1810
`
`
`
`
`
`
`1840
`
`DIALOG ENGINE RESOLVES GOALS
`
`
`
`1850
` ANY
`REMAINING
`
`
`
`
`GOALS?
`
` RETURN RANKED
`
`DOCUMENTS TO USER
`
`FIG. 18
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 17 0f19
`
`US 7,539,656 B2
`
`Example: Dialog Walkthrough
`
`
`
`HOSTESS: "YES?"
`
`USER: "Two FOR LUNCH"
`
`NAITER: “WOULD LIKE ANY DRINKS TODAY?"
`
`“NO"
`
`"DO YOU HAVE ANY DIETARY CONSTRAINTS?"
`
`”YES,
`
`I AM ON HIGH—PROTEIN DIET"
`
`"WOULD YOU LIKE BREAKFAST OR LUNCH FOOD?"
`
`FKl 19
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 13 0f19
`
`US 7,539,656 B2
`
`Restaurant Taxonomies
`
`DRINK
`PREFERENCE
`
`HARD
`
`NON
`
`
`
`
`BREAKFAST ®
`LIQUOR ® @@
`
`2010
`
`@ w ® @
`
`FORCE-IEO
`
`FKl 20
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 19 0f19
`
`US 7,539,656 B2
`
`Example: Dialog Walkthrough
`(continued)
`
`"BREAKFAST"
`
`"WE HAVE EGGS AND PANCAKES. WHAT WOULD YOU LIKE?"
`
`"EGGS”
`
`"SCRAMBLED. POACHED 0R BENEDICT?"
`
`"SCRAMBLED"
`
`"HERE _IS YOUR CHECK. THANKS FOR COMING"
`
`
`
`FKl 21
`
`

`

`US ?,539,656 B2
`
`1
`SYSTEM AND METHOD FOR PROVIDING AN
`INTELLIGENT M UIII'I-STEP DIALOG WITII
`A USER
`
`RELATED APPLICATIONS
`
`This application claims priority to the following applica-
`tions:
`
`US. Provisional application No. 603187.472. entitled
`“System and Method for Producing an Intelligent Multi-Step
`Dialog with a User." filed Mar. 6. 2000.
`The following identified U.S. patent application is relied
`upon and hereby incorporated by reference in this applica—
`tion:
`
`10
`
`U.S. patent application Ser. No. 051594.083. entitled “Sys-
`tem and Method for Implementing a Knowledge Manage-
`ment System.“
`
`FIELD OI“ TI Ill INVENTION
`
`This invention relates to systems and methods for retriev—
`ing information and. more particularly. to systems and meth-
`ods for providing a multi-slep conversation-like interaction
`between a person and a computer or other device to refine and
`satisfy the person’s request for in limitation.
`
`BACKGROUND
`
`A key resource of most. ifnot all enterprises is knowledge.
`For example. in a customer service envirotunent. customers
`expect prompt and correct answers to their infomiation
`requests. These information requests may relate to problems
`with products the customer has purchased. or to questions
`about products they may decide to purchase in the future. In
`most cases. the answer to the customer’s question exists
`somewhere within the enterprise. In other cases. the answer
`may have existed in the enterprise at one time. but is no longer
`there. The challenge is to find the best answer and provide it
`to the customer in a timely manner.
`Typical approaches to providing support infonnation to
`customers on the Internet, either provide a static structure
`(predefmcd hyperlinks) for customers to navigate to the infor-
`mation they need. or they provide simple “lockup" facilities
`for finding documents or products, such as database searches
`or full-text searches for keywords appearing in documents or
`in product descriptions. These types of approaches are typi-
`cally not tailored to the customer {no personalization) and do
`not typically engage the costumer in a multiple step interac-
`tion (no conversational dialog), wherein the infonnation is
`elicited fi'om the customer.
`
`Other current approaches for providing support infonna-
`tion to customers, such as case-based reasoning systems and
`expert systems. provide a multiple step interaction with cus-
`tomers, but they require the business to set up very complex
`“case" structures or expert—system rule sets that define the
`problems and their
`resolutions
`in great detail. These
`approaches are often brittle and it is typically very costly for
`the business to add new rules and cases to these systems.
`Still other Web-based systems check for particular textual
`content without the advantage of context or domain knowl-
`edge. Consequently. they generally do not reliably and con«
`sistently return the desired infonnation. This is at least partly
`due to the fact that language is not only inherently ambiguous.
`but also because it is susceptible to expressing a single con-
`cept any number of ways using numerous and unrelated
`
`3o
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`words audtor phrases. By simply searchng for specific key
`words. prior art search engines fail to identify other alterna-
`tives that may also be helpful.
`Consequently. there is a strong need in the art for an
`improved method and apparatus for retrieving relevant infor-
`mation from large knowledge bases. There is also a need for
`providing this capability to relatively unsophisticated users.
`
`SUMMARY OF THE INVENTION
`
`The present invention satisfies the above-described need
`by providing a system and method for efficiently retrieving
`information from a large knowledge base. More specifically,
`the present invention uses a fairly simple set of knowledge
`structures to represent the domain of problems to be dis-
`cussed with the customers. New documents describing prob-
`lem resolutions. product descriptions. etc.. can be either
`manually or automatically placed into these knowledge struc-
`tures. Users‘ interests. backgrounds. etc._. can also be repre-
`sented using these same structures. Once the knowledge
`structure is populated. businesses can write fairly simple
`navigation rules that allow the invention to engage customers
`in a rich. personalized dialog.
`The present invention supports a model of interaction
`between a machine and a human being that closely models the
`way people interact with each other. It allows the user to begin
`with an incomplete problem description and elicits the
`unstated elements of the description which the user may not
`know at the beginning of the interaction. or may not know are
`important—asking only questions that are relevant
`to the
`problem description stated so far, given the system‘s knowl-
`edge of the problem domain: without requiring the user to
`answer questions one at a time. or to answer all of the ques-
`tions posed; and without imposing unnecessary restrictions
`on the order in which questions are posed to the user. The
`present invention allows the dialog designer to model the way
`an expert elicits information. giving a human feel to the dialog
`and a better customer experience.
`In one embodiment. the present invention is an application
`program running on a server accessed via the world-wide web
`or other data network using standard Internet protocols. a web
`browser and web server software. In operation. users start a
`dialog by directing their web browser to a designated web
`page. Mis web page asks the user some initial questions that
`are then passed to a dialog engine. The dialog engine then
`applies its methods and algorithms to a knowledge map. using
`dialog control infomiation and the user’s responses to pro-
`vide feedback to the ttser. The feedback may include follow-
`up questions, relevant documents. and instructions to the user
`(cg, instructions to contact a human customer service rep-
`resentative). This dialog engine response is rendered as a web
`page and returned to the user‘s web browser. The user can
`then respond further to the follow-up questions he or she is
`presented and the cycle repeats.
`The invention can be implemented so that it can interact
`with customers through a wide variety of communication
`channels including the Internet. wireless devices (e.g., tele-
`phone, pager. etc], handheld devices such as a personal data
`assistant (FDA). email. and via a telephone where the auto-
`mated systcm is delivered using an interactive voice response
`(NR) andfor speech-recognition system.
`Additional features and advantages ofthe invention will be
`set forth in the description which follows and. in part. will be
`apparent from the description. or may be learned by practice
`of the invention. The objectives and other advantages ofthe
`invention will be realized and attained by the methods. sys-
`
`

`

`3
`
`4
`
`US ?,539,656 B2
`
`tents. and apparatus particularly pointed out in the written
`description and claims hereof. as well as the appended draw-
`ings.
`is to be understood that both the foregoing general
`It
`description and the following detailed description are exem-
`plary and explanatory and are intended to provide fnnher
`explanation of the invention as claimed.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The accompanying drawings. which are incorporated in
`and constitute a part of this specification. illustrate embodi-
`ments of the invention and, together with the description.
`serve to explain the objects. advantages. and principles ofthe
`invention.
`In the drawings
`FIG.
`1
`is a block diagram of a network including an
`arrangement constructed in accordance with the subject
`invention for providing a multi-stcp interactive dialog over a
`network;
`FIG. 2 is a more detailed block diagram ofa client corn—
`puting device of FIG. 1;
`FIG. 3 is a more detailed block diagram ofa dialog engine
`server of FIG. 1:
`FIG. 4 is drawing illustrating the relationship between
`knowledge containers. taxonomies and taxonomy tags in
`accordance with an embodiment ofthe present invention:
`FIG. 5 shows one embodiment of knowledge containers
`that include five main components:
`FIG. 6 is a drawing illustrating taxonomies for trouble-
`shooting printer problems;
`FIG. 7 is a drawing illustrating basic constraints in accor-
`dance with an embodiment of the present invention:
`FIG. 8 is a drawing illustrating negated constraints in
`accordance with an embodiment of the present invention;
`FIG. 9 is a drawing illustrating conditional constraints in
`accordance with an embodiment of the present invention;
`FIG. 10 is a drawing illustrating triggers in accordance
`with an embodiment of the present invention;
`FIG. I l is a drawing illustrating the goal resolution process
`in accordance with an embodiment of the present invention:
`FIG. 12 is a drawing illustrating the goal unification pro
`cess in accordance with an embodiment of the present inven—
`tion;
`FIG. 13 is a chart illustrating the different categories of
`follow-up questions in accordzuice with an embodiment of the
`present invention;
`FIG. 14 shows a step in the interactive dialogue where the
`user can choose among the taxonomies;
`FIG. 15 is a chart illustrating a text question in accordance
`with an embodiment of the present invention:
`FIG. 16 is a chart illustrating a document driven question in
`accordance with an embodiment of the present invention:
`FIG. 17 is a chart illustrating a parameterized question in
`accordance with an embodiment of the present invention:
`FIG. 18 is a flow chart showing the operation of the multi—
`step interactive dialog system in a manner consistent with the
`present invention; and
`FIGS. 19- -21 are drawings illustrating a typical dialog.
`
`DETAILED DESCRIPTION
`
`In the following detailed description of one embodiment.
`reference is made to the accompanying drawings that form a
`part thereof and in which is shown by way of illustration a
`specific embodiment ill which the invention may be practiced.
`This embodiment is described in sufficient detail to enable
`
`10
`
`3t]
`
`4t]
`
`45
`
`50
`
`55
`
`60
`
`65
`
`those skilled in the art to practice the invention and it is to be
`understood that other embodiments may be utilized and that
`structural changes may be made without departing from the
`scope of the present
`invention. The following detailed
`description is. therefore. not to be taken in a limited sense.
`A system in accordance with the present invention is
`directed to a system (generically. an “e—service portal") and
`method for the delivery of information resources including
`electronic content (documents, online communities. software
`applications. etc.) and physical sources (expert's within the
`company. other customers. etc.) to end-users. In order to
`further convey a complete understanding of the present sys-
`tem. the following overview is provided:
`Overview
`
`The purpose ofa dialog engine is to facilitate the following
`in an electronic interaction between a human being and a
`machine (computer or other device including for exatnple a
`telephone or personal data assistant):
`a.) Find and deliver an appropriate set of knowledge con~
`tainers (as defined in previous filings) to the human;
`b.) Find and route the human to an appropriate web service
`(see definitions) or human expert;
`c.) Encapsulate the interaction between a human and a
`machine in the form ofa meta-data representation relat-
`ing to a knowledge map (knowledge session): and
`d.) Deliver the knowledge session to other applications via
`API. XML or any other form.
`The dialog engine of the present invention is designed to
`construct a “knowledge session" in the context of a knowl-
`edge map (as described in the commonly assigned. co-pend-
`ing US. patent application Ser. No. 095941.083. entitled
`“System and Method for Implementing a Knowledge Man-
`agement System.” which has previously been incorporated by
`reference).
`A knowledge session is a representation ofa user’s situa-
`tion or scenario in the context of a knowledge map. A know] -
`edge session includes text elicited from the user and a collec-
`tion of tags {as described in application Ser. No. 095941.083)
`that each represent a link to a concept node within the knowl-
`edge map and a “weight" indicating the strength of that link.
`The dialog engine is a machine for knowledge session
`management defined by at least the following operations: the
`ability to accept inputs. the ability to interface to inference
`engines. the ability to construct interactions, and the ability to
`send sessions to other sofiware.
`
`The dialog engine of the present invention is defined by:
`l.) The dialog engine creates the knowledge session
`through a plurality of input types.
`2.) The dialog engine acts on these input types by interact—
`ing with a plurality of inference engines.
`3.) The dialog engine refines the session via a plurality of
`interaction forms.
`
`The dialog engine may output sessions to search engines (or
`other applications) in the form ofa markup language based
`representation (e.g.. XML or HTML. etc.) of the knowledge
`session.
`
`Input Types:
`The dialog engine builds a knowledge session using a
`plurality of input. such as the following:
`The context ofa user’s entry into the present system (entry
`context);
`The autocontextualization (classification into a knowledge
`map, as described in the commonly assigned, co—pending
`11.5. patent application Ser. No. 091594.083, entitled “System
`and Method for Implementing a Knowledge Management
`
`

`

`5
`
`6
`
`US ?,539,656 B2
`
`System." which has previously been incorporated by refer-
`ence) of a natural language text (“a question”) entered by the
`user (question context);
`The customer data or profile maintained about a user (user
`context):
`The responses by the user to queries posed by the dialog
`engine (dialog context):
`Choices made in respect to the common ground (see deli-
`nitions) (conunon ground context);
`The choicesr’actions made by the user during the dialog
`(such as selecting a document) (interaction context).
`
`User Entry:
`The dialog engine can utilize the context 0 fa user' s “ent ry”
`into the present system environment in the form of:
`a) The link the user traversed to enter the system;
`b.) An XML (or other markup) packet describing the user‘s
`situation (a limit, a meta-data collection]:
`c.) A blob of text describing the users situation which can
`be autocontextualized.
`
`Each of these inputs is mapped to the knowledge map to
`create tags.
`
`Natural Language:
`The dialog engine can elicit front the user a statement o fthe
`user’s problem. issue. or request in the form of keywords or
`natural language. This is the user‘s “question". This natural
`language is converted into a set of tags using the autocontex~
`tualimtion process.
`Profile
`
`User ”profiles" can come in the form of:
`I.) a structured data record obtained from a customer rela-
`tionship management ((TRM) or cttstonter database;
`2.) a packet containing meta-data in the form of tags:
`3.) a user knowledge container (as described in co—pending
`U.S. patent application Ser. No. 091594.083).
`
`Each of these inputs is mapped to the knowledge map to
`create tags.
`
`Dialog Response
`The dialog engine interacts with users to create and refine
`the knowledge session tags. The dialog engine utilizes a range
`of interaction forms (described below) to elicit additional
`information front the user.
`
`System Interactions
`‘lhe user makes choices and selections during the dialog
`interaction not specifically associated with the dialog itself.
`These selections include:
`
`a) Browser interactions (cg. choosing the back button);
`b.) Interactions with documents (cg. choosing to view a
`knowledge container): and
`c.) Interactions with GUI elements.
`
`These four interaction forms represent the set of logical
`mechanisms for taking an initial session state as defined by l
`or more of the 3 initia