A survey on phrase structure learning methods for text classification
---
paper_title: Nearest Neighbor Pattern Classification

paper_content:

The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points. This rule is independent of the underlying joint distribution on the sample points and their classifications, and hence the probability of error R of such a rule must be at least as great as the Bayes probability of error R^{\ast} --the minimum probability of error over all decision rules taking underlying probability structure into account. However, in a large sample analysis, we will show in the M -category case that R^{\ast} \leq R \leq R^{\ast}(2 --MR^{\ast}/(M-1)) , where these bounds are the tightest possible, for all suitably smooth underlying distributions. Thus for any number of categories, the probability of error of the nearest neighbor rule is bounded above by twice the Bayes probability of error. In this sense, it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.
---
paper_title: Support-Vector Networks

paper_content:

The support-vector network is a new learning machine for two-group classification problems. The machine conceptually implements the following idea: input vectors are non-linearly mapped to a very high-dimension feature space. In this feature space a linear decision surface is constructed. Special properties of the decision surface ensures high generalization ability of the learning machine. The idea behind the support-vector network was previously implemented for the restricted case where the training data can be separated without errors. We here extend this result to non-separable training data. ::: ::: High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated. We also compare the performance of the support-vector network to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.
---
paper_title: Induction of decision trees

paper_content:

The technology for building knowledge-based systems by inductive inference from examples has been demonstrated successfully in several practical applications. This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail. Results from recent studies show ways in which the methodology can be modified to deal with information that is noisy and/or incomplete. A reported shortcoming of the basic algorithm is discussed and two means of overcoming it are compared. The paper concludes with illustrations of current research directions.
---
paper_title: Automated learning of decision rules for text categorization

paper_content:

We describe the results of extensive experiments using optimized rule-based induction methods on large document collections. The goal of these methods is to discover automatically classification patterns that can be used for general document categorization or personalized filtering of free text. Previous reports indicate that human-engineered rule-based systems, requiring many man-years of developmental efforts, have been successfully built to “read” documents and assign topics to them. We show that machine-generated decision rules appear comparable to human performance, while using the identical rule-based representation. In comparison with other machine-learning techniques, results on a key benchmark from the Reuters collection show a large gain in performance, from a previously reported 67% recall/precision breakeven point to 80.5%. In the context of a very high-dimensional feature space, several methodological alternatives are examined, including universal versus local dictionaries, and binary versus frequency-related features.
---
paper_title: Kazakh Noun Phrase Extraction Based on N-gram and Rules

paper_content:

The aim of the work is to extract Kazakh phrase and basic noun phrase from corpus. For the phrase extraction, N-gram model methods were used, specifically bigram and trigram methods were applied. For basic noun phrase extraction, rule-based methods were used. We started from the grammar structure of basic noun phrase structure model, established a set of rules using the part-of-speech tag and the additional component information of Kazakh basic noun phrase, and extracted the basic noun phrase by rule matching. We have realized the extraction of phrase and basic noun phrase based on corpus of 31 days’ Xinjiang Daily. Experimental results showed that the two methods are feasible, and the extraction accuracies are 50.8% and 79.1% respectively.
---
paper_title: Kazakh Noun Phrase Extraction Based on N-gram and Rules

paper_content:

The aim of the work is to extract Kazakh phrase and basic noun phrase from corpus. For the phrase extraction, N-gram model methods were used, specifically bigram and trigram methods were applied. For basic noun phrase extraction, rule-based methods were used. We started from the grammar structure of basic noun phrase structure model, established a set of rules using the part-of-speech tag and the additional component information of Kazakh basic noun phrase, and extracted the basic noun phrase by rule matching. We have realized the extraction of phrase and basic noun phrase based on corpus of 31 days’ Xinjiang Daily. Experimental results showed that the two methods are feasible, and the extraction accuracies are 50.8% and 79.1% respectively.
---
paper_title: Text Chunking Using Transformation-Based Learning

paper_content:

Transformation-based learning, a technique introduced by Eric Brill (1993b), has been shown to do part-of-speech tagging with fairly high accuracy. This same method can be applied at a higher level of textual interpretation for locating chunks in the tagged text, including non-recursive “baseNP” chunks. For this purpose, it is convenient to view chunking as a tagging problem by encoding the chunk structure in new tags attached to each word. In automatic tests using Treebank-derived data, this technique achieved recall and precision rates of roughly 93% for baseNP chunks (trained on 950K words) and 88% for somewhat more complex chunks that partition the sentence (trained on 200K words). Working in this new application and with larger template and training sets has also required some interesting adaptations to the transformation-based learning approach.
---
paper_title: Automated learning of decision rules for text categorization

paper_content:

We describe the results of extensive experiments using optimized rule-based induction methods on large document collections. The goal of these methods is to discover automatically classification patterns that can be used for general document categorization or personalized filtering of free text. Previous reports indicate that human-engineered rule-based systems, requiring many man-years of developmental efforts, have been successfully built to “read” documents and assign topics to them. We show that machine-generated decision rules appear comparable to human performance, while using the identical rule-based representation. In comparison with other machine-learning techniques, results on a key benchmark from the Reuters collection show a large gain in performance, from a previously reported 67% recall/precision breakeven point to 80.5%. In the context of a very high-dimensional feature space, several methodological alternatives are examined, including universal versus local dictionaries, and binary versus frequency-related features.
---
paper_title: Application of translation knowledge acquired by hierarchical phrase alignment for pattern-based mt

paper_content:

Hierarchical phrase alignment is a method for extracting equivalent phrases from bilingual sentences, even though they belong to different language families. The method automatically extracts transfer knowledge from about 125K English and Japanese bilingual sentences and then applies it to a pattern-based MT system. The translation quality is then evaluated. The knowledge needs to be cleaned, since the corpus contains various translations and the phrase alignment contains errors. Various cleaning methods are applied in this paper. The results indicate that when the best cleaning method is used, the knowledge acquired by hierarchical phrase alignment is comparable to manually acquired knowledge.
---
paper_title: Integrated phrase segmentation and alignment algorithm for statistical machine translation

paper_content:

We present an integrated phrase segmentation/alignment algorithm (ISA) for statistical machine translation. Without the need of building an initial word-to-word alignment or initially segmenting the monolingual text into phrases as other methods do, this algorithm segments the sentences into phrases and finds their alignments simultaneously. For each sentence pair, ISA builds a two-dimensional matrix to represent a sentence pair where the value of each cell corresponds to the point-wise mutual information (MI) between the source and target words. Based on the similarities of MI values among cells, we identify the aligned phrase pairs. Once all the phrase pairs are found, we know both how to segment one sentence into phrases and also the alignments between the source and target sentences. We use monolingual bigram language models to estimate the joint probabilities of the identified phrase pairs. The joint probabilities are then normalized to conditional probabilities, which are used by the decoder. Despite its simplicity, this approach yields phrase-to-phrase translations with significant higher precisions than our baseline system where phrase translations are extracted from the HMM word alignment. When we combine the phrase-to-phrase translations generated by this algorithm with the baseline system, the improvement on translation quality is even larger.
---
paper_title: Effective Phrase Translation Extraction From Alignment Models

paper_content:

Phrase level translation models are effective in improving translation quality by addressing the problem of local re-ordering across language boundaries. Methods that attempt to fundamentally modify the traditional IBM translation model to incorporate phrases typically do so at a prohibitive computational cost. We present a technique that begins with improved IBM models to create phrase level knowledge sources that effectively represent local as well as global phrasal context. Our method is robust to noisy alignments at both the sentence and corpus level, delivering high quality phrase level translation pairs that contribute to significant improvements in translation quality (as measured by the BLEU metric) over word based lexica as well as a competing alignment based method.
---
paper_title: A Generalized Alignment-Free Phrase Extraction

paper_content:

In this paper, we present a phrase extraction algorithm using a translation lexicon, a fertility model, and a simple distortion model. Except these models, we do not need explicit word alignments for phrase extraction. For each phrase pair (a block), a bilingual lexicon based score is computed to estimate the translation quality between the source and target phrase pairs; a fertility score is computed to estimate how good the lengths are matched between phrase pairs; a center distortion score is computed to estimate the relative position divergence between the phrase pairs. We presented the results and our experience in the shared tasks on French-English.
---
paper_title: A Generalized Alignment-Free Phrase Extraction

paper_content:

In this paper, we present a phrase extraction algorithm using a translation lexicon, a fertility model, and a simple distortion model. Except these models, we do not need explicit word alignments for phrase extraction. For each phrase pair (a block), a bilingual lexicon based score is computed to estimate the translation quality between the source and target phrase pairs; a fertility score is computed to estimate how good the lengths are matched between phrase pairs; a center distortion score is computed to estimate the relative position divergence between the phrase pairs. We presented the results and our experience in the shared tasks on French-English.
---
paper_title: LOOSE PHRASE EXTRACTION WITH n-BEST ALIGNMENTS

paper_content:

Loose phrase extraction method is proposed and applied for phrase-based statistical machine translation. The method extracts phrase pairs that are not strictly consistent with word alignments. Two types of constraints on word positions are investigated for this method. Furthermore, n-best alignments are introduced for phrase extraction instead of the one-best. Experimental results show that the proposed approach outperforms the baseline system, Pharaoh system, for both one-best and n-best alignments.
---
paper_title: Integrating a Rule-based with a Hierarchical Translation System.

paper_content:

Recent developments on hybrid systems that combine rule-based machine translation (RBMT) systems with statistical machine translation (SMT) generally neglect the fact that RBMT systems tend to produce more syntactically well-formed translations than data-driven systems. This paper proposes a method that alleviates this issue by preserving more useful structures produced by RBMT systems and utilizing them in a SMT system that operates on hierarchical structures instead of flat phrases alone. For our experiments, we use Joshua as the decoder (Li et al., 2009). It is the first attempt towards a tighter integration of MT systems from different paradigms that both support hierarchical analyses. Preliminary results show consistent improvements over the previous approach.
---
paper_title: Using Moses to Integrate Multiple Rule-Based Machine Translation Engines into a Hybrid System

paper_content:

Based on an architecture that allows to combine statistical machine translation (SMT) with rule-based machine translation (RBMT) in a multi-engine setup, we present new results that show that this type of system combination can actually increase the lexical coverage of the resulting hybrid system, at least as far as this can be measured via BLEU score.
---
paper_title: Phrase Extraction for Japanese Predictive Input Method as Post-Processing

paper_content:

We propose a novel phrase extraction system to generate a phrase dictionary for predictive input methods from a large corpus. This system extracts phrases after counting n-grams so that it can be easily maintained, tuned, and re-executed independently. We developed a rule-based filter based on part-of-speech (POS) patterns to extract Japanese phrases. Our experiment shows usefulness of our system, which achieved a precision of 0.90 and a recall of 0.81, outperforming the N-gram baseline by a large margin.
---
paper_title: Integrated phrase segmentation and alignment algorithm for statistical machine translation

paper_content:

We present an integrated phrase segmentation/alignment algorithm (ISA) for statistical machine translation. Without the need of building an initial word-to-word alignment or initially segmenting the monolingual text into phrases as other methods do, this algorithm segments the sentences into phrases and finds their alignments simultaneously. For each sentence pair, ISA builds a two-dimensional matrix to represent a sentence pair where the value of each cell corresponds to the point-wise mutual information (MI) between the source and target words. Based on the similarities of MI values among cells, we identify the aligned phrase pairs. Once all the phrase pairs are found, we know both how to segment one sentence into phrases and also the alignments between the source and target sentences. We use monolingual bigram language models to estimate the joint probabilities of the identified phrase pairs. The joint probabilities are then normalized to conditional probabilities, which are used by the decoder. Despite its simplicity, this approach yields phrase-to-phrase translations with significant higher precisions than our baseline system where phrase translations are extracted from the HMM word alignment. When we combine the phrase-to-phrase translations generated by this algorithm with the baseline system, the improvement on translation quality is even larger.
---

Title: A Survey on Phrase Structure Learning Methods for Text Classification

Section 1: INTRODUCTION
Description 1: Introduce the topic of text classification, its applications, and the importance of phrase structure learning in improving text classification tasks.

Section 2: SURVEYED TECHNIQUES
Description 2: Summarize various phrase structure extraction techniques for text classification, detailing methods such as N-gram based approach, Rule based method, Word alignment based method, and others.

Section 3: Basic N-gram based approach
Description 3: Describe the N-gram based approach, including its statistical methods, applications, accuracy, and limitations.

Section 4: Rule based method
Description 4: Detail the rule-based method for phrase extraction, its approaches, accuracy, and comparison with N-gram based methods.

Section 5: Word alignment based method
Description 5: Discuss the word alignment based method along with its statistical approach, techniques, advantages, and measuring scores.

Section 6: Phrase alignment based method
Description 6: Explain the phrase alignment based method, including joint probability models, initial steps, performance, and improvements over other methods.

Section 7: Syntactic approach
Description 7: Outline the syntactic approach technique, including parsing of sentences, syntactic phrases, and BLEU score measurement.

Section 8: Mutual Information based method
Description 8: Describe the mutual information based method, including integrating phrase segmentation and alignment, its advantages, and measuring scores.

Section 9: Bilingual N-gram based approach
Description 9: Provide details on the bilingual N-gram based approach, including its phases, methods, benefits, and performance measures.

Section 10: Block based method
Description 10: Explain the block based method for phrase translation extraction, models used, and computational considerations.

Section 11: Clustering method
Description 11: Discuss the clustering method, its statistical approach, steps, and performance comparison.

Section 12: Loose phrase extraction method
Description 12: Describe the loose phrase extraction method with n-best alignments and constraints applied to extracted phrases.

Section 13: Word alignment and Rule based approach
Description 13: Provide an overview of the hybrid method integrating rule-based and hierarchical translation systems.

Section 14: N-gram and Rule based approach
Description 14: Explain the hybrid N-gram and Rule based approach, its methodology, errors observed, and performance measures.

Section 15: CLASSIFICATION
Description 15: Detail the classification of different phrase structure learning methods into statistical, rule-based, and hybrid methods.

Section 16: OBSERVATIONS AND DISCUSSION
Description 16: Compare and contrast various methods based on several factors and discuss their efficiency and performance.

Section 17: CONCLUSION
Description 17: Summarize the survey findings, emphasize the importance of phrases in text classification, and conclude with the most promising technique identified.