9656B2
`
`
`
`*P
`
`r
`
`US0075
`
`(12)
`
`United States Patent
`Fratkina et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,539,656 B2
`May 26, 2009
`
`SYSTEM AND METHOD FOR PROVIDING AN
`INTELLIGENT MULTI-STEP DIALOG WITH
`A USER
`
`wo
`wo
`
`WO-99/ 18526
`WO-2000077690 Al
`
`4/1999
`12/2000
`
`OTHER PUBLICATIONS
`
`Inventors: Raya Fratkina, Hayward, CA (US);
`Monica Anderson, San Jose, CA (US);
`Mark A. Angel, Cupertino, CA (US):
`Max Copperman, Santa Cruz, CA (US),
`Scott B. Huffman, Redwood City. CA
`(US): David Kay, Los Gatos, CA (US);
`Robert Stern, Cupertino, CA (US)
`Assignee: Consona CRM Ine., Indianapolis, IN
`{US}
`
`The impact of 4 simulation-based learning design project on student
`learning Chung, G.K.W.K.; Harmon, T.C., Baker, E.L.; Education,
`IEEE Transactions on vol. 44, [ssue 4, Nov. 2001 pp. 390-398 Digital
`Object Identifier 10,1 109/13,65789."
`
`(Continued)
`
`Primary Examiner—Michael B Holmes
`(74) Attorney, Agent, or Firm—Ice Miller LLP
`
`(54)
`
`(75)
`
`(73)
`
`(21)
`(22)
`(65)
`
`(60)
`
`(51)
`
`(52)
`(58)
`
`(56)
`
`(57)
`ABSTRACT
`Notice:=Subject to any disclaimer, the termofthis
`A method and system are disclosed for retrieving information
`patent is extended or adjusted under 35
`through the use of a multi-stage interaction with a client to
`U.S.C. 154(b) by 1207 days.
`identify particular knowledge content associated with a
`knowledge map. The present inventionis an application pro-
`gramrunning on a server accessed via the world-wide web or
`other data network using standard Internet protocols, a web
`browser and web serversoftware. In addition to an automated
`portion, the present invention allows a humandialog designer
`to model the way the systemelicits information, giving a
`human feel to the dialog and a better customerexperience, In
`operation, users start a dialog by directing their web browser
`io 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 contro! information\ and the
`user's responses to provide feedback to the user. The feed-
`back may include follow-up questions, relevant documents.
`and instructions to the user (e.g.. instructions to contact a
`human customer service representative). This dialog engine
`responseis 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 orsheis presented, and the cycle repeats. The
`invention can be implemented so that it can interact with
`customers through a wide variety ofcommunication channels
`including the Internet, wireless devices (e.g,,
`telephone,
`pager, etc.), handheld devices such as a Personal Data Assis-
`tant (PDA). email, and via a telephone where the auiomated
`systenris delivered using an interactive voice response (TVR)
`and/or speech-recagnition system.
`
`Appl. No.; 09/798,964
`Filed:
`Mar, 6, 2001
`Prior Publication Data
`US 2001/0049688 AJ
`Dee. 6, 2001
`
`Related U.S, Application Data
`
`Provisional application No. 60/187,472. filed on Mar-
`6, 2000.
`Int, Cl.
`(2006.01)
`G06F 17/00
`(2006.01)
`G06F 17/30
`(2006.01)
`GO6N 5/00
`TOR, eeacichouetet cc: 706/45; 707/3; 707/104.1
`Field of Classification Seareh ...00000..... 706/45
`See applicationfile for complete search history.
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4.918.621 A
`
`4/1990 Nadoetial,
`
`..c:c.cccn
`
`364/513
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`wo
`
`WO-97/38378
`
`10/1997
`
`15 Claims, 19 Drawing Sheets
`
`
`
`
`
`
`PETITIONERS - EXHIBIT 1006
`PETITIONERS- EXHIBIT 1006
`
`IPR2022-00217
`
`IPR2022-00217
`
`

