pO
`
`*3
`
`US0075
`
`a2) United States Patent
`Fratkinaet al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,539,656 B2
`May26, 2009
`
`(54) SYSTEM AND METHOD FOR PROVIDING AN
`INTELLIGENT MULTI-STEP DIALOG WITH
`A USER
`
`wo
`WoO
`
`WO-99/18526
`WO-2000077690 Al
`
`4/1999
`12/2000
`
`OTHER PUBLICATIONS
`
`(75)
`
`Inventors: Raya Fratkina, Hayward, CA (US):
`Monica Anderson, San Jose, CA (US):
`MarkA. 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)
`
`(73) Assignee: Consona CRM Ine., Indianapolis, IN
`(US)
`
`(*) Notice:
`
`Subject to any disclaimer, the termofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1207 days.
`
`(21) Appl. No.: 09/798,964
`
`(22)
`
`(65)
`
`Filed:
`
`Mar. 6, 2001
`
`Prior Publication Data
`
`US 2001/0049688 Al
`
`Dee. 6, 2001
`
`Related U.S. Application Data
`
`(60) Provisional application No. 60/187,472, filed on Mar.
`6, 2000.
`
`(51)
`
`Int. Cl.
`(2006.01)
`GO6F 17/00
`(2006.01)
`G06F 17/30
`(2006.01)
`GO6N 5/00
`(52) U.S.Ccee 706/45; 707/3; 707/104.1
`(58) Field of Classification Search .................... 706/45
`See application file for complete search history.
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4.918.621 A
`
`4/1990 Nadoet al.
`
`...........2. 364/513
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`WoO
`
`WO-97/38378
`
`10/1997
`
`The impact of a simulation-basedlearning design project on student
`learning Chung, G.K.W.K.; Harmon, T.C.; Baker, E.L.; Education,
`IEEE Transactions on vol. 44, Issue 4, Nov. 2001 pp. 390-398 Digital
`Object Identifier 10.1109/13.65789."
`
`(Continued)
`
`Primary Examiner—Michael B Holmes
`(74) Attorney, Agent, or Firm—Ice Miller LLP
`
`(57)
`
`ABSTRACT
`
`A method and system are disclosed for retrieving information
`through the use of a multi-stage interaction with a client to
`identify particular knowledge content associated with a
`knowledge map. The present inventionis an application pro-
`gram running ona server accessed via the world-wide web or
`other data network using standard Internet protocols, a web
`browserand webserversoftware. In addition to an automated
`portion, the present invention allows a humandialog designer
`to model the way the systemelicits information, giving a
`humanfeel 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 information\ and the
`user’s responses to provide feedback to the user. The feed-
`back mayinclude follow-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 to the user’s
`web browser. The user can then respond further to the follow-
`up questionshe or she is 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 automated
`systemis delivered using an interactive voice response (IVR)
`and/or speech-recognition system.
`
`15 Claims, 19 Drawing Sheets
`
`
`
`0d
`
`=
`
`
`-boho.BO.
`j
`
`
` sald
`
`
`FF
`
`
`at
`
`1
`1
`
`EX1006
`EX 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,*
`.....ccccccceeeeeees 364/513
`FAMGL Luvet ab.
`5,034,898 A
`5/1994 Katz et al.
`5,309,359 A
`*“(Kanisa) Intelligized Business Processes”, (1998), 12 pgs.
`12/1994 Lamberti etal.
`5,377,103 A
`“About the Information Manifold”, web page, | pg.
`4/1995 Katz et al.
`5,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 etal. .......... 395/600
`5,568,640 A
`“IBM Intelligent Miner for Data’, (1998), 10 pgs.
`
`395/602
`2/1997 Levyetal.
`........
`5,600,831 A
`“IBM Intelligent Miner for Data, Version 2.1”, 2 pgs.
` 395/2.6
`4/1997 McDonoughet al
`§,625,748 A
`“IBM’s Data Mining Technology”, (1996), 25 pgs.
`. 395/601
`8/1997 Kirk etal. ...
`5,655,116 A
`“Industry Solutions: Markets and Applications”, (Nov. 1998), 3 pgs.
`
`8/1997 Levyetal. ..
`. 395/600
`5,659,725 A
`“Kana Communications—Success Story: eBay”, (Nov. 1998), 4 pgs.
`9/1997 Catlett et al.
`we 395/20
`§,671,333 A
`
`“Kana Communications—Success Story: Netscape”, 4 pgs.
`. 395/605
`3/1998 Woods ....
`§,724,571 A
`“ProAmerica Connect Care—The First Customer Care Software”,
`
`6/1998 Kirk etal... S95/61L
`5,768,578 A
`12 pgs.
`“ProAmerica Redefines Customer Care with Visual Warehouse”,
`8/1998 Dahlgren etal.
`............ 395/708
`5,794,050 A
`wee TOTI6
`9/1998 Wong etal.
`....
`5,809,499 A
`
`IBM, (Feb. 1998), 2 pgs.
`12/1998 Schatz et al. oo... 706/11
`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 Goldbergetal.
`5,895,466 A
`“Support Connect”, web page, (Nov. 1998), 4 pgs.
`12/1999 Breese etal.
`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.
`(2000 Snowetal.
`6,055,540 A
`“Using the Intelligent Miner in a Simple Scenario”, Version 2.1.J,
`5/2000 Wical
`6,061,675 A
`IBM, (Apr. 1998), 1-35.
`11/2000 Papierniak etal.
`6,151,584 A
`“Web Connect”, web page, (Nov. 1998), 2 pgs.
`12/2000 Tsourikov etal.
`6,167,370 A
`Buckley, James P., “A Hierarchical Clustering Strategy for Very
`1/2001 Beall etal. wc... 707/103 R
`6,169,992 BL*
`Large Fuzzy Databases”, JEEE Int'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-
`2/2002 Maet al.
`6347313 Bl
`tion and Signature Generation for Organizing Large Text Databases
`2/2002 Singhal
`6,347,317 Bl
`into Hierarchical Topic Taxonomies”, The VLDB Journal, 7, (1998),
`3/2002 Balasubramaniamet al.
`6,359,633 Bl
`163-178,
`3/2002 Wagstaffetal.
`6,360,213 Bl
`Li, Wen-Syan, et al., “PowerBookmarks: A System for Personaliz-
`6/2002 Kupiec
`6,411,962 Bl
`able Web Information Organization, Sharing, and Management”,
`(2002 Delano
`6,430,558 Bl
`Proc. ACM SIGMOD Int'l . Conf: on Management of Data, 28,
`8/2002 Warner et al.
`6,434,550 Bl
`(1999), 565-567.
`8/2002 Hosken
`6,438,579 Bl
`Magennis, Mark, et al., “The Potential and Actual Effectiveness of
`9/2002 Doerre etal.
`6,446,061 Bl
`Interactive Query Expansion”, Annual Int'l. ACN-SIGIR Conf. on
`10/2002 Fries et al.
`6,460,029 Bl
`Research and Development in Information Retrieval, (1997)324-
`10/2002 Wical
`6,460,034 BI
`332.
`6,493,697 BL* 12/2002 Stieretal. .......c..... 706/50
`Stodder, David, et al., “Toward Universal Business Intelligence: An
`6,538,560 Bl
`3/2003 Stobbe etal,
`Interview with Janet Perna”, (1997),6 pgs.
`6,549,949 BI*
`4/2003 Bowman-Amuah ......... 709/236
`Tkach, Daniel S., “Information Mining with the [IBM Intelligent
`6,556,671 Bl
`4/2003 Beauvois
`Miner Family”, 4n JBM Software Solutions White Paper, (1998),
`6,581,056 Bl
`(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 Bl
`11/2003 Getchiuset al.
`Forum, 30, (1996),26-A1.
`6,687,696 B2
`2/2004 Hofmann et al.
`
`“Amazon.com web—archive’,_http://web.archive.org/web/
`6.732.088 Bl
`5/2004 Glance
`19991013091817/http://amazon.com, Web page from Oct. 13, 1999;
`6,766,320 Bl
`/2004 Wangetal.
`Copyright 1996-1999; retrieved Jan. 7, 2007, 2.
`............. 707/3
`6,980,984 BL* 12/2005 Huffmanetal.
`“eBay - Your Personal Trading Community”, http://web.archive.org!
`7,206,778 B2*
`4/2007 Bodeetal. ......0......... 7TO7/S
`web/19990117033 159/pages.ebay.com/aw/index.html,
`Page
`last
`3/2002 Niamir
`2002/0027567 Al
`updated Jan. 16, 1999; Copyright 1995-1998;retrieved Jan. 12, 2007,
`2002/0103798 Al
`8/2002 Abrolet al.
`I pg.
`2005/0055321 Al
`3/2005 Fratkinaetal.
`“EP Office Action”, EPC Patent Application No, 00939890.0 dated
`2007/0033221 Al
`Jul. 29, 2004.
`2/2007 Copperman et al.
`“InQuira Information Manager Data Sheet”, Jnformation Manager
`for 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 pgs.
`“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 U.S. Appl. No.
`10/6 10,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, 1.A.;
`Ghosh, J.; Knowledge and Data Engineering, IEEE Transactions on
`vol. LL, Issue 3, May-Jun. 1999 pp. 448-463 Digital Object Identifier
`10.1109/69.774 103."
`Organizational Experience Management Through Knowledge
`Maps - An Ontological Approach Neshatian, K.; Kharrat, M.;
`Khamaneh, S.B.; World Automation Congress, 2006. WAC °06 Jul.
`24-26, 2006 pp. 1-8 Digital Object Identifier 10.1109/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
`
`.................. 7079/3
`
`OTHER PUBLICATIONS
`
`2
`
`

`

`US 7,539,656 B2
`Page 3
`
`“Supplemental Notice ofAllowability”, Mailed feb. 26, 2007 forU.S.
`Appl. No. 10/610,994, 20 pgs.
`“WO2000077690 Search Report’, PCT Search Report of Interna-
`tional Application No. PCT/US00/16444.
`Downey, S., “Using virtual reality to construct knowledge”, Frontiers
`in Education Conference (1), (1998), 392.
`Eppler, M. J., “Making Knowledgevisible through intranet knowl-
`edge maps: concepts, elements, cases Eppler”’, System Sciences; Pro-
`ceedings of the 34th Annual Hawaii International Conference,
`(2001), 1-10.
`Kuo, R., et al., “Difficulty Analysis for learners in problem solving
`process based on the knowledge map”, Advanced Learning Tech-
`nologies, (2003), 386-387.
`Mularz, D., et al., “Integrating concept mapping and semantic Web
`technologies for knowledge management”, /5th International Work-
`shop on Database and Expert Systems Applications, 2004. Proceed-
`ings., (2004) , 449-453.
`
`Pele, K. 1, “Knowledge system of engineering and technology man-
`agement”, Jechnology Management; the New International Lan-
`guage, (1991), 550-553.
`Rouse, W. B., etal., “Knowledge maps for knowledge mining: applic-
`tion to R&D/technology management”, JEEE 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. FUE 2002., (2002), T2F-
`7-T2F-10.
`Silva, P. C., “Fuzzy congitive maps overpossible worlds”, Proceed-
`ings of1995 IEEE International Conference on Fuzzy Systems, 1995.
`International Joint Conference of the Fourth IEEE International
`Conference on Fuzzy Systems and The Second International Fuzzy
`Engineering Symposium., (Mar. 1995), 555-560.
`
`* cited by examiner
`
`3
`
`

`

`U.S. Patent
`
`May26,2009
`
`Sheet1 of 19
`
`US 7,539,656 B2
`
`18
`34
`EEA
`1oO |—j|||0|
`
`GATEWAY
`
`32
`
` 24 |
`32
`
`52
`
`32
`
`52
`
`COMPANY
`EXTRANET
`
`PUBLIC
`NETWORK
`
`4
`
`

`

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

`

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

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 4 of 19
`
`US 7,539,656 B2
`
`pfZ7
`
`a
`
`<Iyi
`
`V/SATREOMA
`SK
`PieWN\
`cxOXosV
` yimn
`||/\/\iy/og\é
`\Vy|
`
`[p>
`
`y
`
`
`
`
`7
`
`
`
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 5 of 19
`
`US 7,539,656 B2
`
`
`payobysanu!<bs0/>syi<bio>au}‘ggéiUl<d>
`
`
`40}Buryoo,‘<uossad/>udwyjny}j09G¢<wosJad>
`
`
`<a}yopuonouidxa/>§6/1¢/7Z|<a}Opuolouidxe>
`
`
`
`<wa}/>sabsoyoAioulwijaid<wsa}>ay|<q>
`
`<a}0pu0l}0919/>68/1/9<a}0PU0!}D949>
`
`
`<JOUJND\>ZUNM*DII1G“APY<sOU\ND>
`
`‘punsodasawosuiulsanojnbas
`
`07—7
`
`
`
`C60“yIPNYxO]
`
`
`
`Gv'0:pnoJ4
`
`G9°Q:uoIsoAyXD
`
`
`SOVLAWONOXVL
`
`VIVO-VLIN
`
`JAILVYLSININGY
`
`(20p"pMYSul}
`
`duwiqjousbnw
`
`G‘Sls
`
`
`
`“*papnjou!
`
`SNM
`
`
`
`IN3LNODIWNISINO
`
`<d>
`
`
`
`IN3LNODO4xavn
`
`8
`
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 6 of 19
`
`US 7,539,656 B2
`
` SWIIGONd
`
`
`
`
`
`YIINIYdINILOOHSIIENOYLYOISIINONOXVL
`
`9
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 7 of 19
`
`US 7,539,656 B2
`
`AT (GC)
`
`UNDER (6)
`
`WHASTESSSSV\CsRYWSEE
`
`:SS\YSVNSSWY
`
`FIG. 7
`
`10
`
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 8 of 19
`
`US 7,539,656 B2
`
`NOT-UNDER (G
`
`(=)3:
`(=)wWRY-8
`
`YS
`
`SL,
`
`Jy
`
`NM
`
`NOT-AT (G)
`
`PAE
`rsfwSSs2RAR
`ZWTEXS
`(3FR
`
`810 #
`
`FIG. 8
`
`11
`
`

`

`U.S. Patent
`
`Sheet 9 of 19
`
`PATH-IF-TAGGED (6)
`
`yyY
`
`Lig
`
`ETNNN
`WNWOHAQQASTS
`Q—-OOCLO
`\\WotRY
`ey
`
`UNDER-IF - TAGGED
`
`[LL
`
`SIRO)
`
`FIG. 9
`
`12
`
`
`

`

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

`

`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
`
`asVV
`
`WHICH OF THE FOLLOWING
`WOULD YOU LIKE TO GET?
`
`ITERATION N+1
`
`HOW WOULD YOU LIKE
`
`YOUR EGGS PREPARED?
`
`FIG. 11
`
`14
`
`

`

`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?
`
`Fm ohn
`
`WHICH OF THE FOLLOWING
`
`ITERATION N+1
`
`if (breakfast, confirmed)
`
`createGoal
`
`node=pancokes;
`
`WOULD YOU LIKE TO GET?
`
`
`
`
`
`wossueV7
`
`
`
`
`
`HOW WOULD YOU
`LIKE YOUR PANCAKES?
`
`15
`
`

`

`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.
`
`135
`
`16
`
`

`

`US 7,539,656 B2
`
`
`
`
`
`*SsoTWOUOXe9Yy3HuowessooyduedJesNsu
`
`vlSls
`
`U.S. Patent
`
`May26, 2009
`
`Sheet 14 of 19
`
`//®YOff00LI
`
`
`
`onboTetqsATIOeI94UT
`
`OLLI
`
`O9LIjf
`
`OSLI
`
`OELI
`
`OvLI
`
`
`
`LN3SWSNIS3YAY3INO
`
`
`
`NOILOS1SSAWONOXVL
`
`
`
`INSWIANIS3YYSLSN1D
`
`
`
`NOILOSTSSYsLSN19
`
`17
`17
`
`
`

`

`U.S. Patent
`
`May26,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
`
`*
`
`e
`
`TAXONOMY NAVIGATION QUESTION
`
`USER TYPES IN TEXT THAT WILL BE AUTOCONTEXTUALIZED TO
`A PLACE IN THE TAXONOMY
`
`FIG. 15
`
`DQs - Document Driven Question
`
`THE FOLLOWING DISHES ARE LEFT IN THE KITCHEN.
`PLEASE CHOOSE THE ONE(S) YOU WOULD LIKE TO GET:
`yy 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 FOR IT’S CHERRY PIES.
`WOULD YOU LIKE TO TRY A PIECE?
`
`¢
`
`e
`
`SHORTCUT OUT OF DIALOG
`
`A GUESS ABOUT LIKELY USER INTENTIONS
`
`- FREQUENTLY ASKED
`
`— IMPORTANT
`
`FIG. 17
`
`18
`18
`
`

`

`U.S. Patent
`
`May26, 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
`
`19
`
`

`

`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?”
`
`“NO”
`
`“DO YOU HAVE ANY DIETARY CONSTRAINTS?”
`
`“YES,
`
`| AM ON HIGH-PROTEIN DIET”
`
`“WOULD YOU LIKE BREAKFAST OR LUNCH FOOD?"
`
`FIG. 19
`
`20
`20
`
`

`

`U.S. Patent
`
`May26,2009
`
`Sheet 18 of 19
`
`US 7,539,656 B2
`
`Restaurant Taxonomies
`
` DRINK
`PREFERENCE
`
`Cura)
`BREAKFAST
`LIQUOR CY Gems) Cat)
`
`2010
`
`
`
`
`wi
`= OILS
`
`HARD
`
`POACHED
`
`FIG. 20
`
`21
`21
`
`

`

`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
`
`22
`22
`
`

`

`US 7,539,656 B2
`
`1
`SYSTEM AND METHOD FOR PROVIDING AN
`INTELLIGENT MULTI-STEP DIALOG WITH
`A USER
`
`RELATED APPLICATIONS
`
`ay
`
`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 forretrieving relevant infor-
`mation from large knowledge bases. There is also a need for
`providing this capability to relatively unsophisticated users.
`
`SUMMARYOF THE INVENTION
`
`This application claims priority to the following applica-
`tions:
`
`U.S. Provisional application No. 60/187,472, entitled
`“System and Methodfor Producing anIntelligent 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. 09/594,083, entitled “Sys-
`tem and Method for Implementing a Knowledge Manage-
`ment System.”
`
`FIELD OF THE INVENTION
`
`This inventionrelates to systems and methods for retriev-
`ing information and, moreparticularly, to systems and meth-
`ods for providing a multi-step conversation-like interaction
`betweena person and a computeror other deviceto refine and
`satisfy the person’s request for information.
`
`BACKGROUND
`
`Akey 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 purchasein 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 challengeis to find the best answer and provideit
`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) for customersto 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 informationis
`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” structures or expert-system rule sets that define the
`problems and their
`resolutions
`in great detail. These
`approachesare 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 information. Thisis at least partly
`dueto the fact that languageis not only inherently ambiguous,
`but also because it is susceptible to expressing a single con-
`cept any number of ways using numerous and unrelated
`
`30
`
`The present invention satisfies the above-described need
`by providing a system and methodfor 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 knowledgestruc-
`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 inventionto engage customers
`in a rich, personalized dialog.
`The present invention supports a model ofinteraction
`between a machine anda humanbeingthat closely models the
`way people interact with eachother.It allows the user to begin
`with an incomplete problem description and elicits the
`unstated elementsof the description—whichthe user may not
`know at the beginning of the interaction, or maynot know are
`important—asking only questions that are relevant
`to the
`problemdescriptionstated so far, given the system’s knowl-
`edge of the problem domain; without requiring the user to
`answer questions oneat 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
`present invention allowsthe dialog designer to model the way
`an expert elicits information, giving a human feelto the dialog
`and a better customer experience.
`In one embodiment, the present inventionis 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 software. In operation, users start a
`dialog by directing their web browser to a designated web
`page. Mis web pageasks the user someinitial 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 pro-
`vide feedback to the user. The feedback may include follow-
`up questions, relevant documents, andinstructions 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 sheis
`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 suchas 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-recognition system.
`Additional features and advantagesofthe invention will be
`set forth in the description which followsand, inpart, 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
`
`

`

`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
`It
`description and the following detailed description are exem-
`plary and explanatory and are intended to provide further
`explanation ofthe inventionas claimed.
`
`ay
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The accompanying, drawings, which are incorporated in
`and constitute a part ofthis 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-step interactive dialog overa
`network;
`FIG, 2 is a more detailed block diagramof a client com-
`puting device ofFIG. 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 embodimentofthe present invention;
`FIG. 8 is a drawing illustrating negated constraints in
`accordance with an embodimentofthe present invention;
`FIG, 9 is a drawingillustrating conditional constraints in
`accordance with an embodimentof the present invention;
`FIG. 10 is a drawing illustrating triggers in accordance
`with an embodiment ofthe present invention;
`FIG. 11 is a drawingillustrating the goal resolution process
`in accordance with an embodimentof the present invention:
`FIG, 12 is a drawingillustrating the goal unification pro-
`cess in accordance with an embodimentof the present inven-
`tion;
`FIG. 13 is a chart illustrating the different categories of
`follow-up questions in accordance with an embodimentof the
`present invention;
`FIG. 14 showsa step inthe interactive dialogue where the
`user can choose among the taxonomies;
`FIG, 15 isa chart illustrating a text question in accordance
`with an embodimentof the present invention;
`FIG. 16 is a chart illustrating a documentdriven question in
`accordance with an embodimentofthe present invention;
`FIG. 17 is a chart illustrating a parameterized question in
`accordance with an embodimentofthe present invention;
`FIG, 18 is a flow chart showing the operationof the multi-
`step interactive dialog system in a mannerconsistent with the
`present invention; and
`FIGS. 19-21 are drawingsillustrating atypical dialog.
`
`DETAILED DESCRIPTION
`
`In the following detailed description of one embodiment,
`reference is made to the accompanying drawingsthat form a
`part thereof and in which is shown by wayofillustration a
`specific embodimentin which the invention maybe practiced.
`This embodiment is described in sufficient detail to enable
`
`4
`those skilled inthe art to practice the inventionandit 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
`descriptionis, 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 (experts 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 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 humanand a
`machine in the form of a meta-data representation relat-
`ing to a knowledge map (knowledge session); and
`d.) Deliver the knowledge session to other applications via
`API, XML orany 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 U.S. 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 knowledgesession Is a representation of a user’s situa-
`tion or scenariointhe context of a knowledge map. A knowl-
`edge sessionincludes text elicited fromthe user and a collec-
`tion of tags (as describedin application Ser. No. 09/594,083)
`that each represent a 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, andtheability to
`send sessions to other software.
`The dialog engine of the present inventionis defined by:
`1.) The dialog engine creates the knowledge session
`througha 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 of a markup language based
`representation (e.g., XML or HTML,etc.) of the knowledge
`session.
`
`30
`
`40
`
`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
`U.S. patent application Ser. No. 09/594.083, entitled “System
`and Method for Implementing a Knowledge Management
`24
`24
`
`65
`
`

`

`US 7,539,656 B2
`
`5
`System,” which has previously been incorporated by refer-
`ence) of a natural languagetext (“a question”) entered by the
`user (question context);
`The customerdata or profile maintained about a user(user
`context):
`The responses by the user to queries posed by the dialog
`engine (dialog context);
`Choices madein respect to the commonground(see defi-
`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 environmentin the formof:
`a.) The link the user traversed to enter the system;
`b.) An XML (or other markup) packet describingthe user’s
`situation (a form, 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 canelicit from the 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 intoa set of tags using the autocontex-
`tualization process.
`Profile
`
`User “profiles” can come in the formof:
`1.) a structured data record obtained from a customerrela-
`tionship management (CRM) or customer database;
`2.) a packet containing meta-data in the formof tags:
`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 andrefine
`the knowledgesessiontags. The dialog engine utilizes a range
`of interaction forms (described below) to elicit additional
`information fromthe user.
`
`SystemInteractions
`The user makes choices and selections during the dialog
`interaction not specifically associated with the dialog itself.
`These selections include:
`a.) Browserinteractions (e.g. choosing the back button);
`b.) Interactions with documents (e.g. choosing to view a
`knowledge container); and
`c.) Interactions with GUI elements.
`
`6
`These four interaction forms represent the set oflogical
`mechanisms for taking aninitial session state as defined by |
`or more of the 3 initial forms of context. These initial forms
`
`ay
`
`0
`
`are the entry context, the question context and the user con-
`text. Interaction forms ar