||||||||||||||||||||||||||||||||||l||
`
`
`
`|||l|l||||||||||||||||||||||||||||||
`
`USOO?539656B2
`
`(12} United States Patent
`Fratkina et a].
`
`[10) Patent N0.:
`(45) Date of Patent:
`
`US 7,539,656 32
`May 26, 2009
`
`(54) SYSTEM AND METHOD FOR PROVIDING AN
`INTELLIGENT MULTI-STEP DIALOG WITH
`
`W0
`W0
`
`W0-99.-"18526
`WO—EUOOUTTSOO A}
`
`4.-' I999
`|2.-"200[I
`
`A USER
`
`OTHER PUBLICATIONS
`
`(75}
`
`Inventors: Raye Fratkina. Hayward. (fA (US):
`Monica Anderson. San .1056. CA (US):
`_
`'
`-
`1
`.
`n::kciz‘p‘ggfgégtggfiglg‘ni‘élifiksy
`Scott B. Huffman, Redwood City. CA
`15:1)
`'d K . I.
`.‘ ("'t
`(T. US :
`:{;:rt 2:111 :‘yupei’t‘indd((31 (SSE
`)
`_
`(Ionsona (IRM Ine._. Indianapolis. IN
`(US)
`
`(73) Assignee:
`
`( ’B } Notice:
`
`Subject to any disclaimer.- the term Of this
`patent 15 extended or adjusted under 35
`U '5‘“ 15403) by 1207 days.
`(21) Appl. No.: 09n989964
`,
`Flled:
`
`(22)
`(65)
`
`_
`Mar. 6‘ 2091
`Prior Publication Data
`
`Dec. 6’ 2001
`US 200110049688 A]
`Related us. Appficafion Data
`
`(51)
`
`(60) Provisional application No. 50’137-472- filed on Mar.
`-
`-
`52000
`Int. (‘1.
`(2006.01)
`G062” 1.7/09
`'
`(2006.01)
`6061" 17/30
`(2006 0])
`G06N 5/0”
`‘
`_
`'
`‘
`‘
`706145. 7078‘ 707110“
`lib‘ ('1'
`(52)
`[58) held (if-(.Ia'SSIhftatltnl {Search
`T063115
`See application 1110 101' complete 53311311 111 storyi
`References Cited
`
`(56)
`
`US. PATENT DOCUMENTS
`
`4318,631 A
`
`41999 Nada 0‘ 31‘
`_
`(Continued)
`FOREIGN RA'I‘ENT DOCUMENTS
`
`364t'513
`
`The impact of'a simulation-based learning design project on student
`learning Chtmg. G.K.W.K.; Harmon. T.C.; Baker. E.I..; Education.
`IEEE Transactions onvol.44. Issue 4. Nov.300] pp.390-398 Digital
`Object Identifier 10.1 109.1 13.65789.*
`(Continued)
`Primary Stamina—Michael B Holmes
`(74} Attorney. Agent, or Firm—Ice Miller LLP
`
`(57)
`
`ABSTRACT
`
`A method and system aredisclosed [or retrieving information
`through the use of a niulti-stage interaction with a client to
`identify particular knowledge content associated with a
`knowledge map. The present invention is an application pro-
`grant 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 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
`initia
`uestions t at are t ien asse to a
`a 01 e11 inc.
`c
`"‘lq ‘
`h
`l
`p
`d
`dill= 3‘
`Th
`dialog engine then applies its methods and algorithms to a
`knowledge map. using dialog control int'ormation‘t and the
`user’s responses to provide feedback to the user. The feed-
`.
`.
`.
`back may include iollow-up questions. relevant 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 10 the user’s
`web browser. The user can then respond l'urtherto the follow-
`up questions he orshe is presented. and the cycle repeats. The
`invention can be implemented so that it can interact With
`customers through a wide variety ofconununicaiion channels
`including the Internet‘ Wireless devices (eg, 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 (IVR)
`auditor smash-recognition system.
`
`W0
`
`W0-9'2‘.-’383?8
`
`10-" I 997
`
`15 Claims, 19 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`1
`1
`
`EX1006
`EX1006
`
`

`

`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.|1099
`GCC.2007.53.*
`“(Kanisa) lntelligized Business Processes”. (1998). 12 pgs.
`“About the Information Manifold“. web page. I 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". (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. ProAmerica“. (1996). 1v28.
`“Support Connect". webpagc. (Nov. 1998). 4 pgs.
`“Survey Connect”. web page. (Nov. 1998).
`1 pg.
`“The Kana Customer Massaging System". (Nov. 1998). 2 pgs.
`“Using the Intelligent Miner in a Simple Scenario”. 1921939099 2.1.9.
`IBM. (Apr. 1998). [-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 a].. “Scalable Feature Selection. Classifica-
`tion and Signature Generation for Organizing large Text Databases
`into Hierarchical Topic Taxonomies”. The VLDB Journal. 7. (1998).
`[63-178.
`I.i. Wen-Syan. et a].. “PowerBookmarks: 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 a].. “The Potential and Actual Eflectivcness of
`Interactive Query Expansion”. Amara! Int’t‘. ACN—SIGIR Cont: on
`Research and Development in tiy’ai‘ination 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 Sofiwam Solutions White Paper. (1998).
`1—29.
`Wong. Jacqueline W.. ct 0].. “Action: Automatic Classification for
`Full-Text Documents". Association quompnn’ng Machinery SIGIR
`Forum. 30. (1996 ].26-41.
`http:.-"9web.archive.oi'gt'webr'
`archive”.
`“Amazoncom
`web
`[999101309l8l79httpz99amazoncmn. Web page from Oct. 13. [999;
`Copyright 1996-1999; retrieved Jan. 7. 2007. 2.
`“eBay -Your Persona] Trading Community‘. httpn'twebarchiveorg’
`websr 199901 17033 1599pagcs.ebay.com-“awtindexhtml.
`Page
`last
`updated Jan. 16. 1999. Copyright 1995-1998. retrievedJan. 12.2007.
`1 pg.
`“131’ Office Action“. EPC Patent Application No. 009398900 dated
`Jul. 29. 2004.
`“InQuira Information Manager Data Sheet". Infin'mnnon Manager
`for Ian‘ra 7. (2005). 2 pages.
`“Non—Final Ollice Action". Mailed Apr. 12. 2007 forU.S. App]. No.
`109889.888. 12 pgs.
`“Non-l‘inal Oflice Action". Mailed Oct. 31. 2002 for US. App]. No.
`099594.083. 1‘9 [333.
`“Notice of Allowability". Mailed Apr. 18. 2003 for US. App]. No.
`099594.083. 6 pgs.
`“Notice of Allowance". Mailed Mar. 14. 2007 for US. App]. No.
`109010.994. 10 pgs.
`“Notice of Allowance”. Mailed .1101.
`[09610.994. 25 pgs.
`“Notice of Allowance”. Mailed Mar. 14. 2003 for US. App]. No.
`099594.083. 11 pgs.
`
`I9. 2006 for US. App]. No.
`
`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.270 A
`5.878.423 A
`5.887.120 A
`5.895 .466 A
`6.006.218 A
`6.035.305 A ‘V
`6.055.540 A
`6.061.675 A
`6.151.584 A
`6.167.370 A
`6.l69.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 131
`6.438.579 131
`6.446.061 B1
`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 B1
`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 B2”
`200290027567 Al
`200290103798 Al
`200590055321 Al
`20079003322! Al
`
`3649513
`
`..
`
`
`
`7079104.]
`
`79199] Ltl eta].
`591994 Katz et a].
`1291994 Lamberti el al.
`491995 Katz et a].
`591995 Krishna
`1091996 Nishiyama eta].
`395.9600
`291997 Levy el al.
`. 3959602
`
`491997 McDonough et a]
`.. 39592.6
`. 3959601
`891997 Kirketal.
`
`. 3959600
`891997 Levy et a1.
`991997 Catlettetnl.
`395920
`.3959605
`391998 Woods
`
`691998 Kirk eta].
`3959611
`891998 Dahlgren ct a1.
`3959708
`991998 Wong et a].
`70796
`1291998 Schatzetal.
`706911
`391999 Anderson et al.
`391999 Wical
`491999 Goldberg et a1.
`1291999 Breese et a].
`392000 Streveyetal.
`92000 Snow eta].
`592000 Wieal
`1192000 Papierniak et a1.
`1292000 Tsourikov et a1.
`192001 Beali el al. .............. 7079103 R
`29200] Snow ct a].
`39200] Wieal
`292002 Ma eta].
`292002 Singhal
`392002 Balasubramaniam cl a1.
`392002 WagstalTet a].
`692002 Kupiec
`92002 Delano
`892002 Warneret a1.
`892002 ilosken
`992002 Doerreetal.
`1092002 Fries eta].
`[092002 Wical
`1292002 Stieret a].
`392003 Stobbeeta].
`492003 Bowman-1111103.]:
`492003 Beauvois
`92003 Rate
`792003 Junqua
`1092003 Stephens. Jr.
`1 192003 Getchius et a].
`292004 Hofmam'l et al.
`592004 Glance
`92004 Wang et a].
`1292005 Huffman et a1.
`492007 Bodeeta].
`392002 Niamir
`892002 Abrol et al.
`392005 Fratkina et 3].
`292007 Coppermanet al.
`
`70793
`
`706950
`
`709.9236
`
`70793
`70795
`
`0'I‘ll 13R PUBI .IC18'I‘lONS
`
`Symbolic interpretation of artificial neural networks 'I‘al'ia. 1.A.;
`Ghosh. 1.; Knowledge and Data Engineering. 11313131 ‘I‘ransactions on
`vol. 11. Issue 3. May-Jun. 1999 pp. 448-463 Digital Object Identifier
`10.1109.-"69.774103."
`Organiralional Experience Management Through Knowledge
`Maps - An Ontological Approach Neshatian. Ks Khanat. M4
`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 ’l‘extual Topics for the e-Science
`Knowledge Grid Luo. Xiangfeng; Yu. Zhian; Grid and Cooperative
`
`2
`2
`
`