`

`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.1 109
`ccecrsesselieene IOSD
`LA Olay,
`THIOGD,
`5,034,595 A
`GCC,2007,53.*
`5/1994 Katz et al.
`5,309,359 A
`“(Kanisa) Intelligized Business Processes”, (1998), 12 pgs.
`12/1994 Lamberti et al.
`5,377,103 A
`“About the [Information Manifold”, web page, | pg.
`4/1995 Katz etal.
`§,404.295 A
`“Facts Connect Care by ProAmerica—Frequently Asked Ques-
`5/1995 Krishna
`5.412.804 A
`tions’, (1998), 3 pgs.
`10/1996 Nishiyama et al.
`.......... 395/600
`5,568,640 A
`“IBM Intelligent Miner for Data”, (1998), 10 pgs.
`ZN99F Levyel al,
`seuccsns
`- 395/602
`5,600,831 A
`“IBM Intelligent Miner for Data, Version 2,1°, 2 pes.
`
`4/1997 MeDonough etal.
`ww 995/26
`5,625,748 A
`“IBM's Data Mining Technology”, (1996), 25 pgs.
`8/1997 Kirketal. w...c..0.- 995/601
`5,655,116 A
`“Industry Solutions: Markets and Applications", (Nov. L998), 3 pgs.
`
`,....
`395/600
`8/1997 Levyetal.
`5,659,725 A
`“Kana Communications—Success Story: eBay”, (Nov, 1998), 4 pgs.
`ie B9S/20
`9/1997 Catlett et al,
`5,671,333 A
`“Kana Communications——Suecess Story: Netscape”, 4 pgs,
`
`. 395/605
`3/1998 Woods .......
`5,724,571 A
`“ProAmerica Connect Care—The First Customer Care Software”,
`6/1998 Kirketal. .....
`we 395/611
`5,768,578 A
`12 pgs.
`8/1998 Dahlgren etal.
`............ 395/708
`5,794,050 A
`“ProAmerica Redefines Customer Care with Visual Warehouse”,
`
`....
`ae TOT/6
`9/1998 Wong etal.
`5,809,499 A
`IBM,(Feb, 1998), 2 pgs.
`
`...
`corner FOG6/TL
`[2/1998 Schatz et al,
`5,845,270 A
`“Quality Connect’. web page, (Nov, 1998), 2 pgs.
`3/1999 Anderson et al.
`5,878,423 A
`“Sales Connect”, web page, (Nov, 1998), 2 pgs.
`3/1999 Wical
`5,887,120 A
`“SCM—Theory of Customer Care, ProAmerica”™, (1996), 1-28.
`4/1999 Goldberg etal.
`5,895,466 A
`“Support Connect”, webpage, (Nov, 1998), 4 pgs.
`[2/1999 Breese et al.
`6,006,218 A
`“Survey Connect”, web page, (Nov. 1998), | pg.
`3/2000 Strevey etal.
`6,035,305 A *
`“The Kana Customer Messaging System”, (Nov. 1998), 2 pgs-
`4/2000 Snowet al.
`6,055,540 A
`“Using the Intelligent Miner in a Simple Scenario”, lersion 2././,
`§/2000 Wical
`6,061,675 A
`JBM, (Apr. 1998), 1-35,
`11/2000 Papierniak etal.
`6,151,584 A
`“Web Connect”, webpage, (Nov. 1998), 2 pgs.
`12/2000 Tsourikovet al,
`6,167,370 A
`Buckley, James P, “A Hierarchical Clustering Strategy for Very
`1/2001 Bealletal v.00... 7OWIGR
`6,169,992 BI*
`Large Fuzzy Databases”, /EEE dit'l Conf on Systems, Man and
`2/2001 Snowetal,
`6,185,550 Bl
`Cybernetics, 4, (1995), 3573-3578.
`3/2001 Wical
`6,199,034 Bl
`Chakrabarti, Soumen, et al., “Scalable Feature Selection, Classifica-
`6.347.313 BI
`2/2002 Ma et al.
`lion and Signature Generation for Organizing Large Text Databases
`63473517 Bl
`2/2002 Singhal
`into Hierarchical Topic Taxonomies”, The LOB Journal, 7, (1998),
`3/2002 Balasubramaniamet al,
`6.359.633 BI
`163-178.
`6.360.213 Bl
`3/2002 Wagstaffet al.
`Li, Wen-Syan, et al., “PowerBookmarks: A System for Personaliz-
`6411962 Bl
`6/2002 Kupiec
`able Web Information Organization, Sharing, and Management”,
`8/2002 Delano
`6,430,558 Bl
`Proc, ACM SIGMOD Int'l . Conf. on Management of Data, 28.
`$/2002 Warneretal, cccsuinc. TOTS
`6,434,550 Bl
`(1999), 565-567.
`8/2002 Hosken
`6438579 Bl
`Magennis, Mark, et al.. “The Potential and Actual Effectiveness of
`9/2002 Doerre et al.
`6,446,061 Bl
`Interactive Query Expansion”, Annual Int'l. ACN-SIGIR Conf an
`6,460,029 Bl
`10/2002 Fries etal.
`Research and Development in Information Retrieval, (1997)324-
`LO/2002 Wical
`6.460.034 BI
`aa2.
`6,493,697 BI* [2/2002 Stieretal. o.o..c-cu... 706/50
`Stodder, David, et al., “Yoward Universal Business Intelligence: An
`6,538,560 Bl
`3/2003 Stobbe et al.
`Interview with Janet Perna”, (1997),6 pgs.
`6,549,949 BI *
`4/2003 Bowman-Amuah ......... 709/236
`Tkach, Daniel S., “Information Mining with the 18M Intelligent
`6,556,671 Bl
`4/2003 Beauvois
`Miner Family”, An IBM Sojiware Solutions White Paper, (1998),
`6,581,056 Bl
`6/2003 Rao
`1-29.
`6,598,018 Bl
`7/2003 Junqua
`Wong, Jacqueline W.. et al, “Action; Automatic Classification for
`6,636,853 Bl
`10/2003 Stephens, Jr.
`Full-Text Documents”, Association ofComputing Machinery SIGIR
`6,643,640 BI
`11/2003 Getchiuset al.
`Forum, 30, (1996),2641.
`6,687,696 B2
`2/2004 Hofmann et al.
`
`“Amazon.com archive’,—http://web.archive.org/web/web
`
`6.732.088 Bl
`4/2004 Glance
`19991013091817/hilp://amazon.com, Web page from Oet. 13, 1999;
`6,766,320 Bl
`7/2004 Wang etal.
`Copyright 1996-1999; retrieved Jan. 7, 2007, 2.
`6.980.984 BL* [2/2005 Huffmanetal. 220... 7073
`“eBay - Your Personal Trading Community”. http: web.archive.org’
`4/2007 Bode etal.
`....
`7,206,778 B2*
`
`web! 199901170335 159/pages.ebay.com/aw/index.html,
`Page
`last
`2002/0027567 Al
`3/2002 Niamir
`updated Jan. 16, 1999; Copyright 1995-1998; retrieved Jan. 12, 2007,
`2002/0103798 Al
`8/2002 Abrol etal,
`| pe.
`2005/0055321 Al
`3/2005 Fralkinaet al.
`“EP Office Action”, EPC Patent Application No, 00939890.0 dated
`Jul, 29, 2004.
`2007/0033221 Al
`2/2007 Coppermanetal,
`“InQuira Information Manager Data Sheet”, Jaformation Manager
`Jor InQuira 7,(2005), 2 pages.
`“Non-Final Office Action”, Mailed Apr. 12, 2007 for U.S. Appl. No.
`10/889,888, 12 pgs.
`“Non-Final Office Action”, Mailed Oct. 31, 2002 for U.S. Appl. No.
`09/594,083, 17 pas.
`“Notice of Allowability”. Mailed Apr. 18, 2003 for U.S. Appl. No.
`09/594,083, 6 pgs.
`“Notice of Allowance”, Mailed Mar. 14, 2007 for U.S. Appl. No.
`10/610,994, 10 pgs.
`“Notice of Allowance”, Mailed Jun. 19, 2006 for LS. Appl. No.
`10/610,994, 25 pgs.
`“Notice of Allowance”, Mailed Mar 14. 2003 for U.S. Appl No-
`09/594,083, LL pgs.
`
`Symbolic interpretation of artificial neural networks Taha, L.A;
`Ghosh, J.; Knowledge and Data Engineering, IEEE Transactions on
`vol. 11, Issue 3, May-Jun, 1999 pp, 448-463 Digital Object Identifier
`10,1 109/69.774103.*
`Organizational Experience Management Through Knowledge
`Maps - An Ontological Approach Neshatian, K., Kharrat, M.;
`Khamaneh, $.B.; World Automation Congress, 2006. WAC “06 Jul.
`24-26, 2006 pp. 1-8 Digital Object Identifier 10.1 109/WAC.2006.
`376046."
`Building Knowledge Flow of Textual Topics for the e-Science
`Knowledge Grid Luo, Xiangfeng; Yu, Zhian; Grid and Cooperative
`
`......... 707/104.1
`
`OTHER PUBLICATIONS
`
`

`

