Search

In this article, we present a novel principled approach to passage-based (document) retrieval using fuzzy set theory. The approach formulates passage score combination according to general relevance decision principles. By operationalizing these principles using aggregation operators of fuzzy set theory, our approach justifies the common heuristics of taking the maximum constituent passage score as the overall document score. Experiments show that this heuristics is only the near best, with some fuzzy set aggregation operators stipulated in our approach being better methods. The significance of our principled approach is the applicability of many passage score combination methods, potentially bringing further performance enhancement. Experiments on several text retrieval conference collections demonstrate that our approach performs significantly better than document-based retrieval. While recent works in the literature mostly employ document-based rather than passage-based retrieval due to the common conception that document length normalization solves the problem of varying document lengths, our results show that document length normalization alone is not sufficient, especially in pseudo-relevance feedback retrieval.

Feature engineering is one aspect of knowledge engineering. Besides feature selection, the appropriate assignment of feature values is also crucial to the performance of many software applications, such as text categorization (TC) and speech recognition. In this work, we develop a general method to enhance TC performance by the use of context-dependent feature values (aka term weights), which are obtained by a novel adaptation of a context-dependent adjustment procedure previously shown to be effective in information retrieval. The motivation of our approach is that the general method can be used with different text representations and in combination of other TC techniques. Experiments on several test collections show that our context-dependent feature values can improve TC over traditional context-independent unigram feature values, using a strong classifier like Support Vector Machine (SVM), which past works have found to be hard to improve. We also show that the relative performance improvement of our method over the context-independent baseline is comparable to the levels attained by recent word embedding methods in the literature, while an advantage of our approach is that it does not require the substantial training needed to learn word embedding representations.

Model construction is a kind of knowledge engineering, and building retrieval models is critical to the success of search engines. This article proposes a new (retrieval) language model, called binary independence language model (BILM). It integrates two document-context based language models together into one by the log-odds ratio where these two are language models applied to describe document-contexts of query terms. One model is based on relevance information while the other is based on the non-relevance information. Each model incorporates link dependencies and multiple query term dependencies. The probabilities are interpolated between the relative frequency and the background probabilities. In a simulated relevance feedback environment of top 20 judged documents, our BILM performed statistically significantly better than the other highly effective retrieval models at 95% confidence level across four TREC collections using fixed parameter values for the mean average precision. For the less stable performance measure (i.e. precision at the top 10), no statistical significance is shown between the different models for the individual test collections although numerically our BILM is better than two other models with a confidence level of 95% based on a paired sign test across the test collections of both relevance feedback and retrospective experiments.

Given a set of clusters, we consider an optimization problem which seeks a subset of clusters that maximizes the microaverage F-measure. This optimal value can be used as an evaluation measure of the goodness of clustering. For arbitrarily overlapping clusters, finding the optimal value is NP-hard. We claim that a greedy approximation algorithm yields the global optimal solution for clusters that overlap only by nesting. We present a mathematical proof of this claim by induction. For a family of n clusters containing a total of N objects, this algorithm has an {\rm O}(n;{2}) time complexity and O(N) space complexity.

Recently, the increasing use of time series data has initiated various research and development attempts in the field of data and knowledge management. Time series data is characterized as large in data size, high dimensionality and update continuously. Moreover, the time series data is always considered as a whole instead of individual numerical fields. Indeed, a large set of time series data is from stock market. Stock time series has its own characteristics over other time series. Moreover, dimensionality reduction is an essential step before many time series analysis and mining tasks. For these reasons, research is prompted to augment existing technologies and build new representation to manage financial time series data. In this paper, financial time series is represented according to the importance of the data points. With the concept of data point importance, a tree data structure, which supports incremental updating, is proposed to represent the time series and an access method for retrieving the time series data point from the tree, which is according to their order of importance, is introduced. This technique is capable to present the time series in different levels of detail and facilitate multi-resolution dimensionality reduction of the time series data. In this paper, different data point importance evaluation methods, a new updating method and two dimensionality reduction approaches are proposed and evaluated by a series of experiments. Finally, the application of the proposed representation on mobile environment is demonstrated.

