Method and apparatus using discriminative training in natural language call routing and document retrieval

• US 6,925,432 B2
• Filed: 12/26/2000
• Issued: 08/02/2005
• Est. Priority Date: 10/11/2000
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Kuo, Hong-Kwang Jeff, Lee, Chin-Hui
• Primary Examiner(s): Ometz, David L.
• Assistant Examiner(s): Opsasnick, Michael N.
• Application Number:
  US09/748,433
• Publication Number:
  US 20020116174A1
• Time in Patent Office: 1,680 Days
• Field of Search: 704/5, 704/9, 704/240
• US Class Current: 704/5
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 18/21 Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 15/183 using context dependencies, e.g. language models

Abstract

A method and apparatus for performing discriminative training of, for example, call routing training data (or, alternatively, other classification training data) which improves the subsequent classification of a user'"'"'s natural language based requests. An initial scoring matrix is generated based on the training data and then the scoring matrix is adjusted so as to improve the discrimination between competing classes (e.g., destinations). In accordance with one illustrative embodiment of the present invention a Generalized Probabilistic Descent (GPD) algorithm may be advantageously employed to provide the improved discrimination. More specifically, the present invention provides a method and apparatus comprising steps or means for generating an initial scoring matrix comprising a numerical value for each of a set of n classes in association with each of a set of m features, the initial scoring matrix based on a set of training data and, for each element of said set of training data, based on a subset of said features which are comprised in the natural language text of said element of said set of training data and on one of said classes which has been identified therefor; and based on the initial scoring matrix and the set of training data, generating a discriminatively trained scoring matrix for use by said classification system by adjusting one or more of said numerical values such that a greater degree of discrimination exists between competing ones of said classes when said classification requests are performed, thereby resulting in a reduced classification error rate.

Claims

1. A method of training a scoring matrix for use by a classification system, the classification system for use in performing classification requests based on natural language text and with use of said scoring matrix which has been based on a set of training data comprising natural language text, the method comprising the steps of:

generating an initial scoring matrix comprising a numerical value for each of a set of n classes in association with each of a set of m features, the initial scoring matrix based on said set of training data and, for each element of said set of training data, based on a subset of said features which are comprised in said natural language text of said element of said set of training data and on one of said classes which has been identified therefor; and

based on the initial scoring matrix and said set of training data, generating a discriminatively trained scoring matrix for use by said classification system by adjusting one or more of said numerical values such that a greater degree of discrimination exists between competing ones of said classes when said classification requests are performed, thereby resulting in a reduced classification error rate,

wherein said step of adjusting said numerical values is performed with use of a Generalized Probabilistic Descent algorithm and

wherein said step of adjusting said numerical values comprises, for each element of said set of training data, modifying values associated with the identified class and values associated with one or more of the other classes such that a score obtained for said element of said set of training data based on said modified values associated with the identified class is improved relative to one or more scores obtained for said element of said set of training data based on said modified values associated with said one or more other classes.

2. The method of claim 1 wherein said values are modified based on the following equation of the form:

$r_{\mathrm{vw}}<br><br>\left(t+1\right)=\{\begin{array}{cc}<br><br>r_{\mathrm{vw}}<br><br>\left(t\right)+{\mathrm{\varepsilon <br><br>}}_i<br><br>\frac{\partial <br><br>l_k}{\partial <br><br>d_k}<br><br>x_w& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>v=k\\ <br><br>r_{\mathrm{vw}}<br><br>\left(t\right)-\frac{{\mathrm{\varepsilon <br><br>}}_i<br><br>\frac{\partial <br><br>l_k}{\partial <br><br>d_k}<br><br>x_w<br><br>G_k<br><br>\left({\stackrel{\to <br><br>}{x}}_i,R\right)<br><br>{\left({\stackrel{\to <br><br>}{r}}_v·<br><br>{\stackrel{\to <br><br>}{x}}_i\right)}^{\mathrm{\eta <br><br>}-1}}{\underset{j\ne <br><br>k}{\sum <br><br>}<br><br>{\left({\stackrel{\to <br><br>}{r}}_j·<br><br>{\stackrel{\to <br><br>}{x}}_i\right)}^{\mathrm{\eta <br><br>}}}& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>v\ne <br><br>k.\end{array}$

3. The method of claim 1 wherein said classification requests comprise call routing requests, wherein said classes comprise call routing destinations, and wherein said set of training data comprises call routing requests together with associated identified call routing destinations therefor.

4. The method of claim 1 wherein said classification requests comprise document retrieval requests, wherein said classes comprise documents, and wherein said set of training data comprises document retrieval requests together with associated identified documents therefor.

5. The method of claim 1 wherein said natural language text upon which said classification requests are based and said natural language text comprised in said set of training data is processed without the use of stop word filtering.

6. The method of claim 1 wherein said step of adjusting said numerical values comprises iteratively adjusting said numerical values until a stopping criterion is met.

7. The method of claim 6 wherein said stopping criterion comprises an empirical loss threshold.

8. The method of claim 6 wherein said stopping criterion comprises a classification error rate threshold.

9. A method of performing classification requests based on natural language text and with use of a discriminatively trained scoring matrix which has been trained based on a set of training data comprising natural language text, the scoring matrix having been discriminatively trained by a method comprising the steps of:

generating an initial scoring matrix comprising a numerical value for each of a set of n classes in association with each of a set m features, the initial scoring matrix based on said set of training data and, for each element of said set of training data, based on a subset of said features which are comprised in said natural language text of said element of said set of training data and on one of said classes which has been identified therefor; and

based on the initial scoring matrix and said set of training data, generating said discriminatively trained scoring matrix by adjusting one or more of said numerical values such that a greater degree of discrimination exists between competing ones of said classes when said classification requests are performed, thereby resulting in a reduced classification error rate,

wherein said step of adjusting said numerical values is performed with use of a Generalized Probabilistic Descent algorithm and

wherein said step of adjusting said numerical values comprises, for each element of said set of training data, modifying values associated with the identified class and values associated with one or more of the other classes such that a score obtained for said element of said set of training data based on said modified values associated with the identified class is improved relative to one or more scores obtained for said element of said set of training data based on said modified values associated with said one or more other classes.

10. The method of claim 9 wherein said values are modified based on the following equation of the form:

$r_{\mathrm{vw}}<br><br>\left(t+1\right)=\{\begin{array}{cc}<br><br>r_{\mathrm{vw}}<br><br>\left(t\right)+{\mathrm{\varepsilon <br><br>}}_i<br><br>\frac{\partial <br><br>l_k}{\partial <br><br>d_k}<br><br>x_w& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>v=k\\ <br><br>r_{\mathrm{vw}}<br><br>\left(t\right)-\frac{{\mathrm{\varepsilon <br><br>}}_i<br><br>\frac{\partial <br><br>l_k}{\partial <br><br>d_k}<br><br>x_w<br><br>G_k<br><br>\left({\stackrel{\to <br><br>}{x}}_i,R\right)<br><br>{\left({\stackrel{\to <br><br>}{r}}_v·<br><br>{\stackrel{\to <br><br>}{x}}_i\right)}^{\mathrm{\eta <br><br>}-1}}{\underset{j\ne <br><br>k}{\sum <br><br>}<br><br>{\left({\stackrel{\to <br><br>}{r}}_j·<br><br>{\stackrel{\to <br><br>}{x}}_i\right)}^{\mathrm{\eta <br><br>}}}& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>v\ne <br><br>k.\end{array}$

11. The method of claim 9 wherein said classification requests comprise call routing requests, wherein said classes comprise call routing destinations, and wherein said set of training data comprises call routing requests together with associated identified call routing destinations therefor.

12. The method of claim 9 wherein said classification requests comprise document retrieval requests, wherein said classes comprise documents, and wherein said set of training data comprises document retrieval requests together with associated identified documents therefor.

13. The method of claim 9 wherein said natural language text upon which said classification requests are based and said natural language text comprised in said set of training data is processed without the use of stop word filtering.

14. The method of claim 9 wherein said step of adjusting said numerical values comprises iteratively adjusting said numerical values until a stopping criterion is met.

15. The method of claim 14 wherein said stopping criterion comprises an empirical loss threshold.

16. The method of claim 14 wherein said stopping criterion comprises a classification error rate threshold.

17. An apparatus for training a scoring matrix for use by a classification system, the classification system for use in performing classification requests based on natural language text and with use of said scoring matrix which has been based on a set of training data comprising natural language text, the apparatus comprising:

means for generating an initial scoring matrix comprising a numerical value for each of a set of n classes in association with each of a set of m features, the initial scoring matrix based on said set of training data and, for each element of said set of training data, based on a subset of said features which are comprised in said natural language text of said element of said set of training data and on one of said classes which has been identified therefor; and

based on the initial scoring matrix and said set of training data, means for generating a discriminatively trained scoring matrix for use by said classification system by adjusting one or more of said numerical values such that a greater degree of discrimination exists between competing ones of said classes when said classification requests are performed, thereby resulting in a reduced classification error rate,

wherein said means for adjusting said numerical values executes a Generalized Probabilistic Descent algorithm and

wherein said means for adjusting said numerical values comprises, for each element of said set of training data, means for modifying values associated with the identified class and values associated with one or more of the other classes such that a score obtained for said element of said set of training data based on said modified values associated with the identified class is improved relative to one or more scores obtained for said element of said set of training data based on said modified values associated with said one or more other classes.

18. The apparatus of claim 17 wherein said values are modified based on the following equation of the form:

$r_{\mathrm{vw}}<br><br>\left(t+1\right)=\{\begin{array}{cc}<br><br>r_{\mathrm{vw}}<br><br>\left(t\right)+{\mathrm{\varepsilon <br><br>}}_i<br><br>\frac{\partial <br><br>l_k}{\partial <br><br>d_k}<br><br>x_w& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>v=k\\ <br><br>r_{\mathrm{vw}}<br><br>\left(t\right)-\frac{{\mathrm{\varepsilon <br><br>}}_i<br><br>\frac{\partial <br><br>l_k}{\partial <br><br>d_k}<br><br>x_w<br><br>G_k<br><br>\left({\stackrel{\to <br><br>}{x}}_i,R\right)<br><br>{\left({\stackrel{\to <br><br>}{r}}_v·<br><br>{\stackrel{\to <br><br>}{x}}_i\right)}^{\mathrm{\eta <br><br>}-1}}{{\sum <br><br>}_{j\ne <br><br>k}<br><br>{\left({\stackrel{\to <br><br>}{r}}_j·<br><br>{\stackrel{\to <br><br>}{x}}_i\right)}^{\mathrm{\eta <br><br>}}}& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>v\ne <br><br>k.\end{array}$

19. The apparatus of claim 17 wherein said classification requests comprise call routing requests, wherein said classes comprise call routing destinations, and wherein said set of training data comprises call routing requests together with associated identified call routing destinations therefor.

20. The apparatus of claim 17 wherein said classification requests comprise document retrieval requests, wherein said classes comprise documents, and wherein said set of training data comprises document retrieval requests together with associated identified documents therefor.

21. The apparatus of claim 17 wherein said natural language text upon which said classification requests are based and said natural language text comprised in said set of training data is processed without the use of stop word filtering.

22. The apparatus of claim 17 wherein said means for adjusting said numerical values comprises means for iteratively adjusting said numerical values until a stopping criterion is met.

23. The apparatus of claim 22 wherein said stopping criterion comprises an empirical loss threshold.

24. The apparatus of claim 22 wherein said stopping criterion comprises a classification error rate threshold.

25. An apparatus for performing classification requests based on natural language text and with use of a discriminatively trained scoring matrix which has been trained based on a set of training data comprising natural language text, the scoring matrix having been discriminatively trained by an apparatus comprising:

means for generating an initial scoring matrix comprising a numerical value for each of a set of n classes in association with each of a set of m features, the initial scoring matrix based on said set of training data and, for each element of said set of training data, based on a subset of said features which are comprised in said natural language text of said element of said set of training data and on one of said classes which has been identified therefor; and

based on the initial scoring matrix and said set of training data, means for generating said discriminatively trained scoring matrix by adjusting one or more of said numerical values such that a greater degree of discrimination exists between competing ones of said classes when said classification requests are performed, thereby resulting in a reduced classification error rate,

wherein said means for adjusting said numerical values executes a Generalized Probabilistic Descent algorithm and

wherein said means for adjusting said numerical values comprises, for each element of said set of training data, means for modifying values associated with the identified class and values associated with one or more of the other classes such that a score obtained for said element of said set of training data based on said modified values associated with the identified class is improved relative to one or more scores obtained for said element of said set of training data based on said modified values associated with said one or more other classes.

26. The apparatus of claim 25 wherein said values are modified based on the following equation of the form:

$r_{\mathrm{vw}}<br><br>\left(t+1\right)=\{\begin{array}{cc}<br><br>r_{\mathrm{vw}}<br><br>\left(t\right)+{\mathrm{\varepsilon <br><br>}}_i<br><br>\frac{\partial <br><br>l_k}{\partial <br><br>d_k}<br><br>x_w& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>v=k\\ <br><br>r_{\mathrm{vw}}<br><br>\left(t\right)-\frac{{\mathrm{\varepsilon <br><br>}}_i<br><br>\frac{\partial <br><br>l_k}{\partial <br><br>d_k}<br><br>x_w<br><br>G_k<br><br>\left({\stackrel{\to <br><br>}{x}}_i,R\right)<br><br>{\left({\stackrel{\to <br><br>}{r}}_v·<br><br>{\stackrel{\to <br><br>}{x}}_i\right)}^{\mathrm{\eta <br><br>}-1}}{{\sum <br><br>}_{j\ne <br><br>k}<br><br>{\left({\stackrel{\to <br><br>}{r}}_j·<br><br>{\stackrel{\to <br><br>}{x}}_i\right)}^{\mathrm{\eta <br><br>}}}& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>v\ne <br><br>k.\end{array}$

27. The apparatus of claim 25 wherein said classification requests comprise call routing requests, wherein said classes comprise call routing destinations, and wherein said set of training data comprises call routing requests together with associated identified call routing destinations therefor.

28. The apparatus of claim 25 wherein said classification requests comprise document retrieval requests, wherein said classes comprise documents, and wherein said set of training data comprises document retrieval requests together with associated identified documents therefor.

29. The apparatus of claim 25 wherein said natural language text upon which said classification requests are based and said natural language text comprised in said set of training data is processed without the use of stop word filtering.

30. The apparatus of claim 25 wherein said means for adjusting said numerical values comprises means for iteratively adjusting said numerical values until a stopping criterion is met.

31. The apparatus of claim 30 wherein said stopping criterion comprises an empirical loss threshold.

32. The apparatus of claim 30 wherein said stopping criterion comprises a classification error rate threshold.