Search

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.

It is relatively easy to state that information retrieval (IR) is a scientific discipline but it is rather difficult to understand why it is science because what is science is still under debate in the philosophy of science. To be able to convince others that IR is science, our ability to explain why is crucial. To explain why IR is a scientific discipline, we use a theory and a model of scientific study, which were proposed recently. The explanation involves mapping the knowledge structure of IR to that of well-known scientific disciplines like physics. In addition, the explanation involves identifying the common aim, principles and assumptions in IR and in well-known scientific disciplines like physics, so that they constrain the scientific investigation in IR in a similar way as in physics. Therefore, there are strong similarities in terms of the knowledge structure and the constraints of the scientific investigations between IR and scientific disciplines like physics. Based on such similarities, IR is considered a scientific discipline.

A crucial aspect of scientific realism is what do we mean by true. In Luk’s theory and model of scientific study, a theory can be believed to be “true” but a model is only accurate. Therefore, what do we mean by a “true” theory in scientific realism? Here, we focus on exploring the notion of truth by some thought experiments and we come up with the idea that truth is related to what we mean by the same. This has repercussion to the repeatability of the experiments and the predictive power of scientific knowledge. Apart from sameness, we also found that truth is related to the granularity of the observation, the limit of detection, the distinguishability of the objects in theory, the simultaneous measurements of objects/processes, the consistencies of the theory and the one-to-one correspondence between terms/events and objects/processes, respectively. While there is no guarantee that we can arrive at the final “true” theory, we have a process/procedure with more and more experiments together with our own ingenuity, to direct us towards such a “true” theory. For quantum mechanics, since a particle is also regarded as a wave, quantum mechanics cannot be considered as a true theory based on the correspondence theory of truth. Failing this, truth may be defined by the coherence theory of truth which is similar to the coherence of beliefs. However, quantum mechanics may not be believed to be a true theory based on the coherence theory of truth because wave properties and particle properties may contradict. Further research is needed to address this problem if we want to regard quantum mechanics as a “true” theory.

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.

Recently, Luk mentioned that scientific knowledge both explains and predicts. Do these two functions of scientific knowledge have equal significance, or is one of the two functions more important than the other? This commentary explains why prediction may be mandatory but explanation (based intuitively on our everyday experience) may be only desirable and optional.

Recently, Luk tried to establish a model and a theory of scientific studies. He focused on articulating the theory and the model, but he did not emphasize relating them to some issues in philosophy of science. In addition, they might explain some of the issues in philosophy of science, but such explanation is not articulated in his papers. This paper explores the implications and extensions of Luk’s work in philosophy of science or science in general.

This paper presents a theory of scientific study which is regarded as a social learning process of (working) scientific knowledge creation, revision, application, monitoring (e.g., confirmation) and dissemination (e.g., publication) with the aim of securing good quality, general, objective, testable and complete scientific knowledge of the domain. The theory stipulates the aim of scientific study that forms the basis of its principles. It also makes seven assumptions about scientific study and defines the major participating entities (i.e., scientists, scientific knowledge and enabling technical knowledge). It extends a recent process model of scientific study into a detailed interaction model as this process model already addresses many issues of philosophy of science. The detailed interaction model of scientific study provides a common template of scientific activities for developing logical (data) models in different scientific disciplines (for physical database implementation), or alternatively for developing (domain) ontologies of different scientific disciplines. Differences between research and scientific studies are discussed, and a possible way to develop a scientific theory of scientific study is described.

An Inverted file is a commonly used index for both archival databases and free text where no updates are expected. Applications like information filtering and dynamic environments like the Internet require inverted files to be updated efficiently. Recently, extensible inverted files are proposed which can be used for fast online indexing. The effective storage allocation scheme for such inverted files uses the arrival rate to preallocate storage. In this article, this storage allocation scheme is improved by using information about both the arrival rates and their variability to predict the storage needed, as well as scaling the storage allocation by a logarithmic factor. The resultant, final storage utilization rate can be as high as 97-98% after indexing about 1.6million documents. This compares favorably with the storage utilization rate of the original arrival rate storage allocation scheme. Our evaluation shows that the retrieval time for extensible inverted file on solid state disk is on average similar to the retrieval time for in-memory extensible inverted file. When file seek time is not an issue, our scalable storage allocation enables extensible inverted files to be used as the main index on disk. Our statistical storage allocation may be applicable to novel situations where the arrival of items follows a binomial, Poisson or normal distribution.

This paper argues that scientific studies distinguish themselves from other studies by a combination of their processes, their (knowledge) elements and the roles of these elements. This is supported by constructing a process model. An illustrative example based on Newtonian mechanics shows how scientific knowledge is structured according to the process model. To distinguish scientific studies from research and scientific research, two additional process models are built for such processes. We apply these process models: (1) to argue that scientific progress should emphasize both the process of change and the content of change; (2) to chart the major stages of scientific study development; and (3) to define “science”.

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.

