Keywords
|
| Spoken dialogue system , Speech recognition system . Machine Learning, Expectation Maximization , classification . weighted minimum edit distance |
INTRODUCTION
|
| Spoken Language Understand has been a challenge in the design of the spoken dialogue system where the intention of the speaker has to be identified from the words used in his utterances. Typically a spoken dialogue system comprises a four main components an automatic speech recognition system (ASR) , Spoken language understanding component (SLU) , Dialogue manager (DM) and an Speech synthesis system which converts the text to speech (TTS). Spoken Language understanding deals with understanding the intent from the words of the speakers utterances. The accuracy of the speech recognition system is questionable and researchers have provided various solutions to the problem and classifying the information may actually guide the dialogue manager in framing a response. |
| Many models both statistical as well as empirical methods have been suggested for extracting information from text by automatically generating a language model after training from the annotated corpus.[1] When Statistical classifiers are used for classification they have to be trained using a large amount of task data which is usually transcribed and then assigned one or more predefined type to each utterance by humans , a very expensive and laborious process[2]. But they do not perform well due to the lack of large scale richly annotated corpora. Seymore et al [3] extracted the important information from the headers of computer science research papers by making use of Hidden Markov models. A statistical method based on HVS has been proposed to automatically extract information related to protein – protein interactions from biomedical literature [2]. |
| Semi-supervised learning uses both supervised and unsupervised learning to learn from both annotated and unannotated sentences for classifications , clustering and so on. Nigam et al [4] used Expectation-Maximization algorithm with a naïve Bayes classifier on multiple mixture components for text classification. Small amount of labeled data is used to first build a model which is then used to annotate the instances of the unlabeled instances. The instance along with identified label which posses the more confidence measure are then added to the training set and participate in retraining of the model for the left out instances. The process is continued for the training of the remaining of the un-annotated sentences. |
THE HIDDEN VECTOR STATE MODEL
|
| The basic hidden vector state model is a discrete Hidden Markov Model in which each HMM state represents the state of a push down automaton which encodes history in a fixed dimension stack . Each state consists of a stack where each element of the stack is a label chosen from a finite set of cardinality . A HVS model state of depth D can be characterized by a vector of dimension D with most recently pushed element at index 1 and the oldest at index D. Each vector state is like a snapshot of the stack in the push-down automaton and transitions between states can be factored into a stack shift by âÃâ¬Ãân‘ positions followed by a push of one or more new pre-terminal semantic concepts. The number of new concepts to be pushed is limited to one. The joint probability of a sequence of stack pop operations , word sequence and concept vector sequence is approximated as |
 |
 |
| The key feature of the HVS model is its ability for representing hierarchical information in a constrained way which can be trained from only lightly annotated data. The generative process associated with HVS model consists of three steps for each position t : |
 |
| A set of domain specific lexical classes and abstract semantic annotations which limit the forward and backward search to include only those states which are consistent with these constraints for the model training must be provided for each sentence. |
SEMI-SUPERVISED LEARNING
|
| The main aim of the semi-supervised learning is to utilize the labeled utterances for annotating the unlabelled utterances in order to improve the performance of a classifier and reducing the human labeling effort. The semi-supervised learning technique used is as follows , Initially the human labeled task data is used to train the initial model which is used then to classify the unlabelled utterances. The machine labeled utterances whose confidence score value is above a threshold so that the noise due to classifier errors is reduced are added to the training data .If the input space is |
 |
RELATED WORK
|
| In Language Processesing framework there are two approaches viz certainty based approaches and committee based approaches of having control over the type of inputs on which it trains [6] .In certainty based approaches , a small set of annotated examples is used to train the system, the system then labels the unannotated sentences and then determines the confidence for each of its prediction. The sentences with lower confidence are then presented to the labelers for annotation. In Committee based methods , a small set of annotated sentences are used to create a disjoint set of classifiers, which are then used to classify the unannotated sentences. The sentences where the classification differ much are manually annotated . Nigam et al (2000) learned from both labeled and unlabelled data based on combination of Expectation Maximization and a Naïve Bayes classifier on multiple mixture components per class for task of text classification. Yarosky [6] used self training for word sense disambiguation. Rosenberg et al [7] applied self training to object detection from images. Self training builds a model based on the small amount of labeled data and then uses the model to label instances in the unlabeled data . The most confident instances together with their labels participate in the training set to retrain the model. |
| Ghani(2002) proposed an algorithm for exploiting the labeled as well as un- labeled data using the co training with Expectation Maximization(CO-EM)[8]. Riccardi and Hakkani –Tur(2003) used semi-supervised learning for automation speech recognition and have shown improvements for statistical language modeling where they exploited confidence scores for words and utterances computed from ASR word lattices[9]. |
FRAMEWORK
|
| A probabilistic framework is used to describe the nature of sentences and their annotations where semantic annotations are considered as the class label for each sentence with the following two assumptions a) If is the number of distinct annotations in the labeled set where = { ( then the data are produced by probability models. b) there is a one to one correspondence between probability components and classes. Considering the each individual annotation as a class , the likelihood of a sentence is given by |
 |
| Where is the annotation of the sentence and represents the complete set of HVS model parameters. Since the domain of possible training examples is and the binary indicators are known for the sentences in and unknown for the sentences in . The class labels of the sentences are represented as the matrix of binary indicators Z where |
 |
| Calculating the maximum likelihood estimate of the parameters i.e. for learning the HVS model . The annotation for the word sequence can be determined by } i.e the concept vector sequence and the series of stack shift operations and } can be inferred from . Thus can be rewritten as which can further be rewritten as which is the product over all the sentences assuming each sentence is independent of each other . The probability of the data is given by |
 |