`US 7,539,656 B2
`Page 3
`
`“Supplemental Notice ofAllowability”, Mailed feb, 26, 2007 for U.S.
`Appl. No. 10/610,994, 20 pps.
`“WO 2000077690 Search Report”, PCT Search Report of Interna-
`tional Application No. PCT US00/ 16444,
`Downey, S., “Using virtual reality to construct knowledge”, /rontiers
`in Education Conference (1), (1998), 392.
`Eppler. M. J.. “Making Knowledge visible (hrough mtranet knowl-
`edge maps: concepts, elements, cases Eppler”, System Sciences; Pro-
`ceedings of the 34th Annual Hawaii tnternational Conference.
`(2001), 1-10,
`Kuo, R. et all, “Difficulty Analysis for learners in problem solving
`process based on the knowledge map", Advanced Learning Tech-
`nologies, (2003), 386-357,
`Mularz, D,, et al., “Integrating concept mapping and semantic Web
`technologies forknowledge management”, (St International Work-
`shop on Database and Expert Systems Applications, 2004. Proceed-
`ines, (2004) , 449-453,
`
`Pele, K.1,, “Knowledge system ofengineering and technology man-
`agement", Technology Management;
`the New International Lan-
`guage, (1991), 550-553,
`Rouse. W_B., et al., “Knowledge maps forknowledge mining: applic-
`tion to R&Ditechnology management”, [EEE Transactions on Sys-
`tems, Man and Cybernetics, Part C: Applications and Reviews, (Aug.
`1998), 309-317,
`Saad. A., et al, “A knowledge visualisation tool for teaching and
`learning computer engineering knowledge, concepts. and skills”,
`32nd Annual Frontiers in Education, 2002, FIE 2002., (2002), T2F-
`7-T2F-L0.
`Silva. P.C.. “Fuzzy congitive maps overpossible worlds”, Proceed-
`ings of1995 [EEEInternational Conference on FuzzySvstems, 1995.
`International Joint Conference of the Fourth LEEE International
`Conference on Fuzzy Systems and The Second International Fuzzy
`Engineering Symposium, (Mar. 1995), 555-560,
`
`* cited by examiner
`
`

`

`U.S. Patent
`
`May 26, 2009
`
`Sheet 1 of 19
`
`US 7,539,656 B2
`
`12
`
`
`
`
`
`
`
`34
`
`18
`fo [IJT10)
`
`1 G
`
`ATEWAY
`
`32
`
`32
`
`32
`
`YT
`
`company
`EXTRANET
`
`PUBLIC
`NETWORK
`
`: P
`
`Ayaan
`aan
`
`
`|
`
`\
`
`32
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 2 of 19
`
`US 7,539,656 B2
`
`101
`
`106
`
`108
`
`MEMORY
`
`132
`
`130
`
`
`
`BROWSER
`PROGRAM
`
`OPERATING
`SYSTEM
`
`ADAPTOR
`
`DISPLAY
`
`112
`
`110
`
`KEYBOARD
`
`USER INTERFACE
`ADAPTOR
`
`114
`
`/0
`ADAPTOR
`
`1
`
`POINTING
`DEVICE
`
`115
`
`DISK
`STORAGE
`
`120
`
`54
`
`COMM
`ADAPTOR
`
`FIG. 2
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet3 of 19
`
`US 7,539,656 B2
`
`24
`
`\
`
`201
`
`213
`
`206
`
`DISPLAY
`
`208
`
`212
`
`KEYBOARD
`
`m1
`
`POINTING
`DEVICE
`
`215
`
`DISK
`STORAGE
`
`202
`
`230
`
`MEMORY
`232
`
`INFORMATION
`
`DIALOG
`ENGINE
`
`OPERATING
`SYSTEM
`
`234
`
`236
`
`usns
`
`DIALOG
`
`CONTROL
`
`210
`
`USER INTERFACE
`ADAPTOR
`
`214
`
`/0
`ADAPTOR
`
`220
`
`ADAPTOR
`
`30
`
`FIG. 3
`
`

`

`bee_¢~~=
`
`~“
`
`U.S. Patent
`
`May 26, 2009
`
`Sheet 4 of 19
`
`US 7,539,656 B2
`
`KANPEVRYaVOUY[Reeny4viA >tve
`Latwhe
`
`
`
`oF
`
`\
`
`—
`
`—_
`
`
`

`

`U.S. Patent
`
`May 26, 2009
`
`Sheet 5 of 19
`
`US 7,539,656 B2
`
`(0p"ypMYSU
`
`
`
`dwaqjousbnw
`
`G‘Sls
`
`>ZLINM*DII“ABY<sOY;NO>
`payobysaau<bs0/>Syj<bso>ayy“gg6iul<a>
`
`
`10}buryoo,‘<uosuad/>unwWyjny}j09G<wossad>
`
`
`<a}opuonoidxa/>6§6/1¢/Z|<a}0puolouidxa>
`
`
`<Wwa}/>sabsoyoAsouiwuijaid<ws3d}>ay|<q>
`
`
`<9}0puol}0a19/>§8///9<a}0PU0!}Da19>
`
`<JOYIND\
`
`‘Bunsodasawoou!ulsalyojnbaus
`
`
`
`C60“PNYXd]
`
`GyO:pnb4
`
`CQ'Q:uOISOAyxD]
`
`SOVLAWONOXVL
`
`VIVd-VLAN
`
`JALLVYLSININGY
`
`
`
`"Dapnyoul
`
`<d>
`
`
`
`LNJINODC3XYVW
`
`SNM
`
`
`
`LN3LNOD“TWNID!YO
`
`
`

`

