US007539656B2
`
`(12) United States Patent
`Fratkina et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,539,656 B2
`May 26, 2009
`
`4/1999
`WO-99/18526
`(54) SYSTEM AND METHOD FOR PROVIDING AN wo
`12/2000
`INTELLIGENT MULTI-STEP DIALOG WITH
`wo WO-2000077690 A1
`A USER
`OTHER PUBLICATIONS
`
`(75) 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)
`(73) Assignee: Consona CRM Inc., Indianapolis, IN
`(Us)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1207 days.
`(21) Appl.No.: 09/798,964
`(22) Filed:
`Mar. 6, 2001
`(65)
`Prior Publication Data
`
`( * ) Notice:
`
`Dec. 6,2001
`US 2001/0049688 A1
`Related US. Application Data
`
`(60) Provisional application No. 60/187,472, ?led on Mar.
`6, 2000.
`(51) Int. Cl.
`(2006.01)
`G06F 17/00
`(2006.01)
`G06F 17/30
`(2006.01)
`G06N 5/00
`(52) US. Cl. ......................... .. 706/45; 707/3; 707/104.1
`(58) Field of Classi?cation Search .................. .. 706/45
`See application ?le for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,918,621 A
`
`4/1990 Nado et al. ............... .. 364/513
`
`(Continued)
`FOREIGN PATENT DOCUMENTS
`
`The impact of a simulation-based learning design project on student
`learning Chung, G.K.W.K.; Harmon, T.C.; Baker, E.L.; Education,
`IEEE Transactions on v01. 44, Issue 4, Nov. 2001 pp. 390-398 Digital
`Object Identi?er 10.1109/13.65789.*
`(Continued)
`Primary ExamineriMichael B Holmes
`(74) Attorney, Agent, or Firmilce 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 invention is an application pro
`gram 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
`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 inforrnation\ 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
`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., telephone,
`pager, etc.), handheld devices such as a Personal Data Assis
`tant (PDA), email, and via a telephone where the automated
`system is delivered using an interactive voice response (IVR)
`and/or speech-recognition system.
`
`WO
`
`WO-97/38378
`
`10/1997
`
`15 Claims, 19 Drawing Sheets
`
`IPR2017-01039
`Unified EX1006 Page 1
`
`