METHODOLOGY
|
| To improve the performance of classifier, the methods used are based on classification and Expectation Maximization. Both the methods assume that there is some training data available for the initial classifier. The main aim is to use this classifier to label the unlabelled data automatically and to then improve the classifier performance using machine labeled utterances. Semi-supervised learning based on classification measures the edit distance between the POS tag sequences of the sentences in and POS tag sequences of sentences in to automatically generate the annotation for the unlabelled sentences. The edit distance or Levenshtein distance of two strings, s1 and s2, is defined as the minimum number of point mutations required to change s1 into s2, where a point mutation can be either changing a letter or inserting a letter or deleting a letter .If X and Y are two pos tag sequences of length n and m respectively , a tabular computation D(i , j) which contains the score of the optimal alignment between the initial segment from X and the initial segment from Y is calculated using the following algorithm |
 |
| Dynamic programming which solves problems by combining solutions to sub problems is used comprising of edit distance matrix . By this technique we first calculate for smaller i , j and compute larger D(i , j) based on the previous computed smaller values i.e compute for all 0 < i < n and 0 < j < m. Given two sentences Si , Sj and their corresponding POS tag sequences Ti = a1a2 .. ani and Tj = b1b2..bnj , the distance between the two sentences is defined as Dist(Si , Sj ) = - D(ni , nj) where D(ni , nj) is the distance measure of optimal alignment between two POS tag sequences Ti and Tj . |
DISTANCE-WEIGHTED NEAREST NEIGHBOR ALGORITHM
|
| Classification a spoken dialogue learning uses a finite number of labeled examples and selects a hypothesis is expected to generate few errors on the future examples. In case of spoken dialogue systems human labeling of the the spoken utterances has a wide impact on the quality of the machine labeling of the unlabeled sentences . The basic elements to handle by classification algorithm are word lattices which may contain a single word or a collection of words with some weight or probability [10]. The technique which we have used for classification is Distance-Weighted Nearest Neighbor Algorithm. Since the training Input variables consists of the set <X ,Y> where X contains represents the word and Y represents its semantic annotation, the algorithm find s the training points which have the closest edit distance to the queried word. It assigns weights to the neighbors based on their âÃâ¬Ãâdistance‘ from the query point, the Weight are inverse square of the distances. and then classifies according to the mean value of the âÃâ¬Ãâk‘ nearest training examples. All the training points influence a particular instance. |
| Transductive Learning based on expectation maximization |
| The EM algorithm is an efficient iterative procedure to compute the Maximum likelihood (ML) estimate in the presence of missing or hidden data. In ML estimation, we wish to estimate the model parameter(s) for which the observed data are the most likely. So we cluster the sentences in and . The original model will contain more sentences since some sentences in will have the similar semantic structure with those sentences in which have been used to train the HVS Model but adding should be based on some confidence measure so that the performance of the model is improved. To do this a parameter which represents the degree of fitness is to be used for selecting the sentences based on parsing information , structural information and complexity information [2]. These parameters of a sentence are defined as |
| Parsing information describes the information in the parsing result and is defined as |
 |
| Where N denotes the length of the sentence , denotes the jth word of the sentence and the functions is equal to 1 if is a word in the and 0 otherwise. is 1 if is 1 and the semantic tag of is not known and 0 otherwise. Structure information is a measure of similarity between the structure information of a sentence and the sentences in which is given by |
 |
 |