The growing amount of on-line data demands efficient parallel and distributed indexing mechanisms to manage large resource requirements and unpredictable system failures. Parallel and distributed indices built using commodity hardware like personal computers (PCs) can substantially save cost because PCs are produced in bulk, achieving the scale of economy. However, PCs have limited amount of random access memory (RAM) and the effective utilization of RAM for in-memory inversion is crucial. This paper presents an analytical investigation and an empirical evaluation of storage-efficient inmemory extensible inverted files, which are represented by fixed- or variable-sized linked list nodes. The size of these linked list nodes is determined by minimizing the storage wastes or maximizing storage utilization under different conditions, which lead to different storage allocation schemes. Minimizing storage wastes also reduces the number of address indirections (i.e., chaining). We evaluated our storage allocation schemes using a number of reference collections. We found that the arrival rate scheme is the best in terms of both storage utilization and the mean number of chainings per term. The final storage utilization can be over 90% in our evaluation if there is a sufficient number of documents indexed. The mean number of chainings is not large (less than 2.6 for all the reference collections). We have also showed that our best storage allocation scheme can be used for our extensible compressed inverted file. The final storage utilization of the extensible compressed inverted file can be over 90% in our evaluation provided that there is a sufficient number of documents indexed. The proposed storage allocation schemes can also be used by compressed extensible inverted files with word positions

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.

In this paper, collaborative writing is modeled as a workflow application comprising a number of activities. Each activity is assigned to a co-author to edit certain part(s) of the shared document. The order of editing is governed by a workflow schedule, which can be modified during execution. To enable concurrent editing, a data definition scheme is proposed whereby documents are transformed into the XML format for internal storage. Effectively, a hierarchical structure is superimposed on each document, allowing it to be broken down into a number of independent parts. These parts may then be separately edited in parallel. Unlike other approaches, the system supports the use of off-the-shelf editor software. Users can thus adapt to the system easily and existing documents can also be re-used rapidly. A prototype has been built which supports collaborative editing of Microsoft WordTM documents.

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.

Electronic financial news available on the Internet contains a wealth of information useful for business decision-making. However, as this information is both qualitative and existent in huge volumes, it is very inefficient to digest manually. This paper presents a prototype system called FNDS, which automatically digests financial news by extracting important information from the articles and using this information to fill in pre-defined templates. A unique feature of FNDS is that users can access the extracted information through an interactive dialogue-based interface. This has the advantage that if users do not know exactly what information is required, the system will provide feedback to help them to formulate the information requirement incrementally.

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.

Metasearch engines offer better coverage and are more fault-tolerant and expandable than single search engines. A metasearch engine is required to post queries with and obtain retrieval results from several other Internet search engines. In this paper, we describe the use of the extensible style language (XSL) to support metasearches. We show how XSL can transform a query, expressed ir. XML, into different forms for different search engines. We show how the retrieval results could be transformed into a standard format so that the metasearch engine can interpret the retrieved data, filtering the irrelevant information (e.g. advertisement). The proposed structure treats the metasearch engine and the individual search engines as separate modules with a clearly defined communication structure through XSL. Thus, the system is more extensible than coding the structure and syntactic transformation processes. It allows other new search engines to be included just through plug-and-play, requiring only that the new transformation of XML for this search engine be included in the XSL.

The author explores the use of tries to represent tries. A morphic trie image is a trie that represents a set of transformed keywords using an isomorphism h:/spl Sigma/*/spl rarr/(/spl sigma//sup q/)*. Morphic trie images using tenary alphabets achieve near optimal performances but approximation errors degrade their performances. A condition which determines whether tenary or bit tries should be used is found. Even though bit tries have better storage reduction in some cases, tenary tries access faster than bit tries. We show that the morphic trie images use less space than minimal prefix tries. If morphic trie images were compressed to form minimal prefix tries, then the total storage reduction is the product of the two. Approximation errors have no effect on minimal prefix tries.

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.

This paper reports an explorative study on organizing search results by concepts that are selected titles of Wiki pages. Because of limited display areas and for ease of navigation, two novel algorithms identify at most three general concepts, and at most five of their specific concepts for display. Our evaluation shows that the retrieval effectiveness improvement is significant at 90% confidence level using the paired student's t-test, albeit our users have no access to document titles nor to the content.

Time series data are difficult to manipulate. When they can be transformed into meaningful symbols, it becomes an easy task to query and understand them. While most recent works in time series query only concentrate on how to identify a given pattern from a time series, they do not consider the problem of identifying a suitable set of time points based upon which the time series can be segmented in accordance with a given set of pattern templates, e.g., a set of technical analysis patterns for stock analysis. On the other hand, using fixed length segmentation is only a primitive approach to such kind of problem and hence a dynamic approach is preferred so that the time series can be segmented flexibly and effectively. In view of the fact that such a segmentation problem is actually an optimization problem and evolutionary computation is an appropriate tool to solve it, we propose an evolutionary segmentation algorithm in this paper. Encouraging experimental results in segmenting the Hong Kong Hang Seng Index using 22 technical analysis patterns are reported.

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 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 is about the modification of KMP (Knuth, Morris and Pratt) algorithm for string searching of Chinese text. The difficulty is searching through a text string of single-and multi-byte characters. We showed that proper decoding of the input as sequences of characters instead of bytes is necessary. The standard KMP algorithm can easily be modified for Chinese string searching but at the worst-case time-complexity of O(3n) in terms of the number of comparisons. The finite-automaton implementation can achieve worst-case time complexity of O(2n) but constructing the transition table depends on the size of the alphabet, Σ, which is large for Chinese (for Big-5, Σ > 13,000). A mapping technique reduces the size the alphabet to at most /P/ where P is the pattern string.

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 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%).