`

`US 7,539,656 B2
`Page 2
`
`US. PATENT DOCUMENTS
`
`7/1991 Lu et al. ................... .. 364/513
`5,034,898 A
`5/1994 Katz et al.
`5,309,359 A
`5,377,103 A 12/1994 Lamberti et al.
`5,404,295 A
`4/1995 Katz et al.
`5,412,804 A
`5/1995 Krishna
`5,568,640 A 10/1996 Nishiyama et al. ........ .. 395/600
`5,600,831 A
`2/1997 Levy et al. ......... ..
`395/602
`5,625,748 A
`4/1997 McDonough et al. ...... .. 395/2.6
`5,655,116 A
`8/1997 Kirk et al. .......... ..
`395/601
`5,659,725 A
`8/1997 Levy et al.
`395/600
`5,671,333 A
`9/1997 Catlett et al.
`.. 395/20
`5,724,571 A
`3/1998 Woods ..... ..
`395/605
`5,768,578 A
`6/1998 Kirk et al. .... ..
`395/611
`5,794,050 A
`8/1998 Dahlgren et al. ..
`395/708
`5,809,499 A
`9/1998 Wong et al. ..... ..
`707/6
`5,845,270 A 12/1998 Schatz et al. ................ .. 706/11
`5,878,423 A
`3/1999 Anderson et al.
`5,887,120 A
`3/1999 Wical
`5,895,466 A
`4/1999 Goldberg et al.
`6,006,218 A 12/1999 Breese et al.
`6,035,305 A *
`3/2000 Strevey et al. ......... .. 707/104.1
`6,055,540 A
`4/2000 Snow et al.
`6,061,675 A
`5/2000 Wical
`6,151,584 A 11/2000 Papierniak et al.
`6,167,370 A 12/2000 Tsourikov et al.
`6,169,992 B1 *
`1/2001 Beall et al. ............ .. 707/103 R
`6,185,550 B1
`2/2001 Snow et al.
`6,199,034 B1
`3/2001 Wical
`6,347,313 B1
`2/2002 Ma et al.
`6,347,317 B1
`2/2002 Singhal
`6,359,633 B1
`3/2002 Balasubramaniam et al.
`6,360,213 B1
`3/2002 Wagstaffet al.
`6,411,962 B1
`6/2002 Kupiec
`6,430,558 B1
`8/2002 Delano
`6,434,550 B1
`8/2002 Warner et al. ................ .. 707/3
`6,438,579 B1
`8/2002 Hosken
`6,446,061 B1
`9/2002 Doerre et al.
`6,460,029 B1
`10/2002 Fries et al.
`6,460,034 B1
`10/2002 Wical
`6,493,697 B1 * 12/2002 Stier et al. .................. .. 706/50
`6,538,560 B1
`3/2003 Stobbe et al.
`6,549,949 B1* 4/2003 Bowman-Amuah ....... .. 709/236
`6,556,671 B1
`4/2003 Beauvois
`6,581,056 B1
`6/2003 Rao
`6,598,018 B1
`7/2003 Junqua
`6,636,853 B1
`10/2003 Stephens, Jr.
`6,643,640 B1
`11/2003 Getchius et al.
`6,687,696 B2
`2/2004 Hofmann et al.
`6,732,088 B1
`5/2004 Glance
`6,766,320 B1
`7/2004 Wang et al.
`6,980,984 B1 * 12/2005 Huffman et al. ............. .. 707/3
`7,206,778 B2 *
`4/2007 Bode et al. ................... .. 707/5
`3/2002 Niamir
`2002/0027567 A1
`2002/0103798 A1
`8/2002 Abrol et al.
`2005/0055321 A1
`3/ 2005 Fratkina et al.
`2/2007 Copperman et al.
`2007/0033221 A1
`
`OTHER PUBLICATIONS
`
`Symbolic interpretation of arti?cial neural networks Taha, I.A.;
`Ghosh, J .; Knowledge and Data Engineering, IEEE Transactions on
`vol. 11, Issue 3, May-Jun. 1999 pp. 448-463 Digital Object Identi?er
`10.1109/69.774103.*
`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 Identi?er 10.1109/WAC.2006.
`376046.*
`Building Knowledge Flow of Textual Topics for the e-Science
`Knowledge Grid Luo, Xiangfeng; Yu, Zhian; Grid and Cooperative
`
`Computing, 2007. GCC 2007. Sixth International Conference on
`Aug. 16-18, 2007 pp. 693-700 Digital Object Identi?er 10.1109/
`GCC.2007.53.*
`“(Kanisa) Intelligized Business Processes”, (1998), 12 pgs.
`“About the Information Manifold”, Web page, 1 pg.
`“Facts Connect Care by ProAmericaiFrequently 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 CommunicationsiSuccess Story: eBay”, (Nov. 1998), 4 pgs.
`“Kana CommunicationsiSuccess Story: Netscape”, 4 pgs.
`“ProAmerica Connect CareiThe First Customer Care Software”,
`12 pgs.
`“ProAmerica Rede?nes Customer Care with Visual Warehouse”,
`IBM, (Feb. 1998), 2 pgs.
`“Quality Connect”, Web page, (Nov. 1998), 2 pgs.
`“Sales Connect”, Webpage, (Nov. 1998), 2 pgs.
`“SCMiTheory of Customer Care, ProAmerica”, (1996), 1-28.
`“Support Connect”, Web page, (Nov. 1998), 4 pgs.
`“Survey Connect”, Web page, (Nov. 1998), 1 pg.
`“The Kana Customer Messaging System”, (Nov. 1998), 2 pgs.
`“Using the Intelligent Miner in a Simple Scenario”, Version 2.1.1,
`IBM, (Apr. 1998), 1-35.
`“Web Connect”, Webpage, (Nov. 1998), 2 pgs.
`Buckley, James P, “A Hierarchical Clustering Strategy for Very
`Large Fuzzy Databases”, IEEE Int’! Conf on Systems, Man and
`Cybernetics, 4, (1995), 3573-3578.
`Chakrabarti, Soumen, et al., “Scalable Feature Selection, Classi?ca
`tion and Signature Generation for Organizing Large Text Databases
`into Hierarchical Topic Taxonomies”, The VLDB Journal, 7, (1998),
`163-178.
`Li, Wen-Syan, et al., “PowerBookmarks: A System for Personaliz
`able Web Information Organization, Sharing, and Management”,
`Proc. ACM SI GMOD Int’l . Conf on Management of Data, 28,
`(1999), 565-567.
`Magennis, Mark, et al., “The Potential and Actual Effectiveness of
`Interactive Query Expansion”, Annual Int’l. ACN-SIGIR Conf on
`Research and Development in Information Retrieval, (1997),324
`332.
`Stodder, David, et al., “Toward Universal Business Intelligence: An
`Interview with Janet Perna”, (1997),6 pgs.
`Tkach, Daniel S., “Information Mining with the IBM Intelligent
`Miner Family”, An IBM Software Solutions White Paper, (1998),
`1-29.
`Wong, Jacqueline W., et al., “Action: Automatic Classi?cation for
`Full-Text Documents”, Association of Computing Machinery SI GIR
`Forum, 30, (1996),26-41.
`http://web.archive.org/web/
`archive”,
`“Amazon.com
`web
`19991013091817/http://amazon.com, Web page from Oct. 13, 1999;
`Copyright 1996-1999; retrieved Jan. 7, 2007, 2.
`“eBay -Your Personal Trading Community”, http://web.archive.org/
`web/19990117033159/pages.ebay.com/aw/index.html, Page last
`updated Jan. 16, 1999; Copyright 1995-1998; retrieved Jan. 12,2007,
`1 pg.
`“EP Of?ce Action”, EPC Patent Application No. 009398900 dated
`Jul. 29, 2004.
`“InQuira Information Manager Data Sheet”, Information Manager
`for InQuira 7, (2005), 2 pages.
`“Non-Final Of?ce Action”, Mailed Apr. 12, 2007 for US. Appl. No.
`10/889,888, 12 pgs.
`“Non-Final Of?ce Action”, Mailed Oct. 31, 2002 for US. Appl. No.
`09/594,083, 17 pgs.
`“Notice of Allowability”, Mailed Apr. 18, 2003 for US. Appl. No.
`09/594,083, 6 pgs.
`“Notice of Allowance”, Mailed Mar. 14, 2007 for US. Appl. No.
`10/610,994, 10 pgs.
`“Notice of Allowance”, Mailed Jun. 19, 2006 for US. Appl. No.
`10/610,994, 25 pgs.
`“Notice of Allowance”, Mailed Mar. 14, 2003 for US. Appl. No.
`09/594,083, 11 pgs.
`
`IPR2017-01039
`Unified EX1006 Page 2
`
`

`