One of the major duties of financial analysts is technical analysis. It is necessary to locate the technical patterns in the stock price movement charts to analyze the market behavior. Indeed, there are two main problems: how to define those preferred patterns (technical patterns) for query and how to match the defined pattern templates in different resolutions. As we can see, defining the similarity between time series (or time series subsequences) is of fundamental importance. By identifying the perceptually important points (PIPs) directly from the time domain, time series and templates of different lengths can be compared. Three ways of distance measure, including Euclidean distance (PIP-ED), perpendicular distance (PIP-PD) and vertical distance (PIP-VD), for PIP identification are compared in this paper. After the PIP identification process, both template- and rule-based pattern-matching approaches are introduced. The proposed methods are distinctive in their intuitiveness, making them particularly user friendly to ordinary data analysts like stock market investors. As demonstrated by the experiments, the template- and the rule-based time series matching and subsequence searching approaches provide different directions to achieve the goal of pattern identification.

We describe the use of the discrete wavelet transform (DWT) for non-parametric linear time-invariant system identification. Identification is achieved by using a test excitation to the system under test (SUT) that also acts as the analyzing function for the DWT of the SUT's output, so as to recover the impulse response. The method uses as excitation any signal that gives an orthogonal inner product in the DWT at some step size (that cannot be 1). We favor wavelet scaling coefficients as excitations, with a step size of 2. However, the system impulse or frequency response can then only be estimated at half the available number of points of the sampled output sequence, introducing a multirate problem that means we have to 'oversample' the SUT output. The method has several advantages over existing techniques, e.g., it uses a simple, easy to generate excitation, and avoids the singularity problems and the (unbounded) accumulation of round-off errors that can occur with standard techniques. In extensive simulations, identification of a variety of finite and infinite impulse response systems is shown to be considerably better than with conventional system identification methods.

Detection of recognition errors is important in many areas, such as improving recognition performance, saving manual effort for proof-reading and post-editing, and assigning appropriate weights for retrieval in constructing digital libraries. We propose a novel application of multiple classifiers for the detection of recognition errors. A need for multiple classifiers emerges when a single classifier cannot improve recognition-error detection performance compared with the current detection scheme using a simple threshold mechanism. Although the single classifier does not improve recognition error performance, it serves as a baseline for comparison and the related study of useful features for error detection suggests three distinct cases where improvement is needed. For each case, the multiple classifier approach assigns a classifier to detect the presence or absence of errors and additional features are considered for each case. Our results show that the recall rate (70-80%) of recognition errors, the precision rate (80-90%) of recognition error detection and the saving in manual effort (75%) were better than the corresponding performance using a single classifier or a simple threshold detection scheme.

Language modeling is a current research topic in many domains including speech recognition, optical character recognition, handwriting recognition, machine translation and spelling correction. There are two main types of language models, the mathematical and the linguistic. The most widely used mathematical language model is the n-gram model inferred from statistics. This model has three problems: long distance restriction, recursive nature and partial language understanding. Language models based on linguistics present many difficulties when applied to large scale real texts. We present here a new hybrid language model that combines the advantages of the n-gram statistical language model with those of a linguistic language model which makes use of grammatical or semantic rules. Using suitable rules, this hybrid model can solve problems such as long distance restriction, recursive nature and partial language understanding. The new language model has been effective in experiments and has been incorporated in Chinese sentence input products for Windows and Macintosh OS.

Time series data, due to their numerical and continuous nature, are difficult to process, analyze, and mine. However, these tasks become easier when the data can be transformed into meaningful symbols. Most recent works on time series only address how to identify a given pattern from a time series and do not consider the problem of identifying a suitable set of time points for segmenting the time series in accordance with a given set of pattern templates (e.g., a set of technical patterns for stock analysis). However, the use of fixed-length segmentation is an oversimplified approach to this problem; hence, a dynamic approach (with high controllability) is preferable so that the time series can be segmented flexibly and effectively according to the needs of the users and the applications. In view of the fact that this segmentation problem is an optimization problem and evolutionary computation is an appropriate tool to solve it, we propose an evolutionary time series segmentation algorithm. This approach allows a sizeable set of pattern templates to be generated for mining or query. In addition, defining similarity between time series (or time series segments) is of fundamental importance in fitness computation. By identifying the perceptually important points directly from the time domain, time series segments and templates of different lengths can be compared and intuitive pattern matching can be carried out in an effective and efficient manner. Encouraging experimental results are reported from tests that segment both artificial time series generated from the combinations of pattern templates and the time series of selected Hong Kong stocks.

