CiteULike: AbnerCYH's Huang

Using AUC and accuracy in evaluating learning algorithms

Jin Huang — 2008-05-09T12:01:38-00:00

Knowledge and Data Engineering, IEEE Transactions on, Vol. 17, No. 3. (2005), pp. 299-310.

The area under the ROC (receiver operating characteristics) curve, or simply AUC, has been traditionally used in medical diagnosis since the 1970s. It has recently been proposed as an alternative single-number measure for evaluating the predictive ability of learning algorithms. However, no formal arguments were given as to why AUC should be preferred over accuracy. We establish formal criteria for comparing two different measures for learning algorithms and we show theoretically and empirically that AUC is a better measure (defined precisely) than accuracy. We then reevaluate well-established claims in machine learning based on accuracy using AUC and obtain interesting and surprising new results. For example, it has been well-established and accepted that Naive Bayes and decision trees are very similar in predictive accuracy. We show, however, that Naive Bayes is significantly better than decision trees in AUC. The conclusions drawn in this paper may make a significant impact on machine learning and data mining applications.

Efficient transposition algorithms for large matrices

SD Kaushik — 2008-04-03T17:49:25-00:00

(1993), pp. 656-665.

A Primal-Dual Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions

Li-Sha Huang — 2008-01-05T15:53:58-00:00

Algorithmica

Abstract We develop an algorithm for computing the equilibrium price in the Fisher’s exchange market model with logarithmic utility functions. The algorithm is proved to converge to the equilibrium price in finite time and performs well in experimental tests.

Fixed-Parameter Approximation: Conceptual Framework and Approximability Results

Liming Cai — 2007-11-13T17:12:09-00:00

Parameterized and Exact Computation (2006), pp. 96-108.

The notion of fixed-parameter approximation is introduced to investigate the approximability of optimization problems within the framework of fixed-parameter computation. This work partially aims at enhancing the world of fixed-parameter computation in parallel with the conventional theory of computation that includes both exact and approximate computations. In particular, it is proved that fixed-parameter approximability is closely related to the approximation of small-cost solutions in polynomial time. It is also demonstrated that many fixed-parameter intractable problems are not fixed-parameter approximable. On the other hand, fixed-parameter approximation appears to be a viable approach to solving some inapproximable yet important optimization problems. For instance, all problems in the class MAX SNP admit fixed-parameter approximation schemes in time O(2O((1– ε/O(1))k)p(n)) for any small ε> 0.

Parameterized complexity and polynomial-time approximation schemes

Xiuzhen Huang — 2007-11-13T10:33:37-00:00

(December 2004)

According to the theory of NPcompleteness, many problems that have important realworld applications are NPhard. This excludes the possibility of solving them in polynomial time unless P=NP. A number of approaches have been proposed in dealing with NPhard problems, among them are approximation algorithms and parameterized algorithms. The study of approximation algorithms tries to ﬁnd good enough solutions instead of optimal solutions in polynomial time, while parameterized algorithms try to give exact solutions when a natural parameter is small. In this thesis, we study the structural properties of parameterized computation and approximation algorithms for NP optimization problems. In particular, we investigate the relationship between parameterized complexity and polynomialtime approximation scheme (PTAS) for NP optimization problems. We give nice characterizations for two important subclasses in PTAS: Fully Polynomial Time Approximation Scheme (FPTAS) and Effcient Polynomial Time Approximation Scheme (EPTAS), using the theory of parameterized complexity. Our characterization of the class FPTAS has its advantages over the former characterizations, and our characterization of EPTAS is the ﬁrst systematic investigation of this new but important approximation class. We develop new techniques to derive strong computational lower bounds for certain parameterized problems based on the theory of parameterized complexity. For example, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the clique problem could not be solved in time O(f (k)no(k)) for any function f . This lower bound matches the upper bound of the trivial algorithm that simply enumerates and checks all subsets of k vertices in the given graph of n vertices. We then extend our techniques to derive computational lower bounds for PTAS and EPTAS algorithms of NP optimization problems. We prove that certain NP optimization problems with known PTAS algorithms have no PTAS algorithms of running time O(f (1/Epsilon)no(1/Epsilon)) for any function f . Therefore, for these NP optimization problems, although theoretically they can be approximated in polynomial time to an arbitrarily small error bound Epsilon, they have no practically effective approximation algorithms for small error bound Epsilon. To our knowledge, this is the ﬁrst time such lower bound results have been derived for PTAS algorithms. This seems to open a new direction for the study of computational lower bounds on the approximability of NP optimization problems.

Parameterized Complexity and Biopolymer Sequence Comparison

Liming Cai — 2007-11-10T18:57:42-00:00

The Computer Journal, Vol. 51, No. 3. (27 June 2007), bxm035.

The paper surveys parameterized algorithms and complexities for computational tasks on biopolymer sequences, including the problems of longest common subsequence, shortest common supersequence, pairwise sequence alignment, multiple sequencing alignment, structure-sequence alignment and structure-structure alignment. Algorithm techniques, built on the structural-unit level as well as on the residue level, are discussed. 10.1093/comjnl/bxm035

Polynomial time approximation schemes and parameterized complexity

Jianer Chen — 2007-11-08T18:10:21-00:00

Discrete Appl. Math., Vol. 155, No. 2. (January 2007), pp. 180-193.

Minimum connected dominating sets and maximal independent sets in unit disk graphs

Weili Wu — 2007-10-09T16:13:52-00:00

Theoretical Computer Science, Vol. 352, No. 1-3. (7 March 2006), pp. 1-7.

In ad hoc wireless networks, a connected dominating set can be used as a virtual backbone to improve the performance. Many constructions for approximating the minimum connected dominating set are based on the construction of a maximal independent set. The relation between the size mis(G) of a maximum independent set and the size cds(G) of a minimum connected dominating set in the same graph G plays an important role in establishing the performance ratio of those approximation algorithms. Previously, it is known that mis(G)[less-than-or-equals, slant]4[middle dot]cds(G)+1 for all unit disk graphs G. In this paper, we improve it by showing mis(G)[less-than-or-equals, slant]3.8[middle dot]cds(G)+1.2.