| The parameter is estimated from the set of training data , is the estimated value and is the observed value. First a sample corpus of words are identified from the travel domain. Then a semantic tag based on the class is attached for identifying interactions. The vertibi decoding algorithm is used to parse the sentences of the . For the sentences in selection is done based on the parameters i.e. . Thus the sentences in would be added to the set of sentences with annotation and participate in further automatically annotating sentences in . |
EXPERIMENTS
|
| To evaluate the models proposed the training data was split into two data sets corpus I comprising of 200 sentences out of which 100 sentences with manual annotation from travel domain are added to for training the HVS model and 100 sentences were added to . First clusters are created from the learned sentences based on the edit distance measure and then semi supervised learning based on expectation maximization was applied to the sentences in The corpus II comprised of the 250 sentences which incremented the 200 sentences by 50 more sentences with annotation for learning the HVS model. And then out of 100 sentences 47 sentences were semantic annotated successfully with out any human labeling by the algorithm. |
RESULTS
|
| The experimental results for the baseline HVS model trained on sentences in contained 74 classes when classification was performed . 8 Experiments were performed for subset of sentences in with the k = 1,2,3 based on Distance- Weighted Nearest Neighbor Algorithm. The overall precision was calculated by ratio of ( Number of sentences for which annotation was done correctly )/SUM (Number of sentences for which annotation was done correctly , Number of sentences for which annotation was done Incorrectly) based on classification. The overall precision in the travel domain data set was observed at 65.4% with k=3 when only sentences from were used. The HVS Model was incrementally trained with these newly added sentences from based on the sentence selection based on expectation maximization which improved the performance by 4.6% |
 |
| Table: 1 |
 |
| Figure: 1 |
CONCLUSION AND FUTURE WORK
|
| In this paper we have used two semi-supervised learning techniques which made use of both labeled and unlabeled data to improve the performance of the HVS model. The overall performance was improved by nearly 4-5% . In future we will use the learning technique like SVM or Kernels for dealing with problems where minimum labeled data is available. |
ACKNOWLEDGEMENT
|
| We thank the University of Michigan and University of Rochester for keeping the data sets online and free for academic and research usage. |
References
|
- G. Tur , Dilek Hakkani- Tur , Robert E. Schapire , ?Combining active and semi-supervised learning for spoken language understand, 175-186 Speech communications.
- Deyu Zhou , Yulan He , Chee Keong Kwoh ,? Semi Supervised Learning of Hidden Vector State model for extracting protein-protein interactions, 209-222 , Artificial intelligence in Medicine (2007) vol – 41.
- Seymore K, McCallum A, Rosenfeld R. Learning hidden Markov model structure for information extraction. In: Proceedings of the sixteenth national conference on artificial intelligence (AAAI-99)
- Zhou D, He Y, Kwoh CK. Extracting protein—protein interactionsfrom the literature using the hidden vector state model. In: Alexandrov VN, van Albada GD, Sloot PMA, Dongarra J, editors. Lecture notes in computer science, vol. 3992. 2006. p. 549—56.
- Nigam K, McCallum AK, Thrun S, Mitchell TM. Text classification from labeled and unlabeled documents using EM. Machine Learn 2000; 39(2/3):103—34.
- Yarowsky D. Unsupervised word sense disambiguation rivaling supervised methods. In Proceedings of the 33rd annual meeting of the association for computational linguistics. Morristown, NJ, USA: Association for Computational Linguistics; 1995. p. 189—96.
- Rosenberg C, Hebert M, Schneiderman H. Semi-supervised self-training of object detection models. In: Proceedings of the seventh IEEE workshop on applications of computer vision. Washington, DC, USA: IEEE Computer Society; 2005. p.29—36.
- Ghani, R., July 2002. Combining labeled and unlabeled data for multiclass text categorization. In: Proc. Internat. Conf. on Machine Learning (ICML), Sydney, Australia.
- Riccardi, G, ]Gorin, A.L Wright, J.H., 2002. Automated natural spoken dialog. IEEE Computer. Mag. 35 (4), 51–56.
- Blum A, Mitchell T. Combining labeled and unlabeled data with co-training. In Proceedings of Annual workshop on computational learning theory,
- Argamon-Engelson, S., Dagan, I., 1999. Committee-based sample selection for probabilistic classifiers. J. Artif. Intell.Res. 11, 335–360.
- Blum, A., Mitchell, T., July 1998. Combining labeled and unlabeled data with co-training. In: Proc.of the eleventh annual conference on computational learning theory. New York, NY, USA: ACM Press; 1998 . p.92—100.
- Jones R. Learning to extract entities from labeledand unlabeled text. PhD thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA, 2005.
- Blum A, Chawla S. Learning from labeled and unlabeled data using graph mincuts. In: Brodley CE, Danyluk AP, editors. Proceedings of the 18th international conference on machine learning. Morgan Kaufmann; 2001. p. 19—26.
- Zhu X. Semi-supervised learning literature survey. Technical Report 1530, Computer Sciences Department, University of Wisconsin-Madison; 2005.
- He Y, Young S. Semantic processing using the hidden vector state model. Comput Speech Lang 2005;19(1):85—106.
- Cohn, D., Atlas, L., Ladner, R., 1994. Improving generalization with active learning. Machine Learning 15, 201–221.
- Freund, Y., Seung, H.S., Shamir, E., Tishby, N., 1997. Selective sampling using the query by committee algorithm. Machine Learning 28, 133–168.
- Iyer, R., Gish, H., McCarthy, D., May 2002. Unsupervised training techniques for natural language call routing. In: Proc. Internat. Conf. on Acoustics, Speech and Signal Processing (ICASSP), Orlando, FL.
|
Menu