This paper describes the design and development of a computer interface for blind and visually-impaired users, who are native speakers of Cantonese (i.e. a Chinese dialect). Apart from enabling the interface to (1) produce Chinese voice output, (2) convert Chinese characters to Braille codes, (3) facilitate Chinese Braille input, and (4) operate in a Microsoft Chinese Windows environment, the significant aspects of this paper include the following: (1) the description of an integrated architecture, which can be used for other languages; (2) a general bilingual Braille input mechanism; (3) a sentence-based input method that can be used for contracted-Braille-to-text conversion with an error rate of about 6%, operating at about 700 characters/second using a Pentium II 300 MHz PC; (4) a code-mixed synthesis module for general bilingual and multilingual applications; (5) the potential to directly adopt the system for use with other ideographic languages (like Japanese and Korean), as well as agglutinating languages like Finnish and Turkish, which have no space between words.

With the advent of the Internet and intranets, substantial interest is being shown in Asian language information retrieval; especially in Chinese, which is a good example of an Asian ideographic language (other examples include Japanese and Korean). Since, in this type of language, spaces do not delimit words, an important issue is which index terms should be extracted from documents. This issue also has wider implications for indexing other languages such as agglutinating languages (e.g., Finnish and Turkish), archaic ideographic languages like Egyptian hieroglyphs, and other types of information such as data stored in genomic databases. Although comparisons of indexing strategies for Chinese documents have been made, almost all of them are based on a single retrieval model. This article compares the performance of various combinations of indexing strategies (i.e., character, word, short-word, bigram, and Pircs indexing) and retrieval models (i.e., vector space, 2-Poisson, logistic regression, and Pircs models). We determine which model (and its parameters) achieves the (near) best retrieval effectiveness without relevance feedback, and compare it with the open evaluations (i.e., TREC and NTCIR) for both long and title queries. In addition, we describe a more extensive investigation of retrieval efficiency. In particular, the storage cost of word indexing is only slightly more than character indexing, and bigram indexing is about double the storage cost of other indexing strategies. The retrieval time typically varies linearly with the number of unique terms in the query, which is supported by correlation values above 90%. The Pircs retrieval system achieves robust and good retrieval performance, but it appears to be the slowest method, whereas vector space models were not very effective in retrieval, but were able to respond quickly. For robust, near-best retrieval effectiveness, without considering storage overhead, the 2-Poisson model using bigram indexing appears to be a good compromise between retrieval effectiveness and efficiency for both long and title queries.

XML holds the promise to yield (1) a more precise search by providing additional information in the elements, (2) a better integrated search of documents from heterogeneous sources, (3) a powerful search paradigm using structural as well as content specifications, and (4) data and information exchange to share resources and to support cooperative search. We survey several indexing techniques for XML documents, grouping them into flat-file, semistructured, and structured indexing paradigms. Searching techniques and supporting techniques for searching are reviewed, including full text search and multistage search. Because searching XML documents can be very flexible, various search result presentations are discussed, as well as database and information retrieval system integration and XML query languages. We also survey various retrieval models, examining how they would be used or extended for retrieving XML documents. To conclude the article, we discuss various open issues that XML poses with respect to information retrieval and database research.