`

`US 7,539,656 B2
`Page 3
`
`“Supplemental Notice ofA]lowabili1y".Mniled feb. 26. 2007 forUS.
`App]. No. 10.-"610.994. 20 pgs.
`“W0 2000077690 Search Report”. PCT Search Report oflnlerna-
`tiona] Application No. PCTtUSODt'IGMti.
`Downey. S. . “Using virtual reality to construct knowledge". i‘mtttiem'
`in Education Conference (I). (1998), 392.
`Eppler. M. J .. "Making Knowledge visible through intranet knowl-
`edge maps: concepts, elements, cases Eppier", System Sciences; Pro-
`eeeviings of the 34th Ai'imtatr Hawaii international Con erenee.
`(2001). 1-10.
`K110. R.. et 31.. “Difficulty Analysis for ieamers in problem solving
`process based on the knowledge map”. Advmiced Learning Territ-
`noiogies. (2003). 386-381
`Mularz. 1).. et 211.. “Integrating concept mapping and semantic Web
`technologies for knowledge mmgement”, i5tir internationai Work—
`shop on Dominate and Expert Systems Appiieations, 2004. Proceed—
`ings.. (2004) . 449-453.
`
`Pele. K. 1.. "Knowledge system of engineering and technology man-
`agement”.
`i'eciniaiag’ Management; the New internationai Lan-
`guage. (1991). 550-553.
`Rouse. W. B. . et al.. “Knowledgemaps for knowledge mining: applie-
`tion to R&Ditechnology management“. {EEE Transactions on Sys-
`tems, Man and Cybernetim, Part C: Appiimtiam' and Reviews. (_ Aug.
`1998). 309-317.
`Saad. .v‘\.. et ai.. “A knowledge visualisation too] for teaching and
`learning computer engineering knowledge. concepts. and skills".
`32ndAnnnai Harriers in Education. 2002. FIE 2002., ( 2002). TEF-
`7-T2F-10.
`Silva. P. C. "Fuzzy congitive maps over possible worlds”. Piecewi—
`ings aft 995 JEEE internationai Conferenee on Fuzzy Einstenis. i995.
`fitternationai Joint CorJeienCe of the Fonrtit [FEE internationai
`Conference an inn}; Systems and The Second International Hts: .-
`Engineering Symposinm.. (Mar. 1995). 555-560.
`
`* cited by examiner
`
`3
`
`

`

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

