7913579
Robustness of adaptive filtering methods in a cross-benchmark evaluation
This paper reports a cross-benchmark evaluation of regularized logistic regression (LR) and incremental Rocchio for adaptive filtering. Using four corpora from the Topic Detection and Tracking (TDT) forum and the Text Retrieval Conferences (TREC) we evaluated these methods with non-stationary topics at various granularity levels, and measured performance with different utility settings. We found that LR performs strongly and robustly in optimizing T11SU (a TREC utility function) while Rocchio is better for optimizing Ctrk (the TDT tracking cost), a high-recall oriented objective function. Using systematic cross-corpus parameter optimization with both methods, we obtained the best results ever reported on TDT5, TREC10 and TREC11. Relevance feedback on a small portion (0.05~0.2%) of the TDT5 test documents yielded significant performance improvements, measuring up to a 54% reduction in Ctrk and a 20.9% increase in T11SU (with b=0.1), compared to the results of the top-performing system in TDT2004 without relevance feedback information.
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.
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.
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.
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.
16965968
Performance of Full Text Search in Structured and Unstructured Peer-to-Peer Systems
While structured P2P systems (such as DHTs) are often regarded as an improvement over unstructured P2P systems (such as super-peer networks) in terms of routing efficiency, it is not clear which architecture is better for full text search. This paper provides a quantitative comparison of full text keyword search in structured and unstructured P2P systems. We examine three techniques (and optimizations to those techniques) proposed in the literature: using a DHT along with inverted lists and Bloom filters; using a super-peer network; and using a random walk over an unstructured network. We use real Web documents and user queries to measure the cost for both document publishing and query processing, in terms of bandwidth and response time. Our results show that all three techniques use roughly the same bandwidth to process queries (with the super-peer technique having a slight edge). The structured network provides the best response time (30 percent better than a super-peer network), but has a high cost of document publishing, using six times as much bandwidth as the super-peer system. The random walk technique requires no publishing, but has a very long response time unless multiple random walks operate in parallel.
5645902
On designing incentive-compatible routing and forwarding protocols in wireless ad-hoc networks: an integrated approach using game theoretical and cryptographic techniques
In many applications, wireless ad-hoc networks are formed by devices belonging to independent users. Therefore, a challenging problem is how to provide incentives to stimulate cooperation. In this paper, we study ad-hoc games---the routing and packet forwarding games in wireless ad-hoc networks. Unlike previous work which focuses either on routing or on forwarding, this paper investigates both routing and forwarding. We first uncover an impossibility result---there does not exist a protocol such that following the protocol to always forward others' traffic is a dominant action. Then we define a novel solution concept called cooperation-optimal protocols. We present Corsac, a cooperation-optimal protocol consisting of a routing protocol and a forwarding protocol. The routing protocol of Corsac integrates VCG with a novel cryptographic technique to address the challenge in wireless ad-hoc networks that a link's cost (ie, its type) is determined by two nodes together. Corsac also applies efficient cryptographic techniques to design a forwarding protocol to enforce the routing decision, such that fulfilling the routing decision is the optimal action of each node in the sense that it brings the maximum utility to the node. Additionally, we extend our framework to a practical radio propagation model where a transmission is successful with a probability. We evaluate our protocols using simulations. Our evaluations demonstrate that our protocols provide incentives for nodes to forward packets.
14899560
Dealing with Predictive-but-Unpredictable Attributes in Noisy Data Sources
Attribute noise can affect classification learning. Previous work in handling attribute noise has focused on those predictable attributes that can be predicted by the class and other attributes. However, attributes can often be predictive but unpredictable. Being predictive, they are essential to classification learning and it is important to handle their noise. Being unpredictable, they require strategies different from those of predictable attributes. This paper presents a study on identifying, cleansing and measuring noise for predictive-but-unpredictable attributes. New strategies are accordingly proposed. Both theoretical analysis and empirical evidence suggest that these strategies are more effective and more efficient than previous alternatives.
4910050
Empirical Study on Benchmarking Software Development Tasks
Benchmarking is one of the most important methods to learn the best practices for software process improvement. However, in current software process context, benchmarking is mainly for projects rather than software development tasks. Can we benchmark software development tasks? If so, how to? Moreover, benchmarking software development tasks has to deal with multivariate and variable return to scale (VRS). This paper reports practical experience of benchmarking software development tasks under multivariate and VRS constraints using Data Envelopment Analysis (DEA). The analysis of experience data in Institute of Software, Chinese Academy of Sciences (ISCAS) indicates that the ideas and techniques of benchmarking software projects can be deployed at the software development task level. Moreover, results also show that DEA VRS model allows the developers to gain new insight about how to identify the relatively efficient tasks as the task performance benchmark and how to establish different reference sets for each relatively inefficient task under multivariate and VRS constraints. We thus recommend DEA VRS model be used as the default technique for appropriately benchmarking software development tasks. Our results are beneficial to software process improvement. To the best of our knowledge, we believe that it is the first time to report such comprehensive and repeatable results of benchmarking software development tasks using DEA.
5522263
HybMig: A Hybrid Approach to Dynamic Plan Migration for Continuous Queries
In data stream environments, the initial plan of a long-running query may gradually become inefficient due to changes of the data characteristics. In this case, the query optimizer generates a more efficient plan based on the current statistics. The online transition from the old to the new plan is called dynamic plan migration. In addition to correctness, an effective technique for dynamic plan migration should achieve the following objectives: 1) minimize the memory and CPU overhead of the migration, 2) reduce the duration of the transition, and 3) maintain a steady output rate. The only known solutions for this problem are the moving states (MS) and parallel track (PT) strategies, which have some serious shortcomings related to the above objectives. Motivated by these shortcomings, we first propose HybMig, which combines the merits of MS and PT and outperforms both in every aspect. As a second step, we extend PT, MS, and HybMig to the general problem of migration, where both the new and the old plans are treated as black boxes