Retrieval effectiveness depends on how terms are extracted and indexed. For Chinese text (and others like Japanese and Korean), there are no space to delimit words. Indexing using hybrid terms (i.e. words and bigrams) were able to achieve the best precision amongst homogenous terms at a lower storage cost than indexing with bigrams. However, this was tested with conjunctive queries. Here, we extended the weighted Boolean models using fuzzy and p-norm measures, as well as the vector space model using the cosine measure, for processing hybrid terms. Our evaluation shows that all IR models using hybrid terms achieve better average precision over those using words. Across different recall values, the weighted Boolean model using fuzzy measures with hybrid terms achieve consistently about 8% higher than those using words. The vector space model using the cosine measures with hybrid terms achieved the best improvement in the average recall and precision.

Context windows are important for a variety of natural language analysis and processing. A trade-off exists between the task performance and the size of the context. Lucassen and Mercer used mutual information to determine the size of the context for English text. We apply the same technique to determine the Context window size for Chinese text. In addition, we use the association score, proposed by Church. The association score is directly related to the prediction ability of units in the context. To reduce the effects of spurious associations, the association score values at the N% quartile is used, instead of the maximum, and the association score derived from low frequency occurrences (i.e.

This paper introduces and reviews stochastic phonographic transduction (SPT), a trainable (“data-driven”) technique for letter-to-phoneme conversion based on formal language theory, as well as describing and detailing one particularly simple realization of SPT. The spellings and pronunciations of English words are modelled as the productions of a stochastic grammar, inferred from example data in the form of a pronouncing dictionary. The terminal symbols of the grammar are letter–phoneme correspondences, and the rewrite (production) rules of the grammar specify how these are combined to form acceptable English word spellings and their pronunciations. Given the spelling of a word as input, a pronunciation can then be produced as output by parsing the input string according to the letter-part of the terminals and selecting the “best” sequence of corresponding phoneme-parts according to some well-motivated criteria. Although the formalism is in principle very general, restrictive assumptions must be made if practical, trainable systems are to be realized. We have assumed at this stage that the grammar is regular. Further, word generation is modelled as a Markov process in which terminals (correspondences) are simply concatenated. The SPT learning task then amounts to the inference of a set of correspondences and estimation from the training data of their associated transition probabilities. Transduction to produce a pronunciation for a word given its spelling is achieved by Viterbi decoding, using a maximum likelihood criterion. Results are presented for letter–phoneme alignment and transduction for the dictionary training data, unseen dictionary words, unseen proper nouns and novel (pseudo-)words. Two different ways of inferring correspondences are described and compared. It is found that the provision of quite limited information about the alternating vowel/consonant structure of words aids the inference process significantly. Best transduction performance obtained on unseen dictionary words is 93·7% phonemes correct, conservatively scored. Automatically inferred correspondences also consistently out-perform a published set of manually derived correspondences when used for SPT. Although the comparison is difficult to make, we believe that current results for letter-to-phoneme conversion are at least as good as the best reported so far for a data-driven approach, while being comparable in performance to knowledge-based approaches.

In ad hoc information retrieval (IR), some information need (e.g., find the advantages and disadvantages of smoking) requires the explicit identification of information related to the discourse type (e.g., advantages/ disadvantages) as well as to the topic (e.g., smoking). Such information need is not uncommon and may not be satisfied by using conventional retrieval methods. We extend existing retrieval models by adding a re-ranking strategy based on a novel graph-based retrieval model using document contexts that are called information units (IU). For evaluation, we focused on a discourse type that appeared in a subset of TREC topics where the retrieval effectiveness achieved by our conventional retrieval models for those topics was low. We showed that our approach is able to enhance the retrieval effectiveness for the selected TREC topics. This shows that our preliminary investigation is promising and deserves further investigation.

The distribution of the number of documents in topic classes is typically highly skewed. This leads to good micro-average performance but not so desirable macro-average performance. By viewing topics as clusters in a high dimensional space, we propose the use of clustering to determine subtopic clusters for large topic classes by assuming that large topic clusters are in general a mixture of a number of subtopic clusters. We used the Reuters News articles and support vector machines to evaluate whether using subtopic cluster can lead to better macro-average performance.

This paper examines the impact of recognition errors on spoken Cantonese query retrieval effectiveness. One of the largest test collections provided by NTCIR for evaluating Chinese information retrieval is used. The retrieval system uses one of the best models (2-Poisson) and the robust bigram indexing strategy. If there are no syllable recognition errors, then the errors in converting spelling (called pinyin) to characters degrades the performance by 3.9% points which is not statistically significant. Otherwise, the performance dropped by 10.2% points which is statistically significant. We improved our system by merging the /n/ and /l/ phone labels and retrained the syllable-to-text conversion routines. The improved retrieval system dropped only 6.4% points.

In this paper, semantic role labeling is addressed. We formulate the problem as a classification task, in which the words of a sentence are assigned to semantic role classes using a classifier. The maximum entropy approach is applied to train the classifier, by using a large real corpus annotated with argument structures.

This paper investigates (1) the robustness of epoch detection (i.e. identification of glottal closure) by the wavelet transform and (2) the methods to improve its robustness. We achieved a similar identification performance (2% error rate) to earlier investigation using the spline wavelet transform, under Gaussian noise degradation. However, the performance under other types of noise degradation, such as periodic noise (e.g. traffic lights) and short noise (e.g. keyboard noise), is not as robust as before. The scale matching technique could not secure good performance because the spline wavelet has poor recall performance. We explored the use of the Gaussian wavelet transform. Instead of scale matching, a single level is used and the recall of epochs associated with the nearest laryngograph differences by the Gaussian wavelet is about 30% more than by the spline wavelet, across different types of noise degradation. However, the spline wavelet has less false alarm (29% on average) in identification and the peaks correspond well to epoch positions (with less [standard] deviation). We evaluated detection schemes using both scalograms of Gaussian and spline wavelets and achieved improvement of recall (26%), with a relative position consistency of 1.4 ms.

In this study, we propose a knowledge-independent method for aligning terms and thus extracting translations from a small, domain-specific corpus consisting of parallel English and Chinese court judgments from Hong Kong. With a sentence-aligned corpus, translation equivalences are suggested by analysing the frequency profiles of parallel concordances. The method overcomes the limitations of conventional statistical methods which require large corpora to be effective, and lexical approaches which depend on existing bilingual dictionaries. Pilot testing on a parallel corpus of about 113K Chinese words and 120K English words gives an encouraging 85% precision and 45% recall. Future work includes fine-tuning the algorithm upon the analysis of the errors, and acquiring a translation lexicon for legal terminology by filtering out general terms.

Despite progress in the development of computational means, human input is still critical in the production of consistent and useable aligned corpora and term banks. This is especially true for specialized corpora and term banks whose end-users are often professionals with very stringent requirements for accuracy, consistency and coverage. In the compilation of a high quality Chinese-English legal glossary for ELDoS project, we have identified a number of issues that make the role human input critical for term alignment and extraction. They include the identification of low frequency terms, paraphrastic expressions, discontinuous units, and maintaining consistent term granularity, etc. Although manual intervention can more satisfactorily address these issues, steps must also be taken to address intra- and inter-annotator inconsistency.

This chapter describes the use of stochastic transducers to model and to perform the conversion of English word spellings to phonemic equivalents. Generic word structures can be described by a simple regular grammar which usually overgenerates, producing many candidate translations. The ‘best’ candidate is selected based on the maximum likelihood criterion and the stochastic translation is assumed to be a Markov chain. The initial grammar allows any input string to translate to any output string. A set of example translations is used to refine this grammar to a more specific form: the Kleene closure of letter-phoneme correspondences. These correspondences were inferred by segmenting the maximum likelihood alignment of example translations when a special type of transducer movement is found, or when a segmentation point is found in one of the two (orthographic or phonemic) domains. For efficient translation, the transducers were implemented as stochastic generalised sequential Moore machines so that useless intermediate states in translation and Markov probabilities can be eliminated and reduced, respectively. The current translation accuracy on a per symbol basis is 93.7% on a representative 1667 word test set selected from the Oxford Advanced Learners Dictionary.

Retrieval effectiveness depends on how terms are extracted and indexed. For Chinese text (and others like Japanese and Korean), there are no space to delimit words. Indexing using hybrid terms (i.e. words and bigrams) were able to achieve the best precision amongst homogenous terms at a lower storage cost than indexing with bigrams. However, this was tested with conjunctive queries. Here, we extended the weighted Boolean models using fuzzy and p-norm measures, as well as the vector space model using the cosine measure, for processing hybrid terms. Our evaluation shows that all IR models using hybrid terms achieve better average precision over those using words. Across different recall values, the weighted Boolean model using fuzzy measures with hybrid terms achieve consistently about 8% higher than those using words. The vector space model using the cosine measures with hybrid terms achieved the best improvement in the average recall and precision.

This paper describes our effort to mark and annotate read Cantonese speech for both citation pronunciation and reading aloud sentences/phrases. Four signals are recorded simultaneously to assist marking and annotation: acoustic, laryngograph, nasal and air burst signals. A coarse match between voiced segments of speech and voiced segments of the phonetic spelling of the utterance is executed by dynamic programming as for approximate string matching. Finally, we discuss general issues in the design of our software for annotation.

This paper describes a set of computer programs for Chinese corpus analysis. These programs include (1) extraction of different characters, bigrams and words; (2) word segmentation based on bigram, maximal-matching and the combined technique; (3) identification of special terms; (4) Chinese concordancing; (5) compiling collocation statistics and (6) evaluation utilities. These programs run on the IBM-PC and batch programs co-ordinate the use of these programs.

The authors describe the automatic inferencing of letter-phoneme correspondences with predefined consonant and vowel patterns, which imply a segmentation of the word in one domain. The technique obtains the maximum likelihood (ML) alignment of the training word, and correspondences are found according to where the segmentation projects onto the ML alignment. Here, the phoneme strings were segmented depending on the number of consonant phonemes preceding or following the vowel phoneme. Sets of correspondences were evaluated according to the performance obtained when they were used for text-phonemic alignment and translation. The number of correspondences inferred was too large to evaluate using Markov statistics. Instead, hidden Markov statistics were used, where the storage demand is further reduced by a recording technique. Performance improves significantly as the number of consonants included in the pattern is increased. The performance of correspondences with predefined V.C* patterns was consistently better than with C*.V patterns. >

An algorithm for inferring correspondences between letters and phonemes from a large set of word spellings and their associated phonemic forms is described. The algorithm uses two techniques to infer correspondences: delimiting and dynamic time warping (DTW). The first technique delimits the part of the word spelling and pronunciation that cannot be aligned with the existing set of correspondences. The second technique derives correspondences from the delimited part of that word. The inferred correspondences are evaluated in terms of translation performance tested with unseen words, proper names and novel words. The translation performance is compared with those obtained using the manually driven correspondences as the benchmark. Nonparametric statistical tests are used to establish whether the performances of inferred correspondences are significantly different from the manually derived correspondences. >

The bigram language models are popular, in much language processing applications, in both Indo-European and Asian languages. However, when the language model for Chinese is applied in a novel domain, the accuracy is reduced significantly, from 96% to 78% in our evaluation. We apply pattern recognition techniques (i.e. Bayesian, decision tree and neural network classifiers) to discover language model errors. We have examined 2 general types of features: model-based and language-specific features. In our evaluation, Bayesian classifiers produce the best recall performance of 80% but the precision is low (60%). Neural network produced good recall (75%) and precision (80%) but both Bayesian and Neural network have low skip ratio (65%). The decision tree classifier produced the best precision (81%) and skip ratio (76%) but its recall is the lowest (73%).

An inference algorithm to obtain letter-phoneme correspondences for English using image-processing techniques is described. The main idea of the inference algorithm is to construct a table of association indices. The table is regarded as an image and image-processing algorithms are use to derive letter-phoneme correspondences. The advantages of the technique are that the association index has a theoretical basis in terms of modeling spelling and pronunciation as a homogeneous Markov chain, computational demand is low, and the inference process is not dependent on the ordering of the sample. The authors have implemented both a thresholding and a minimum spanning tree technique to derive correspondences. Illustrative examples are given for each technique. >