`

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

`

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

`

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

`

`US. Patent
`
`May 26, 2009
`
`Sheet 5 of 19
`
`US 7,539,656 B2
`
`8K
`
`mowwflmélma
`
`QEo.Ho:mm:E
`
`
`
`lllllllll2828229%
`
`86¢:ngA90\vmm_Ao_ov2:.wwmflc_Aav
`
`L83302.AcoflvaEEtzxsoumAEoEmav
`
`
`A38co:E_axo\vmm\_m\m_ABou8:93wa
`
`
`AEE<v$mBEboEEzmaAELBVmEAn—v
`
`A$88288?mw\n\oABoucozoobv
`
`
`GEE/XE;.o___m.smcofisv
`
`55:88QESEE8:238:
`Bo”c2854”:85Eozoxfi
`
`m.o_u._
`
`8362
`
`mxz:
`
`
`
`So562'on
`
`28”8E
`
`(EaIKE:
`
`H._>:<Em_z__)_e<
`
`0%25288%:
`
`8
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 6 of 19
`
`US 7,539,656 B2
`
`
`
`
`
`mzfimomaEEEQ0250135305mo»$50293
`
`memowas
`
`mommuuomm
`
`..
`
`__
`
`
`
`mgzo:
`
`zozfianz
`
`OF,
`
`w.07..
`
`9
`
`
`
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 7 of 19
`
`US 7,539,656 B2
`
`
`
`
`,,}/./¢
`@«i’igy/W/I/W
`
`0
`
`0
`
`1/:,//.
`’7a?0é;/
`”z.¢7%///////IM./WM/”Maip
`
`’70
`
`FIG. 7
`
`10
`10
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 8 of 19
`
`US 7,539,656 132
`
`NOT-UNDER (6)
`
`FIG. 8
`
`11
`11
`
`