`US 7,539,656 B2
`Page 3
`
`“Supplemental Notice of Allowability”, Mailed feb. 26, 2007 for US.
`Appl. No. 10/610,994, 20 pgs.
`“WO 2000077690 Search Report”, PCT Search Report of Interna
`tional Application No. PCT/U S00/ 16444.
`Downey, S., “Using virtual reality to construct knowledge”, Frontiers
`in Education Conference (1), (1998), 392.
`Eppler, M. J ., “Making Knowledge visible through intranet knowl
`edge maps: concepts, elements, cases Eppler”, System Sciences; Pro
`ceedings of the 34th Annual Hawaii International Conference,
`(2001),1-10.
`Kuo, R., et al., “Dif?culty 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”, 15th International Work
`shop on Database and Expert Systems Applications, 2004. Proceed
`ings., (2004) , 449-453.
`
`Pelc, K. 1., “Knowledge system of engineering and technology man
`agement”, Technology Management; the New International Lan
`guage, (1991), 550-553.
`Rouse, W. B., et al., “Knowledge maps for knowledge mining: applic
`tion to R&D/technology management”, IEEE 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”,
`32ndAnnual Frontiers in Education, 2002. FIE 2002., (2002), T2F
`7-T2F-10.
`Silva, P. C., “Fuzzy congitive maps over possible 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
`
`IPR2017-01039
`Unified EX1006 Page 3
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 1 6f 19
`
`US 7,539,656 B2
`
`GATEWAY
`
`IPR2017-01039
`Unified EX1006 Page 4
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 2 6f 19
`
`US 7,539,656 B2
`
`2, K
`
`101
`
`CPU
`
`5
`
`H102
`
`MEMORY
`132
`P’
`BROWSER
`PROGRAM
`
`150
`”
`OPERATING
`SYSTEM
`
`106
`
`DISPLAY
`ADAPTOR
`
`1 10
`H
`USER INTERFACE
`ADAPTOR
`
`114
`
`I/O
`ADAPTOR
`
`108
`
`DISPLAY
`
`H112
`KEYBOARD
`
`m
`2
`PO|NT|NG
`DEVICE
`
`115
`
`DISK
`STORAGE
`
`120
`r’
`COMM
`ADAPTOR
`
`34
`5
`
`_g2__
`
`FIG. 2
`
`IPR2017-01039
`Unified EX1006 Page 5
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 3 6f 19
`
`US 7,539,656 B2
`
`24\\
`
`201
`,-/
`
`CPU
`
`213’
`5
`
`H202
`
`MEMORY
`252
`H
`DIALOG
`ENGINE
`234
`”
`KNOWLEDGE
`MAP
`
`230
`H
`OPERATING
`SYSTEM
`236
`OTAEOO
`CONTROL
`INFORMATION
`
`206
`,4
`DISPLAY
`ADAPTOR
`
`210
`”
`USER INTERFACE
`ADAPTOR
`
`2T 4
`'1
`l/O
`ADAPTOR
`
`208
`,J
`
`DISPLAY
`
`H212
`KEYBOARD
`
`2H
`H
`POINTINC
`DEVICE
`
`215
`H
`DISK
`STORAGE
`
`220
`r]
`COMM
`ADAPTOR
`
`322
`
`FIG. 3
`
`IPR2017-01039
`Unified EX1006 Page 6
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 4 6f 19
`
`US 7,539,656 B2
`
`IPR2017-01039
`Unified EX1006 Page 7
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 5 of 19
`
`US 7,539,656 B2
`
`(2OP"IPMYSUI
`
`dwq'jousbnw
`
`G‘Old
`
`“ODIIIG“A2Y<JOU}ND>
`payobysaau;<bio/>Syi<bso>au}‘gg6lul<d>
`
`
`40}Buryoo;‘<uossad/>udWyjny}j;09G<WwosJad>
`
`
`<ayopuonouidxa/>6§6/1¢/Z1<a}Opuolouidxa>
`
`
`<wJa}/>sabsoysAiduiwjasd<wWsa}>ay]<q>
`
`
`<ayopuooas/>68///9<2}0PUd!}Da419>
`
`
`<JOUIND\>ZYNM
`
`‘Bunsodasawoouulsatyojnba!
`
`
`
`Gv'0:pno.4
`
`C60‘PNYXO]
`
`G9°Q:uoISDAZxD]
`
`
`SOVLAWONOXVL
`
`VIVO-VLIW
`
`INIVYLSININGY
`
`Papnjou!
`
`<d>
`
`
`
`INJINODCayYVA
`
`SAN]
`
`
`
`INJLNODWNIDIYO
`
`IPR2017-01039
`Unified EX1006 Page 8
`
`IPR2017-01039
`Unified EX1006 Page 8
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 6 6f 19
`
`US 7,539,656 B2
`
`
`
`
`
`mz?momm mEzEm 02200185305 mo.‘ mmiozox?
`
`
`
`
`
`0% é l- E5 02%
`
`IPR2017-01039
`Unified EX1006 Page 9
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 7 6f 19
`
`US 7,539,656 B2
`
`V
`
`/ “a,
`
`
`
`“at 6 A/ ,6,
`
`
`
`P ////%,,,I
`
`IPR2017-01039
`Unified EX1006 Page 10
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 8 6f 19
`
`US 7,539,656 B2
`
`a‘eM/Aw M / N I ,
`
`> 6 7/,
`6 a 0
`,/ A7
`/ 1
`
`O 2 8
`
`FIG.
`
`IPR2017-01039
`Unified EX1006 Page 11
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 9 6f 19
`
`US 7,539,656 B2
`
`UNDER-IF-TAGGED (
`
`)
`
`)
`
`y @
`
`/ /¢lo
`
`e
`
`//////0 w/
`
`//, 9
`
`FIG. 9
`
`//a9
`my
`
`IPR2017-01039
`Unified EX1006 Page 12
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 10 6f 19
`
`US 7,539,656 B2
`
`1010
`
`1030
`
`10540
`creoteGool
`
`@@ node=breokf0st;
`@ ;
`
`SCRAMBLED
`
`@ POACHED
`
`BREAKFAST
`
`PANCAKES
`
`1020
`
`CE}
`@@
`
`FIG. 10
`
`BENEDICT
`
`WITH SYRUP
`
`SYRUP
`
`IPR2017-01039
`Unified EX1006 Page 13
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 11 0f 19
`
`US 7,539,656 B2
`
`QUESTIONS GENERATED
`DURING DIALOG AND USER
`ANSWERS (SELECTIONS)
`ITERATION N
`
`SCRAMBLED
`
`WHICH OF THE FOLLOWING
`WOULD YOU LIKE TO GET?
`
`POACHED
`
`BENEDICT
`
`EGGS
`
`PANCAKES
`
`ITERATION N+I
`
`SCRAMBLED
`
`HOW WOULD YOU LIKE
`YOUR EGGS PREPARED?
`
`POACHED
`
`BENEDICT
`
`SCRAMBLED
`
`POACHED
`
`BENEDICT
`
`ITERATION N+2
`
`SCRAMBLED
`
`POACHED
`
`BENEDICT
`
`: @ i“
`I @ m
`@ m
`
`DIALOG STATE
`
`PANCAKES
`
`O
`
`PANCAK ES
`
`BREAKFAST
`
`PANCAK ES
`
`FIG.
`
`11
`
`IPR2017-01039
`Unified EX1006 Page 14
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 12 0f 19
`
`US 7,539,656 B2
`
`DIALOG STATE
`
`-__.___________
`
`QUESTIONS GENERATED
`DURING DIALOG AND USER
`ANSWERS (SELECTIONS)
`ITERATION N
`ARE YOU ON ANY DIET?
`7
`
`.T m WHICH OF THE FOLLOWING
`
`wouu) YOU LIKE TO GET?
`
`BREAKFAST
`
`VEGETARIAN
`
`I
`
`DIET
`
`I
`
`ITERATION N+I
`
`if (breakfast, confirmed)
`
`creoIeGool
`
`node=poncokes;
`
`WITH SYRUP
`
`WITHOUT
`SYRUP
`
`HOW WOULD YOU
`LIKE YOUR PANCAKES?
`
`WITH SYRUP
`
`WITHOUT SYRUP
`
`ITERATION N+2
`
`BREAKFAST
`
`PANCAKES
`
`FIG.
`
`12 I.
`
`WITH SYRUP
`
`WITHOUT
`SYRUP
`
`IPR2017-01039
`Unified EX1006 Page 15
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 13 6f 19
`
`US 7,539,656 B2
`
`Follow-up Questions
`
`' 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. 13
`
`IPR2017-01039
`Unified EX1006 Page 16
`
`

`