`U.S. Patent
`
`May 26, 2009
`
`Sheet 6 of 19
`
`US 7,539,656 B2
`
`
`
`SWA1E0YdYALNIYdONILOOHSITIENONLYO4SIINONOXVL
`
`
`
`
`
`
`
`NOIWONdd¥
`
`Ole
`
`9‘Sl4
`
`
`

`

`U.S. Patent
`
`May 26, 2009
`
`Sheet 7 of 19
`
`US 7,539,656 B2
`
`QSREORSVi
`
`ASNe\\Qo-oN&::ASSNSSQW
`
`PATH
`
`FIG. 7
`
`UNDER (GC)
`
`ONS
`
`Roore<eSXSde‘
`
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 8 of 19
`
`NOT-UNDER (G
`
`NOT-AT (G)
`
`rsENNaif,©“woREO)
`OoLSLAS
`DPS©TON
`rmpo
`
`310
`
`FIG. 8
`
`ODQS
`
`de
`
`co
`
`

`

`U.S. Patent
`
`Sheet 9 of 19
`
`UNDER—IF-TAGGED
`
`Y
`
`gOo0G
`
`WY
`
`aNIWR-\SQ:REE|
`
`FIG. 9
`
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 10 of 19
`
`US 7,539,656 B2
`
`1040
`1030
`
`createGoal
`
`BREAKFAST
`
`
`node=breakfast;
`
`1010
`
`
`
`
`
`
`
`
`1020
`
`
`SCRAMBLED
`
`POACHED
`
`BENEDICT
`
`WITH SYRUP
`
`WITHOUT
`SYRUP
`
`
`
`BREAKFAST
`
`PANCAKES
`
` DINNER
`
`
`FIG. 10
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 11 of 19
`
`US 7,539,656 B2
`
`DIALOG STATE
`
`QUESTIONS GENERATED
`DURING DIALOG AND USER
`ANSWERS (SELECTIONS)
`
`ITERATION N
`
`SCRAMBLED
`
`fas
`
`WHICH OF THE FOLLOWING
`WOULD YOU LIKE TO GET?
`
`ITERATION N+1
`
`HOW WOULD YOU LIKE
`
`YOUR EGGS PREPARED?
`
`FIG.
`
`11
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 12 of 19
`
`US 7,539,656 B2
`
`DIALOG STATE
`
`
`
`
`
`
`QUESTIONS GENERATED
`DURING DIALOG AND USER
`ANSWERS (SELECTIONS)
`
`ITERATION N
`
`ARE YOU ON ANY DIET?
`
`fj m veqrharia
`
`i
`
`WHICH OF THE FOLLOWING
`
`ITERATION N+1
`
`if (breakfast, confirmed)
`
`createGoal
`
`node=pancakes;
`
`WOULD YOU LIKE TO GET?
`
`
`
`wossur[V
`
`
`
`
`
`HOW WOULD YOU
`LIKE YOUR PANCAKES?
`
`WITHOUT SYRUP
`
`FIG. 12
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 13 of 19
`
`US 7,539,656 B2
`
`Follow-up Questions
`
`e
`
`*
`
`SYSTEM ASKS USER FOLLOW-UP QUESTIONS BASED ON ACTIVE GOALS
`-
`(CQ: CLARIFYING QUESTION
`-
`DQ: DOCUMENT QUESTION
`-
`TEXT QUESTION
`
`SYSTEM CAN OFFER USER A CACHED QUESTION
`-
`PQ: PARAMETERIZED QUESTION
`
`FIG. 15
`
`

`

`U.S. Patent
`
`OOLT
`
`
`
`
`
`anboTetqsatIoOeIEqUT
`
`May 26, 2009
`
`Sheet 14 of 19
`
`//®YUwe
`OLLIO9LTjf
`
`
`INSWANISSYYSLSN1D
`
`
`
`NOILDA1SSAWONOXVL
`
`
`
`NOILO31SSwalSNlo
`
`US 7,539,656 B2
`
`
`
`“SOTWOUOXeoYHuoweesooyoueoJ9sSNsui
`
`vl‘Sls
`
`O£LI
`
`OSLI
`
`OrLT
`
`
`
`IN3W3ANIS3YAYINO
`
`
`

`

`U.S. Patent
`
`May 26, 2009
`
`Sheet 15 of 19
`
`US 7,539,656 B2
`
`TQ - Text Question
`
`WHAT KIND OF BREAKFAST FOOD WOULD YOU LIKE TO HAVE TODAY:
`
`(PLEASE TYPE IN)
`
`Scrambled eggs
`
`*
`
`*
`
`TAXONOMY NAVIGATION QUESTION
`
`USER TYPES IN TEXT THAT WILL BE AUTOCONTEXTUALIZED TO
`A PLACE IN THE TAXONOMY
`
`FIG. 15
`
`DOs - Document Driven Question
`
`THE FOLLOWING DISHES ARE LEFT IN THE KITCHEN.
`PLEASE CHOOSE THE ONE(S) YOU WOULD LIKE TO GET:
`a 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
`FIG. 16
`
`PQ - Parameterized Question
`
`KANISTAURANT IS FAMOUS FORIT’S CHERRY PIES.
`WOULD YOU LIKE TO TRY A PIECE?
`
`*
`
`*
`
`SHORTCUT OUT OF DIALOG
`
`A GUESS ABOUT LIKELY USER INTENTIONS
`
`~ FREQUENTLY ASKED
`
`— IMPORTANT
`
`FIG. 17
`
`

`

`U.S. Patent
`
`May 26, 2009
`
`Sheet 16 of 19
`
`US 7,539,656 B2
`
`USER POSES QUESTION
`TO DIALOG ENGINE
`
`1820
`
`DIALOG ENGINE
`CREATES INITIAL GOALS
`
`DIALOG ENGINE POSES
`FOLLOW-ON QUESTION TO USER
`
`
`
`1840
`
`DIALOG ENGINE RESOLVES GOALS
`
` 1810
`
`
`
`
`
`
`1850
`
` ANY
`
`REMAINING
`GOALS?
`
`
` RETURN RANKED
`DOCUMENTS TO USER
`
`FIG. 18
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 17 of 19
`
`US 7,539,656 B2
`
`Example: Dialog Walkthrough
`
`
`
`HOSTESS: “YES?”
`
`USER:
`
`"TWO FOR LUNCH”
`
`WAITER:
`
`““WOULD LIKE ANY DRINKS TODAY?"
`
`HN”
`
`“DO YOU HAVE ANY DIETARY CONSTRAINTS?”
`
`"YES,
`
`| AM ON HIGH-PROTEIN DIET”
`
`"WOULD YOU LIKE BREAKFAST OR LUNCH FOOD?"
`
`FIG. 19
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 18 of 19
`
`US 7,539,656 B2
`
`Restaurant Taxonomies
`
`DRINK
`
`PREFERENCE
`
`FIG. 20
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 19 of 19
`
`US 7,539,656 B2
`
`Example: Dialog Walkthrough
`(continued)
`
`
`
`“ BREAKFAST”
`
`“WE HAVE EGGS AND PANCAKES. WHAT WOULD YOU LIKE?”
`
`“EGGS”
`
`“SCRAMBLED, POACHED OR BENEDICT?”
`
`"SCRAMBLED"
`
`"HERE IS YOUR CHECK. THANKS FOR COMING”
`
`FIG. 21
`
`

`

`US 7,539,656 B2
`
`1
`SYSTEM AND METHOD FOR PROVIDING AN
`INTELLIGENT MULTI-STEP DIALOG WITH
`AUSER
`
`RELATED APPLICATIONS
`
`‘This application claims priority to the following applica-
`tons:
`
`2
`words and/or phrases. By simply searching for specific key
`words, prior art search enginesfail 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.
`
`ww
`
`SUMMARY OF THE INVENTION
`
`U.S. Provisional application No, 60/187.472. entitled
`“System and Method lor Producing anIntelligent Multi-Step
`Dialog with a User,” filed Mar. 6, 2000.
`The following identified U.S. patent applicationis relied
`upon and hereby incorporated by reference in this applica-
`tion:
`
`U.S. patent application Ser. No. 09/594.083.entitled “Sys-
`tem and Method for Implementing a Knowledge Manage-
`ment System.”
`
`FIELD OF THE INVENTION
`
`ha
`
`ae
`
`ac
`
`The present invention satislies the above-described need
`by providing a system and method for efficiently retrieving
`information froma 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 [airly simple
`This invention relates to systems and methods for retriev-
`navigation rules that allowthe inventionto engage customers
`ing information and. more particularly, to systems and meth-
`in a rich, persoualized dialog.
`ods for providing a multi-step conversation-like interaction
`The present
`invention supports a model of interaction
`betweenaperson and a computer or other device to refine and
`between a machine anda humanbeing that closely models the
`satisfy the person’s request for information.
`way people interact with eachother. [t allows the user to begin
`with an incomplete problem description and elicits the
`unstated elements ofthe description—whichthe user may not
`knowat 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 ofthe problem domain; without requiring the user to
`answer questions one at a time, or to answerall of the ques-
`tions posed; and without imposing unnecessary restrictions
`on the order in which questions are posed to the user. The
`presentinvention allows the dialog designer to mode! the way
`an expert elicits information, giving a humanfeelto the dialog,
`and a better customer experience.
`In one embodiment, the present invention is an application
`program running ona server accessed via the world-wide web
`or other data network using standard Internet protocols. a web
`browser and web server sofiware. In operation, users start a
`dialog bydirecting their web browser to a designated web
`page. Mis web page asks the user someinitial questions that
`are then passed to a dialog engine. The dialog engine then
`applies its methods and algorithms toa knowledge map, using
`dialog contro] information 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 (PDA), email, and via a telephone where the auto-
`mated system is delivered using an interactive voice response
`(IVR) and/or speech-recognitionsystem.
`Additional features and advantages ofthe invention will be
`set forth in the deseription 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-
`
`BACKGROUND
`
`Akey resource of most, ifnotall 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. [n other cases, the answer
`may have existed in the enterprise atone 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
`(predefined hyperlinks) lor customers to navigate to the infor-
`mation they need, or they provide simple “lookup”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 customer in a multiple step interac-
`tion (no conversational dialog), wherein the information is
`elicited from the customer.
`
`Other current approaches for providing support informa-
`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” siructures 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.
`Sull 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 information. 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
`
`uia
`
`GtS
`
`65
`
`

`

`US 7,539,656 B2
`
`3
`tems. 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
`lt
`description and the following detailed description are exem-
`plary and explanatory and are intended to provide further
`explanation ofthe invention as claimed.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`4
`those skilled in the art to practice the inventionand 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 canient (documents, online communities, software
`applications. ete.) and physical sources (experts within the
`company, other customers, etc.) to end-users. In order to
`further convey a complete understanding ofthe present sys-
`lem,the following overview is provided:
`Overview
`The purpose of a dialog engineis 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 previousfilings) to the human;
`b.) Find and route the humanto 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 ofa knowl-
`edge map (as deseribed in the commonly assigned, co-pend-
`ing US, patent application Ser. No, 09/594,083, entitled
`“System and Method for Implementing a Knowledge Man-
`agement System,” which has previously been incorporated by
`reference).
`A knowledge session Is 4 representation of a user's situa-
`lion or scenario in the context of a knowledge map. A knowl-
`edge session includestext elicited from the user and a collec-
`tion oftags (as described in application Ser, No. 09/594,083)
`that each representa link to a concept node withinthe knowl-
`edge map and a “weight” indicating the strength ofthat link.
`The dialog engine is a machine for knowledge session
`managementdefined by at least the following operations: the
`ability to accept inputs, the ability to interlace to inference
`engines, the ability to constructinteractions, and the ability to
`send sessions to other sofiware,
`The dialog engine of the present inventionis defined by:
`1.) The dialog engine creates the knowledge session
`through a plurality of input types.
`2.) The dialog engineacts 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 of a markup language based
`representation (¢.g.. XML or HTML.ete.) of the knowledge
`session.
`
`Input ‘Types:
`The dialog engine builds a knowledge session using a
`plurality ofinput, 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
`U.S. patent application Ser. No.09/594.083. entitled “System
`and Method for Implementing a Knowledge Management
`
`The accompanying drawings, which are incorporated in
`and constitute a part ofthis specification, illustrate embadi-
`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-step interactive dialog over a
`network:
`FIG, 2 is a more detailed block diagram of a client com-
`puting device of FIG. 1;
`FIG. 3 is a more detailed block diagram ofa dialog engine
`server of PIG. 1:
`FIG. 4 is drawing illustrating the relationship between
`knowledge containers,
`taxonomies and taxonomy tags in
`accordance with an embodiment of the 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 ofthe present invention;
`PIG. 8 is a drawing illustrating negated constraints in
`accordance with an embodiment ofthe present invention:
`FIG. 9 is a drawing illustrating conditional constraints in
`accordance with an embodiment of the present invention;
`PIG, 10 as a drawing illustrating triggers in accordance
`with an embodiment of the present invention;
`FIG. 11 isa drawing illustrating the goal resolution process
`in accordance with an embodimentof the present invention;
`FIG. 12 is a drawing ilustrating the goal unification pro-
`cess in accordance with an embodiment of the present inven-
`tion;
`FG. 13 is a chart illustrating the different categories of
`follow-up questions in accordance with an embodiment of the
`present invention:
`PIG. 14 shows a step in the interactive dialogue where the
`user can choose among the taxonomies:
`FIG. 15 isa chart illustrating a text question in accordance s
`with an embodiment ofthe present invention:
`PIG. 16 is achart 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 embodimentof the present invention;
`FIG. 18 is a flow chart showing the operation of the multi-
`sep interactive dialog system ina manner consistent with the
`present invention; and
`FIGS. 19.21 are drawings illustrating a typical dialog.
`
`ae
`
`40
`
`45
`
`60
`
`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 ofillustration a
`specific embodimentin whichthe invention maybe practiced.
`This embodiment is described in sufficient detail to enable
`
`

`

`US 7,539,656 B2
`
`5
`
`System,” which has previously been incorporated by refer-
`ence) ofa 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 deti-
`nitions) (common ground context):
`‘The choices/actions made by the user during the dialog
`(such as selecting a document) (interaction context),
`User Entry:
`The dialog engine can utilize the context ofa user's “entry”
`into the present system environment in the formof:
`a.) The link the user traversed to enter the system:
`b.)An XML(orother markup) packet describing the user's
`situation (a form, a meta-data collection);
`c.) A blob oftext describing the users situation which can
`be autocontextualized.
`
`Each ofthese inputs is mapped to the knowledge map to
`create tags.
`
`Natural Language:
`The dialog engine canelicit fromthe user a statement ofthe
`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 oftags using the autocontex-
`tualization process.
`Profile
`User “profiles” can come in the formof:
`L.).a structured data record obtained from a customer rela-
`uonship management (CRM)or customer database:
`2.) a packet containing meta-data in the form oftags;
`3.) auser knowledge container (as described in co-pending
`U.S. patent application Ser, No. 09/594,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
`ofinteraction forms (described below) to elicit additional
`information from the user.
`
`wa
`
`ae
`
`ac
`
`45
`
`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 (e.g, choosing the back button):
`b.) Interactions with documents (e.g. choosing to view a ~
`knowledge container): and
`c.) Interactions with GUI elements.
`
`Fach of these inputs can be translated into inferences in
`relationship to the knowledge map.
`Inference Engine Interaction:
`
`Dialog Engine Drivers
`‘The dialog engine can be driven by one or more “inference
`engines”(e.g. a stundard niles engine, a standard classifica-
`lion engine, and an autocontextualizationengine.)
`The dialog engine can support some orall ofthe following
`interaction forms:
`L.) Popular o