`

`US. Patent
`
`Sheet 9 01.19
`
`US 7,539,656 B2
`
`PATH-IF—TACGED (
`7/
`
`)
`
`/%
`
`I
`
`law
`(fill
`
`
`U_471.4
`m,»1%MV/@I
`
`.mW/o/éomo/WMW/o’o
`
`0
`
`FIG, 9
`
`12
`12
`
`
`

`

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

`

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

`

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

`

`US. Patent
`
`May 26, 2009
`
`Sheet 13 0f19
`
`US 7,539,656 32
`
`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 CACHE!) QUESTION
`
`-
`
`PQ: PARAMETERIZED QUESTION
`
`FKl 13
`
`16
`16
`
`

`

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

`

`US. Patent
`
`May 26, 2009
`
`Sheet 15 0f19
`
`US 7,539,656 32
`
`TQ — Text Question
`
`WHAT NND 0F BREAKFAST FOOD WOULD YOU UKE TO HAVE TDDAN
`
`(PLEASE TYPE IN)
`
`Scrambled eggs
`
`.
`
`-
`
`TAXONOU‘I’ 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
`
`18
`18
`
`

`

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

`

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

`

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

`

`US. Patent
`
`May 26, 2009
`
`Sheet 19 0f19
`
`US 7,539,656 32
`
`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
`
`22
`22
`
`

`

`US ?,539,656 B2
`
`2
`
`words andtor phrases. By simply searching 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.
`
`10
`
`SUMMARY OF THE INVENTION
`
`3o
`
`1
`SYSTEM AND METHOD FOR PROVIDING AN
`INTELLIGENT M UIII'I-STEP DIALOG WITII
`A USER
`
`REELA’I‘I—il) APPLICAITONS
`
`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:
`
`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 fonnation.
`
`BACKGROUND
`
`A key resource of most. ifnot all enterprises is knowledge.
`For example. in a customer service environment. customers
`expect prompt and correct answers to their information
`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 information to
`customers on the Internet, either provide a static structure
`(predefmed 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 custorner in a multiple step interac-
`tion (no conversational dialog), wherein the information is
`elicited from 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 i1 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
`
`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 user. The feedback may include follow-
`up questions. relevant documents. and instructions to the user
`(e.g._. 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-
`23
`23
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`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 com—
`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—
`titiri;
`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
`
`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 example 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 appropriatc'wcb 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. 09594383. 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.
`
`10
`
`3t]
`
`4t]
`
`45
`
`50
`
`55
`
`60
`
`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
`24
`24
`
`65
`
`

`

`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) (conurton 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 cotttext ofa user' 5 “entry”
`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~
`[utilization process.
`Profile
`
`User ”profiles" can come in the fonn of:
`I.) a structured data record obtained from a customer rela-
`tionship management ((TRM) or customer 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
`The 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 (c.g. 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 initial forms of context. These initia