`U.S. Patent
`
`May26, 2009
`
`Sheet 14 of 19
`
`US 7,539,656 B2
`
`OOLT
`
`
`
`enboTetqeATIOe7SqUI
`
`
`
`“SoTWOUOXe}oy}HuoweesooyduedJesnsy]
`
`vlSls
`
`O9LTIjf/jOcLI
`OLLI
`
`OSLI
`
`
`
`INAWSANIS35YYSLSN1D
`
`OrllI
`
`
`
`LNSWSNIZ3YAYANO
`
`khAott
`
`NOILOA1SSAWONOXVL
`
`OcLI
`
`
`
`NOWOSTASYALSNT19
`
`IPR2017-01039
`Unified EX1006 Page 17
`
`IPR2017-01039
`Unified EX1006 Page 17
`
`
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 15 6f 19
`
`US 7,539,656 B2
`
`TQ — Text Question
`
`WHAT KIND OF BREAKFAST FOOD WOULD YOU LIKE T0 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
`
`DQs — Document Driven Question
`
`THE FOLLOWING DISHES ARE LEFT IN THE KITCHEN.
`PLEASE CHOOSE THE ONE(S) YOU WOULD LIKE TO GET:
`@/ Scrambled eggs
`I] Poached eggs
`I] 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?
`
`' SHORTCUT OUT OF DIALOG
`' A GUESS ABOUT LIKELY USER INTENTIONS
`
`- FREQUENTLY ASKED
`
`- IMPORTANT
`
`FIG. 17
`
`IPR2017-01039
`Unified EX1006 Page 18
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 16 6f 19
`
`US 7,539,656 B2
`
`(
`
`START
`
`)
`
`v
`USER POSES QUESTION
`T0 DIALOC ENGINE
`
`1810
`,1
`
`V
`DIALOG ENGINE
`CREATES INITIAL GOALS
`
`1820
`,,
`
`H1830
`v
`DIALOC ENGINE POSES
`FOLLOW-0N QUESTION TO USER
`
`V
`
`1840
`
`DIALOG ENGINE RESOLVES GOALS
`
`RETURN RANKED
`DOCUMENTS TO USER
`
`(
`
`END
`
`)
`
`FIG. 18
`
`IPR2017-01039
`Unified EX1006 Page 19
`
`

`

