3342722
A study of thresholding strategies for text categorization
Thresholding strategies in automated text categorization are an underexplored area of research. This paper presents an examination of the effect of thresholding strategies on the performance of a classifier under various conditions. Using k-Nearest Neighbor (kNN) as the classifier and five evaluation benchmark collections as the testbets, three common thresholding methods were investigated, including rank-based thresholding (RCut), proportion-based assignments (PCut) and score-based local optimization (SCut); in addition, new variants of these methods are proposed to overcome significant problems in the existing approaches. Experimental results show that the choice of thresholding strategy can significantly influence the performance of kNN, and that the ``optimal'' strategy may vary by application. SCut is potentially better for fine-tuning but risks overfitting. PCut copes better with rare categories and exhibits a smoother trade-off in recall versus precision, but is not suitable for online decision making. RCut is most natural for online response but is too coarse-grained for global or local optimization. RTCut, a new method combining the strength of category ranking and scoring, outperforms both PCut and RCut significantly.
7098682
High-performing feature selection for text classification
This paper reports a controlled study on a large number of filter feature selection methods for text classification. Over 100 variants of five major feature selection criteria were examined using four well-known classification algorithms: a Naive Bayesian (NB) approach, a Rocchio-style classifier, a k-nearest neighbor (kNN) method and a Support Vector Machine (SVM) system. Two benchmark collections were chosen as the testbeds: Reuters-21578 and small portion of Reuters Corpus Version 1 (RCV1), making the new results comparable to published results. We found that feature selection methods based on chi2 statistics consistently outperformed those based on other criteria (including information gain) for all four classifiers and both data collections, and that a further increase in performance was obtained by combining uncorrelated and high-performing feature selection methods.The results we obtained using only 3% of the available features are among the best reported, including results obtained with the full feature set.
1743726
Hypertext Categorization using Hyperlink Patterns and Meta Data
Hypertext poses new text classi cation research challenges as hyperlinks, content of linked documents, and meta data about related web sites all provide richer sources of information for hypertext classi cation that are not available in traditional text classi cation. We investigate the use of such information for representing web sites, and the e ectiveness of di erent classi ers (Naive Bayes, Nearest Neighbor, and Foil) in exploiting those representations. We nd that using words in web pages alone often yields suboptimal performance of classi ers, compared to exploiting additional sources of information beyond document content. On the other hand, we also observe that linked pages can be more harmful than helpful when the linked neighborhoods are highly \noisy" and that links have to be used in a careful manner. More importantly, our investigation suggests that meta data which is often available, or can be acquired using Information Extraction techniques, can be extremely useful for improving classi cation accuracy. Finally, the relative performance of the di erent classi ers being tested gives us insights into the strengths and limitations of our algorithms for hypertext classi cation.
10555290
From Lasso regression to Feature vector machine
Lasso regression tends to assign zero weights to most irrelevant or redundant features, and hence is a promising technique for feature selection. Its limitation, however, is that it only offers solutions to linear models. Kernel machines with feature scaling techniques have been studied for feature selection with non-linear models. However, such approaches require to solve hard non-convex optimization problems. This paper proposes a new approach named the Feature Vector Machine (FVM). It reformulates the standard Lasso regression into a form isomorphic to SVM, and this form can be easily extended for feature selection with non-linear models by introducing kernels defined on feature vectors. FVM generates sparse solutions in the nonlinear feature space and it is much more tractable compared to feature scaling kernel machines. Our experiments with FVM on simulated data show encouraging results in identifying the small number of dominating features that are non-linearly correlated to the response, a task the standard Lasso fails to complete.
14181364
Probabilistic score estimation with piecewise logistic regression
Well-calibrated probabilities are necessary in many applications like probabilistic frameworks or cost-sensitive tasks. Based on previous success of asymmetric Laplace method in calibrating text classifiers' scores, we propose to use piecewise logistic regression, which is a simple extension of standard logistic regression, as an alternative method in the discriminative family. We show that both methods have the flexibility to be piecewise linear functions in log-odds, but they are based on quite different assumptions. We evaluated asymmetric Laplace method, piecewise logistic regression and standard logistic regression over standard text categorization collections (Reuters-21578 and TRECAP) with three classifiers (SVM, Naive Bayes and Logistic Regression Classifier), and observed that piecewise logistic regression performs significantly better than the other two methods in the log-loss metric.
8555900
Unsupervised Learning of Arabic Stemming Using a Parallel Corpus
This paper presents an unsupervised learning approach to building a non-English (Arabic) stemmer. The stemming model is based on statistical machine translation and it uses an English stemmer and a small (10 K sentences) parallel corpus as its sole training resources. No parallel text is needed after the training phase. Monolingual, unannotated text can be used to further improve the stemmer by allowing it to adapt to a desired domain or genre. Examples and results will be given for Arabic, but the approach is applicable to any language that needs affix removal. Our resource-frugal approach results in 87.5% agreement with a state of the art, proprietary Arabic stemmer built using rules, affix lists, and human annotated text, in addition to an unsupervised component. Task-based evaluation using Arabic information retrieval indicates an improvement of 22-38% in average precision over unstemmed text, and 96% of the performance of the proprietary stemmer above.
2183
Path-independent load balancing with unreliable machines
We consider algorithms for load balancing on unreliable machines. The objective is to optimize the two criteria of minimizing the makespan and minimizing job reassignments in response to machine failures. We assume that the set of jobs is known in advance but that the pattern of machine failures is unpredictable. Motivated by the requirements of BGP routing, we consider path-independent algorithms, with the property that the job assignment is completely determined by the subset of available machines and not the previous history of the assignments. We examine first the question of performance measurement of path-independent load-balancing algorithms, giving the measure of makespan and the normalized measure of reassignments cost. We then describe two classes of algorithms for optimizing these measures against an oblivious adversary for identical machines. The first, based on independent random assignments, gives expected reassignment costs within a factor of 2 of optimal and gives a makespan within a factor of O (log m/log log m) of optimal with high probability, for unknown job sizes. The second, in which jobs are first grouped into bins and at most one bin is assigned to each machine, gives constant-factor ratios on both reassignment cost and makespan, for known job sizes. Several open problems are discussed.
207726294
Evolving better population distribution and exploration in evolutionary multi-objective optimization
The aim of multi-objective evolutionary optimization is to minimize the distance between the solution set and the true Pareto front, to distribute the solutions evenly and to maximize the spread of solution set. This paper addresses these issues by presenting two features that enhance the optimization ability of multi-objective evolutionary algorithms. The first feature is a variant of the mutation operator that adapts the mutation rate along the evolution process to maintain a balance between the introduction of diversity and local fine-tuning. In addition, this adaptive mutation operator adopts a new approach to strike a compromise between the preservation and disruption of genetic information. The second feature is an enhanced exploration strategy that encourages the exploration towards less populated areas and hence achieves better discovery of gaps in the generated front. The strategy also preserves non-dominated solutions in the evolving population to achieve a good convergence for the optimization. Comparative studies of some well-known diversity operators, mutation operators and multi-objective evolutionary algorithms are performed on different benchmark problems, which illustrate the effectiveness and efficiency of the proposed features.
4907231
Temporal Dependency for Dynamic Verification of Fixed-Date Constraints in Grid Workflow Systems
Grid workflow systems aim to support large-scale complex e-science and e-business processes. Due to the complexity of these kinds of processes, to control the execution of them in terms of time in the grid workflow execution environments, multiple fixed-date temporal constraints often need to be set simultaneously. Hence the dependency problem between them must be considered and emphasised, which affects the verification effectiveness and efficiency of the fixed-date temporal constraints. However, current relevant workflow verification works do not take into consideration this dependency. Therefore, in this paper, we explore it in depth and analyse its impact on the verification of the fixed-date temporal constraints. Furthermore, based on the temporal dependency, we develop some new temporal verification methods and algorithms. The comparison and evaluation show that these new methods and algorithms make the verification more effective and efficient. All these analyses, new methods and algorithms further strengthen the grid workflow time management.
45091923
An evolutionary programming algorithm for continuous global optimization
Evolutionary computations are very effective at performing global search (in probability), however, the speed of convergence could be slow. This paper presents an evolutionary programming algorithm combined with macro-mutation (MM), local linear bisection search (LBS) and crossover operators for global optimization. The MM operator is designed to explore the whole search space and the LBS operator to exploit the neighborhood of the solution. Simulated annealing is adopted to prevent premature convergence. The performance of the proposed algorithm is assessed by numerical experiments on 12 benchmark problems. Combined with MM, the effectiveness of various local search operators is also studied.
2958357
An Architecture and the Related Mechanisms for Web-based Global Cooperative Teamwork Support
Given the exposure of the Internet and the Web, there is a significant impact on Web-based cooperative teamwork support which can be beneficial to many teamwork managers and normal team members who may be either computing or non-computing professionals. In this paper, we focus on our research into a more effective architecture for Web-based teamwork automation support and its corresponding innovative mechanisms for various perspectives including visual process modelling for teamwork managers and process enactment for team members in an asynchronous and synchronous manner. Our research prototype is implemented in Java and data repository used can be an object-oriented or relational database.