Bagging (Breiman 1996) and its variants is one of the most popular methods in aggregating classifiers and regressors. Originally, its analysis assumed that the bootstraps are built from an unlimited, independent source of samples, therefore we call this form of bagging ideal-bagging. However in the real world, base predictors are trained on data subsampled from a limited number of training samples and thus they behave very differently. We analyze the effect of intersections between bootstraps, obtained by subsampling, to train different base predictors. Most importantly, we provide an alternative subsampling method called design-bagging based on a new construction of combinatorial designs, and prove it universally better than bagging. Methodologically, we succeed at this level of generality because we compare the prediction accuracy of bagging and design-bagging relative to the accuracy ideal-bagging. This finds potential applications in more involved bagging-based methods. Our analytical results are backed up by experiments on classification and regression settings.

@inproceedings{PXZ14, author = {Periklis Papakonstantinou, Jia Xu, Cao Zhu}, title = {Bagging by Design (On the Sub-optimality of Bagging)}, booktitle = {Proceedings of AAAI}, series = {AAAI '14}, year = {2014}, location = {Quebec City, Quebec, Canada}, publisher = {Association for the Advancement of Artificial Intelligence}, address = {Quebec City, Quebec, Canada} }

Translation retrieval aims to search for the most probable translation candidate from a set of target-language strings for a given source-language string. Existing work only uses 1-best translations as queries and suffers from the translation error propagation problem. In this work, we propose to use {\em query lattice}, which is a compact representation of exponentially many queries, in translation retrieval to alleviate the translation error propagation problem. As compared with using 1-best translations as queries, our approach explores a much larger search space (from 1 query to 1.24*10^62 queries), runs much faster (from 0.75 second per sentence to 0.13), and retrieves more accurately (from 83.76% to 93.16%). We also evaluate our approach on extracting parallel sentences from comparable corpora. Experiments show that our translation retrieval system significantly outperforms the state-of-the-art parallel corpus mining system.

@inproceedings{DCLXS14, author = {Meiping Dong, Yong Cheng, Yang Liu, Jia Xu and Maosong Sun}, title = {Query Lattice for Translation Retrieval}, booktitle = {Proceedings of COLING}, series = {COLING '14}, year = {2014}, isbn = {978-1-937284-11-4}, location = {Dublin, Ireland}, publisher = {International Committee on Computational Linguistics }, address = {Dublin, Ireland} }

Contemporary video search and categorization are non-trivial tasks due to the massively increasing amount and content variety of videos. We put forward the study of visual saliency models in video. Such a model is employed to identify salient objects from the image background. Starting from the observation that motion information in video often attracts more human attention compared to static images, we devise a region contrast based saliency detection model using spatialtemporal cues (RCST). We introduce and study four saliency principles to realize the RCST. This generalizes the previous static image for saliency computational model to video. We conduct experiments on a publicly available video segmentation database where our method significantly outperforms seven state-of-the-art methods with respect to PR curve, ROC curve and visual comparison.

@inproceedings{GQXW13, author = {Chuang Gan, Zengchang Qin, Jia Xu, Tao Wan}, title = {Salient Object Detection in Image Sequences via Spatial-Temporal Cue}, booktitle = {Proceedings of Visual Communications and Image Processing (VCIP)}, series = {VCIP '13}, year = {2013}, isbn = {978-1-937284-11-4}, location = {Sarawak, Malaysia}, publisher = {IEEE}, address = {Sarawak, Malaysia}, }

This paper investigates improving supervised word segmentation accuracy with unlabeled data. Both large-scale in-domain data and small-scale document text are considered. We present a unified solution to include features derived from unlabeled data to a discrimina- tive learning model. For the large-scale data, we derive string statistics from Gigaword to assist a character-based segmenter. In addi- tion, we introduce the idea about transductive, document-level segmentation, which is de- signed to improve the system recall for out-of- vocabulary (OOV) words which appear more than once inside a document. Novel features1 result in relative error reductions of 13.8% and 15.4% in terms of F-score and the recall of OOV words respectively.

@inproceedings{Sun:2011:ECW:2145432.2145538, author = {Sun, Weiwei and Xu, Jia}, title = {Enhancing Chinese word segmentation using unlabeled data}, booktitle = {Proceedings of the Conference on Empirical Methods in Natural Language Processing}, series = {EMNLP '11}, year = {2011}, isbn = {978-1-937284-11-4}, location = {Edinburgh, United Kingdom}, pages = {970--979}, numpages = {10}, url = {http://dl.acm.org/citation.cfm?id=2145432.2145538}, acmid = {2145538}, publisher = {Association for Computational Linguistics}, address = {Stroudsburg, PA, USA} }

The processing of many natural languages suf- fers from scarce linguistic resources. We in- troduce the idea of compatibility to extend training data for machine translation: If trans- lation hypotheses by multiple systems are measured as compatible, they are considered as reliable predictions. By this way, we gen- erate virtual parallel data per bridge language, and re-compiling on this corpus improves our machine translation quality by more than 30% relatively.

@article{xu2011generating, title={Generating virtual parallel corpus: A compatibility centric method}, author={Xu, Jia and Sun, Weiwei}, journal={Proceedings of the Machine Translation Summit XIII}, year={2011} }

The overwhelming majority of the languages in the world are spoken by less than 50 million native speakers, and automatic translation of many of these languages is less investigated due to the lack of linguistic resources such as parallel corpora. In the ACCURAT project we will work on novel methods how comparable corpora can compensate for this shortage and improve machine translation systems of under-resourced languages. Translation systems on eighteen European language pairs will be investigated and methodologies in corpus linguistics will be greatly advanced. We will explore the use of preliminary SMT models to identify the parallel parts within comparable corpora, which will allow us to derive better SMT models via a bootstrapping loop.

@inproceedings{eisele2010improving, title={Improving machine translation performance using comparable corpora}, author={Eisele, Andreas and Xu, Jia}, booktitle={Proceedings of the 3rd Workshop on Building and Using Comparable Corpora. Applications of Parallel and Comparable Corpora in Natural Language Engineering and the Humanities}, pages={35--39}, year={2010}, organization={Citeseer} }

@inbook{ Title = {Synchronous Learning of ChineseWord Segmentation and Word Alignment}, Author = {Jia Xu and Jianfeng Gao and Kristina Toutanova, Hermann Ney}, BookTitle = {Handbook of Natural Language Processing and Machine Translation}, Year = {2011}, Publisher = {Springer}, Pages = {135-163}, Edition = {1}, Chapter = {2.2} }

We describe our hybrid machine trans- lation system which has been developed for and used in the WMT10 shared task. We compute translations from a rule- based MT system and combine the re- sulting translation “templates” with par- tial phrases from a state-of-the-art phrase- based, statistical MT engine. Phrase sub- stitution is guided by several decision factors, a continuation of previous work within our group. For the shared task, we have computed translations for six lan- guage pairs including English, German, French and Spanish. Our experiments have shown that our shallow substitu- tion approach can effectively improve the translation result from the RBMT system; however it has also become clear that a deeper integration is needed to further im- prove translation quality.

@inproceedings{Federmann:2010:ESH:1868850.1868858, author = {Federmann, Christian and Eisele, Andreas and Uszkoreit, Hans and Chen, Yu and Hunsicker, Sabine and Xu, Jia}, title = {Further experiments with shallow hybrid MT systems}, booktitle = {Proceedings of the Joint Fifth Workshop on Statistical Machine Translation and MetricsMATR}, series = {WMT '10}, year = {2010}, isbn = {978-1-932432-71-8}, location = {Uppsala, Sweden}, pages = {77--81}, numpages = {5}, url = {http://dl.acm.org/citation.cfm?id=1868850.1868858}, acmid = {1868858}, publisher = {Association for Computational Linguistics}, address = {Stroudsburg, PA, USA}, }

Words in Chinese text are not naturally separated by delimiters, which poses a challenge to standard machine translation (MT) systems. In MT, the widely used approach is to apply a Chinese word seg- menter trained from manually annotated data, using a fixed lexicon. Such word segmentation is not necessarily optimal for translation. We propose a Bayesian semi-supervised Chinese word segmenta- tion model which uses both monolingual and bilingual information to derive a seg- mentation suitable for MT. Experiments show that our method improves a state-of- the-art MT system in a small and a large data environment.

@inproceedings{xu2008bayesian, title={Bayesian semi-supervised chinese word segmentation for statistical machine translation}, author={Xu, Jia and Gao, Jianfeng and Toutanova, Kristina and Ney, Hermann}, booktitle={Proceedings of the 22nd International Conference on Computational Linguistics-Volume 1}, pages={1017--1024}, year={2008}, organization={Association for Computational Linguistics} }

In this work, the problem of extracting phrase translation is formulated as an information re- trieval process implemented with a log-linear model aiming for a balanced precision and re- call. We present a generic phrase training al- gorithm which is parameterized with feature functions and can be optimized jointly with the translation engine to directly maximize the end-to-end system performance. Multiple data-driven feature functions are proposed to capture the quality and confidence of phrases and phrase pairs. Experimental results demon- strate consistent and significant improvement over the widely used method that is based on word alignment matrix only.

@inproceedings{deng2008phrase, title={Phrase table training for precision and recall: What makes a good phrase and a good phrase pair?}, author={Deng, Yonggang and Xu, Jia and Gao, Yuqing}, booktitle={ACL}, pages={81--88}, year={2008} }

While statistical machine translation (SMT) has advanced significantly with better modeling techniques and much more training data, domain specific SMT has received much less attention and leaves much room for further improvements. In this work, we address domain issues and propose to use the combination of feature weights and language model adaptation, to distinguish multiple domains, which share a general translation engine with phrase-based log-linear models. The proposed method requires much less parallel data than what is typically used to build a domain independent system, which makes it easy, cheap and efficient to capture as many domains as required. Domain adaptation during decoding is approached with source text classification methods. Our results on the GALE tasks show significant improvements with the proposed domain dependent translation than domain independent translation.

@article{xu2007domain, title={Domain dependent statistical machine translation}, author={Xu, Jia and Deng, Yonggang and Gao, Yuqing and Ney, Hermann}, journal={MT Summit XI}, year={2007} }

In statistical machine translation, large numbers of parallel sentences are required to train the model parameters. However, plenty of the bilingual language resources available on web are aligned only at the document level. To exploit this data, we have to extract the bilingual sentences from these documents. The common method is to break the doc- uments into segments using predefined anchor words, then these segments are aligned. This approach is not error free, incorrect alignments may decrease the translation quality. We present an alternative approach to ex- tract the parallel sentences by partitioning a bilingual document into two pairs. This process is performed recursively until all the sub-pairs are short enough. In experiments on the Chinese-English FBIS data, our method was capable of producing translation results comparable to those of a state-of-the-art sentence aligner. Using a combination of the two approaches leads to better translation per- formance.

@inproceedings{Xu:2006:PPD:1654650.1654662, author = {Xu, Jia and Zens, Richard and Ney, Hermann}, title = {Partitioning parallel documents using binary segmentation}, booktitle = {Proceedings of the Workshop on Statistical Machine Translation}, series = {StatMT '06}, year = {2006}, location = {New York City, New York}, pages = {78--85}, numpages = {8}, url = {http://dl.acm.org/citation.cfm?id=1654650.1654662}, acmid = {1654662}, publisher = {Association for Computational Linguistics}, address = {Stroudsburg, PA, USA}, } [

Evaluation of automatic translation output is a difficult task. Several performance measures like Word Error Rate, Position Independent Word Error Rate and the BLEU and NIST scores are widely use and provide a useful tool for comparing different systems and to evaluate improvements within a system. However the interpretation of all of these measures is not at all clear, and the identification of the most prominent source of errors in a given system using these measures alone is not possible. Therefore some analysis of the generated translations is needed in order to identify the main problems and to focus the research efforts. This area is however mostly unexplored and few works have dealt with it until now. In this paper we will present a framework for classification of the errors of a machine translation system and we will carry out an error analysis of the system used by the RWTH in the first TC-STAR evaluation.

@inproceedings{vilar2006error, title={Error analysis of statistical machine translation output}, author={Vilar, David and Xu, Jia and d’Haro, Luis Fernando and Ney, Hermann}, booktitle={Proceedings of LREC}, pages={697--702}, year={2006} }

A Chinese sentence is represented as a sequence of charac- ters, and words are not separated from each other. In statisti- cal machine translation, the conventional approach is to seg- ment the Chinese character sequence into words during the pre-processing. The training and translation are performed afterwards. However, this method is not optimal for two rea- sons: 1. The segmentations may be erroneous. 2. For a given character sequence, the best segmentation depends on its context and translation. In order to minimize the translation errors, we take dif- ferent segmentation alternatives instead of a single segmen- tation into account and integrate the segmentation process with the search for the best translation. The segmentation de- cision is only taken during the generation of the translation. With this method we are able to translate Chinese text at the character level. The experiments on the IWSLT 2005 task showed improvements in the translation performance using two translation systems: a phrase-based system and a finite state transducer based system. For the phrase-based system, the improvement of the BLEU score is 1.5% absolute.

@inproceedings{xu2005integrated, title={Integrated Chinese word segmentation in statistical machine translation}, author={Xu, Jia and Matusov, Evgeny and Zens, Richard and Ney, Hermann}, booktitle={Proc. of IWSLT}, year={2005} }

We give an overview of the RWTH phrase-based statistical machine translation system that was used in the evaluation campaign of the International Workshop on Spoken Lan- guage Translation 2005. We use a two pass approach. In the first pass, we gen- erate a list of the N best translation candidates. The second pass consists of rescoring and reranking this N -best list. We will give a description of the search algorithm as well as the models that are used in each pass. We participated in the supplied data tracks for man- ual transcriptions for the following translation direc- tions: Arabic-English, Chinese-English, English-Chinese and Japanese-English. For Japanese-English, we also partic- ipated in the C-Star track. In addition, we performed trans- lations of automatic speech recognition output for Chinese- English and Japanese-English. For both language pairs, we translated the single-best ASR hypotheses. Additionally, we translated Chinese ASR lattices.

@inproceedings{zens2005rwth, title={The RWTH phrase-based statistical machine translation system}, author={Zens, Richard and Bender, Oliver and Hasan, Sa{\v{s}}a and Khadivi, Shahram and Matusov, Evgeny and Xu, Jia and Zhang, Yuqi and Ney, Hermann}, booktitle={Proceedings of the International Workshop on Spoken Language Translation (IWSLT)}, pages={155--162}, year={2005} }

In statistical machine translation, word alignment models are trained on bilingual corpora. Long sentences pose severe problems: 1. the high computational requirements; 2. the poor quality of the resulting word alignment. We present a sentence-segmentation method that solves these problems by splitting long sentence pairs. Our approach uses the lexicon information to locate the optimal split point. This method is evaluated on two Chinese-English translation tasks in the news domain. We show that the segmentation of long sentences before training significantly improves the final translation quality of a state-of-the-art machine translation system. In one of the tasks, we achieve an improvement of the BLEU score of more than 20% relative.

@inproceedings{xu2005sentence, title={Sentence segmentation using IBM word alignment model 1}, author={Xu, Jia and Zens, Richard and Ney, Hermann}, booktitle={Proceedings of EAMT 2005 (10th Annual Conference of the European Association for Machine Translation)}, pages={280--287}, year={2005} }

In Chinese texts, words are not separated by white spaces. This is problematic for many nat- ural language processing tasks. The standard approach is to segment the Chinese character sequence into words. Here, we investigate Chi- nese word segmentation for statistical machine translation. We pursue two goals: the first one is the maximization of the final translation qual- ity; the second is the minimization of the man- ual effort for building a translation system. The commonly used method for getting the word boundaries is based on a word segmenta- tion tool and a predefined monolingual dictio- nary. To avoid the dependence of the trans- lation system on an external dictionary, we have developed a system that learns a domain- specific dictionary from the parallel training corpus. This method produces results that are comparable with the predefined dictionary. Further more, our translation system is able to work without word segmentation with only a minor loss in translation quality.

@inproceedings{xu2004we, title={Do we need Chinese word segmentation for statistical machine translation}, author={Xu, Jia and Zens, Richard and Ney, Hermann}, booktitle={Proceedings of the Third SIGHAN Workshop on Chinese Language Learning}, pages={122--128}, year={2004} }

Application No. 12/163.119, (ASM 8310) MS 323635.01, Redmond, Washington, June 2008