`US. Patent
`
`May 26, 2009
`
`Sheet 17 6f 19
`
`US 7,539,656 B2
`
`Example: Dialog Walkthrough
`
`HOSTESS: "YES?"
`
`USER: "TWO FOR LUNCH"
`
`WAITER: "WOULD LIKE ANY DRINKS TODAY?"
`
`IINO”
`
`"00 YOU HAVE ANY DIETARY CONSTRAINTS?"
`
`"YES, I AM ON HIGH-PROTEIN DIET"
`
`"WOULD YOU LIKE BREAKFAST OR LUNCH FOOD?"
`
`FIG. 19
`
`IPR2017-01039
`Unified EX1006 Page 20
`
`

`

`U.S. Patent
`
`May 26, 2009
`
`Sheet 18 of 19
`
`US 7,539,656 B2
`
`Restaurant Taxonomies
`
` DRINK
`
`PREFERENCE
`
`
`(una)
`BREAKFAST
`
`
`
`HARD
`0
`LIQUOR
`NONSKS Ce) Can) Ca
`a CED DD
`
`2010
`
`POACHED
`
`FIG. 20
`
`IPR2017-01039
`Unified EX1006 Page 21
`
`IPR2017-01039
`Unified EX1006 Page 21
`
`

`

`U.S. Patent
`
`May 26, 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
`
`IPR2017-01039
`Unified EX1006 Page 22
`
`IPR2017-01039
`Unified EX1006 Page 22
`
`

`

`US 7,539,656 B2
`
`1
`SYSTEM AND METHOD FOR PROVIDING AN
`INTELLIGENT MULTI-STEP DIALOG WITH
`A USER
`
`RELATED APPLICATIONS
`
`This application claimspriority to the following applica-
`tions:
`
`U.S. Provisional application No. 60/187,472, entitled
`“System and Methodfor 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:
`
`USS. patent application Ser. No. 09/594,083, entitled “Sys-
`tem and Method for Implementing a Knowledge Manage-
`ment System.”
`
`FIELD OF THE INVENTION
`
`This invention relates to systems and methodsforretriev-
`ing information and, more particularly, to systems and meth-
`ods for providing a multi-step conversation-like interaction
`between a person and a computeror otherdevice to 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 mayrelate 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
`mayhaveexisted in the enterprise at one time, but is no longer
`there. The challenge is 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 navigateto the infor-
`mation they need, or they provide simple “lookup”facilities
`for finding documentsor products, such as database searches
`or full-text searches for keywords appearing in documents or
`in product descriptions. These types of approachesare typi-
`cally nottailored 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” structures or expert-system rule sets that define the
`problems and their
`resolutions
`in great detail. These
`approachesare often brittle andit 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 notreliably and con-
`sistently return the desired information. This is at least partly
`dueto thefact that language is not only inherently ambiguous,
`but also becauseit is susceptible to expressing a single con-
`cept any number of ways using numerous and unrelated
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`words and/or phrases. By simply searching for specific key
`words, prior art search engines fail to identify other alterna-
`tives that mayalso be helpful.
`Consequently, there is a strong need in the art for an
`improved methodand apparatusfor retrieving relevant infor-
`mation from large knowledge bases. There is also a need for
`providing this capability to relatively unsophisticated users.
`
`SUMMARY OF THE INVENTION
`
`The present invention satisfies the above-described need
`by providing a system and methodforefficiently retrieving
`information from a large knowledge base. Morespecifically,
`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 invention to engage customers
`in a rich, personalized dialog.
`The present invention supports a model of interaction
`between a machine and a humanbeingthat 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 ofthe description—whichthe user may not
`know atthe beginningofthe interaction, or may not know are
`important—asking only questions that are relevant to the
`problem description stated so far, given the system’s know]-
`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 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 software. In operation, users start a
`dialog by directing 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 to a knowledge map, using
`dialog control 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 customerservice 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-recognition system.
`Additional features and advantagesofthe invention will be
`set forth in the description which followsand,in part, will be
`apparent from the description, or may be learned by practice
`of the invention. The objectives and other advantages of the
`invention will be realized and attained by the methods, sys-
`
`IPR2017-01039
`Unified EX1006 Page 23
`
`IPR2017-01039
`Unified EX1006 Page 23
`
`

`

`US 7,539,656 B2
`
`3
`tems, and apparatus particularly pointed out in the written
`description and claimshereof, as well as the appended draw-
`ings.
`It is to be understood that both the foregoing general
`description and the following detailed description are exem-
`plary and explanatory and are intended to provide further
`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 principlesof the
`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 of a dialog engine
`server of FIG. 1;
`FIG. 4 is drawing illustrating the relationship between
`knowledge containers, taxonomies and taxonomy tags in
`accordance with an embodimentof 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 drawingillustrating basic constraints in accor-
`dance with an embodimentof the present invention;
`FIG. 8 is a drawing illustrating negated constraints in
`accordance with an embodimentof the present invention;
`FIG.9 is a drawing illustrating conditional constraints in
`accordance with an embodimentof the present invention;
`FIG. 10 is a drawing illustrating triggers in accordance
`with an embodimentof the present invention;
`FIG. 11 is a drawingillustrating the goalresolution process
`in accordance with an embodimentofthe present invention;
`FIG. 12 is a drawing illustrating 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 embodimentofthe
`present invention;
`FIG. 14 showsa 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 embodimentof the present invention;
`FIG. 16 is a chart illustrating a documentdriven question in
`accordance with an embodimentof 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-
`step interactive dialog system in a mannerconsistent with the
`present invention; and
`FIGS. 19-21 are drawingsillustrating 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 wayofillustration a
`specific embodimentin which the invention maybepracticed.
`This embodimentis described in sufficient detail to enable
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`those skilled in the art to practice the invention andit is to be
`understood that other embodiments maybe 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 (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 purposeofa 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
`telephoneor 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
`machinein the form of a meta-data representationrelat-
`ing to a knowledge map (knowledgesession); and
`d.) Deliver the knowledge session to other applications via
`API, XMLor 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 commonlyassigned, 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 knowledge session is a representation of a user’s situa-
`tion or scenario in the context of a knowledge map. A know!]-
`edge session includestext elicited from the user and a collec-
`tion of tags (as described in application Ser. No. 09/594,083)
`that each represent a link to a concept node within the know]-
`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 interface to inference
`engines, the ability to constructinteractions, and the ability to
`send sessions to other software.
`
`The dialog engine of the present invention is defined by:
`1.) 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 enginerefines 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.
`
`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
`USS. patent application Ser. No. 09/594,083, entitled “System
`and Method for Implementing a Knowledge Management
`
`IPR2017-01039
`Unified EX1006 Page 24
`
`IPR2017-01039
`Unified EX1006 Page 24
`
`

`

`US 7,539,656 B2
`
`5
`System,” which has previously been incorporated by refer-
`ence) of a natural language text (“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 made in respect to the commonground(see defi-
`nitions) (commongroundcontext);
`The choices/actions made by the user during the dialog
`(such as selecting a document) (interaction context).
`
`User Entry:
`The dialog engine canutilize th