CiteULike: AbnerCYH's information

An introduction to ROC analysis

Tom Fawcett — 2006-08-29T01:24:20-00:00

Pattern Recognition Letters, Vol. 27, No. 8. (June 2006), pp. 861-874.

Receiver operating characteristics (ROC) graphs are useful for organizing classifiers and visualizing their performance. ROC graphs are commonly used in medical decision making, and in recent years have been used increasingly in machine learning and data mining research. Although ROC graphs are apparently simple, there are some common misconceptions and pitfalls when using them in practice. The purpose of this article is to serve as an introduction to ROC graphs and as a guide for using them in research.

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.

The use of receiver operating characteristic curves in biomedical informatics

Thomas Lasko — 2006-01-14T16:08:59-00:00

Journal of Biomedical Informatics, Vol. 38, No. 5. (October 2005), pp. 404-415.

Receiver operating characteristic (ROC) curves are frequently used in biomedical informatics research to evaluate classification and prediction models for decision support, diagnosis, and prognosis. ROC analysis investigates the accuracy of a model's ability to separate positive from negative cases (such as predicting the presence or absence of disease), and the results are independent of the prevalence of positive cases in the study population. It is especially useful in evaluating predictive models or other tests that produce output values over a continuous range, since it captures the trade-off between sensitivity and specificity over that range. There are many ways to conduct an ROC analysis. The best approach depends on the experiment; an inappropriate approach can easily lead to incorrect conclusions. In this article, we review the basic concepts of ROC analysis, illustrate their use with sample calculations, make recommendations drawn from the literature, and list readily available software.

Information measures, effective complexity, and total information

Murray Gell-Mann — 2007-12-17T18:36:29-00:00

Complexity, Vol. 2, No. 1. (1996), pp. 44-52.

This article defines the concept of an information measure and shows how common information measures such as entropy, Shannon information, and algorithmic information content can be combined to solve problems of characterization, inference, and learning for complex systems. Particularly useful quantities are the effective complexity, which is roughly the length of a compact description of the identified regularities of an entity, and total information, which is effective complexity plus an entropy term that measures the information required to describe the random aspects of the entity. Mathematical definitions are given for both quantities and some applications are discussed. In particular, it is pointed out that if one compares different sets of identified regularities of an entity, the ?best? set minimizes the total information, and then, subject to that constraint, minimizes the effective complexity; the resulting effective complexity is then in many respects independent of the observer. © 1996 John Wiley & Sons, Inc.

Pattern Recognition with Fuzzy Objective Function Algorithms

James Bezdek — 2008-04-02T05:09:59-00:00

(1981)

Aspects of discrete mathematics and probability in the theory of machine learning

Martin Anthony — 2008-02-27T02:41:05-00:00

Discrete Applied Mathematics, Vol. 156, No. 6. (15 March 2008), pp. 883-902.

This paper discusses the applications of certain combinatorial and probabilistic techniques to the analysis of machine learning. Probabilistic models of learning initially addressed binary classification (or pattern classification). Subsequently, analysis was extended to regression problems, and to classification problems in which the classification is achieved by using real-valued functions (where the concept of a large margin has proven useful). Another development, important in obtaining more applicable models, has been the derivation of data-dependent bounds. Here, we discuss some of the key probabilistic and combinatorial techniques and results, focusing on those of most relevance to researchers in discrete applied mathematics.

Adaptive sorting: an information theoretic perspective

Amr Elmasry — 2008-02-08T21:53:27-00:00

Acta Informatica, Vol. 45, No. 1. (19 February 2008), pp. 33-42.

Abstract We present two algorithms that are near optimal with respect to the number of inversions present in the input. One of the algorithms is a variation of insertion sort, and the other is a variation of merge sort. The number of comparisons performed by our algorithms, on an input sequence of length n that has I inversions, is at most $$n\, log_2 (\fracIn + 1) + O(n)$$ . Moreover, both algorithms have implementations that run in time $$O(n\, log_2 (\fracIn + 1)\,+\,n)$$ . All previously published algorithms require at least $$cn\, log_2 (\fracIn + 1)$$ comparisons for some c > 1.

An information-theoretic framework for resolving community structure in complex networks

Martin Rosvall — 2007-05-01T17:50:37-00:00

PNAS, Vol. 104, No. 18. (1 May 2007), pp. 7327-7331.

To understand the structure of a large-scale biological, social, or technological network, it can be helpful to decompose the network into smaller subunits or modules. In this article, we develop an information-theoretic foundation for the concept of modularity in networks. We identify the modules of which the network is composed by finding an optimal compression of its topology, capitalizing on regularities in its structure. We explain the advantages of this approach and illustrate them by partitioning a number of real-world and model networks. 10.1073/pnas.0611034104

Topological permutation entropy

Jose Amigo — 2007-11-26T13:38:44-00:00

Physica D: Nonlinear Phenomena, Vol. 231, No. 2. (15 July 2007), pp. 137-142.

Permutation entropy quantifies the diversity of possible ordering of the successively observed values a random or deterministic system can take, just as Shannon entropy quantifies the diversity of the values themselves. When the observable or state variable has a natural order relation, making permutation entropy possible to compute, then the asymptotic rate of growth in permutation entropy with word length forms an alternative means of describing the intrinsic entropy rate of a source. Herein, extending a previous result on metric entropy rate, we show that the topological permutation entropy rate for expansive maps equals the conventional topological entropy rate familiar from symbolic dynamics. This result is not limited to one-dimensional maps.

The mutual information: Detecting and evaluating dependencies between variables

R Steuer — 2007-11-26T13:36:33-00:00

Bioinformatics, Vol. 18 (2002), pp. S231-S240.

Motivation: Clustering co-expressed genes usually requires the definition of `distance' or `similarity' between measured datasets, the most common choices being Pearson correlation or Euclidean distance. With the size of available datasets steadily increasing, it has become feasible to consider other, more general, definitions as well. One alternative, based on information theory, is the mutual information, providing a general measure of dependencies between variables. While the use of mutual information in cluster analysis and visualization of large-scale gene expression data has been suggested previously, the earlier studies did not focus on comparing different algorithms to estimate the mutual information from finite data. Results: Here we describe and review several approaches to estimate the mutual information from finite datasets. Our findings show that the algorithms used so far may be quite substantially improved upon. In particular when dealing with small datasets, finite sample effects and other sources of potentially misleading results have to be taken into account.

Entropy of capacities on lattices and set systems

Aoi Honda — 2007-11-14T08:37:40-00:00

(13 Nov 2007)

We propose a definition for the entropy of capacities defined on lattices. Classical capacities are monotone set functions and can be seen as a generalization of probability measures. Capacities on lattices address the general case where the family of subsets is not necessarily the Boolean lattice of all subsets. Our definition encompasses the classical definition of Shannon for probability measures, as well as the entropy of Marichal defined for classical capacities. Some properties and examples are given.

Infeasibility of Instance Compression and Succinct PCPs for NP

Lance Fortnow — 2007-11-08T17:00:38-00:00

No. TR07-096. (2007)

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there is a polynomial-time computable function $f$ and a set $A$ such that for each instance $x$ of $L$, $f(x)$ is of size polynomial in the it witness size of $x$, and $f$ reduces $L$ to $A$. We prove that SAT is not instance compressible unless NP is contained in coNP/poly, and the Polynomial Hierarchy collapses. This result settles an open problem posed by [Harnik-Naor06] and [Downey07], and has a number of implications: 1. A number of parametric NP problems, including SAT, Clique, DominatingSet and IntegerProgramming, are not polynomially kernelizable unless NP is contained in coNP/poly. 2. SAT does not have "succinct PCPs", i.e., PCPs of size polynomial in the number of variables, unless NP is contained in coNP/poly. 3. An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is inviable in its present form. 4. (Burhman) There are no sub-exponential size complete sets for NP or coNP unless NP is contained in coNP/poly.

A Group Theoretic Model for Information

Hua Li — 2007-10-09T19:55:15-00:00

(5 Oct 2007)

In this paper we formalize the notions of information elements and information lattices, first proposed by Shannon. Exploiting this formalization, we identify a comprehensive parallelism between information lattices and subgroup lattices. Qualitatively, we demonstrate isomorphisms between information lattices and subgroup lattices. Quantitatively, we establish a decisive approximation relation between the entropy structures of information lattices and the log-index structures of the corresponding subgroup lattices. This approximation extends the approximation for joint entropies carried out previously by Chan and Yeung. As a consequence of our approximation result, we show that any continuous law holds in general for the entropies of information elements if and only if the same law holds in general for the log-indices of subgroups. As an application, by constructing subgroup counterexamples we find surprisingly that common information, unlike joint information, obeys neither the submodularity nor the supermodularity law. We emphasize that the notion of information elements is conceptually significant--formalizing it helps to reveal the deep connection between information theory and group theory. The parallelism established in this paper admits an appealing group-action explanation and provides useful insights into the intrinsic structure among information elements from a group-theoretic perspective.

Finite Model Theory and Descriptive Complexity

E Grädel — 2006-09-30T14:30:13-00:00

(2003)

This is a survey on the relationship between logical definability and computational complexity on finite structures. Particular emphasis is given to game-based evaluation algorithms for various logical formalisms and to logics capturing complexity classes.

Metafinite Model Theory

Erich Gradel — 2006-09-30T14:38:06-00:00

Information and Computation, Vol. 140, No. 1. (1998), pp. 26-81.

Motivated by computer science challenges, we suggest to extend the approach and methods of finite model theory beyond finite structures. We study definability issues and their relation to complexity on metafinite structures which typically consist of (i) a primary part, which is a finite structure, (ii) a secondary part, which is a (usually infinite) structure that can be viewed as a structured domain of numerical objects, and (iii) a set of "weight" functions from the first part into the...

Combining Pattern Classifiers: Methods and Algorithms

Ludmila Kuncheva — 2006-09-02T17:12:18-00:00

(01 July 2004)

Covering pattern classification methods, Combining Classifiers: Ideas and Methods focuses on the important and widely studied issue of how to combine several classifiers together in order to achieve improved recognition performance. It is one of the first books to provide unified, coherent, and expansive coverage of the topic and as such will be welcomed by those involved in the area. With case studies that bring the text alive and demonstrate 'real-world' applications it is destined to become essential reading. Covering pattern classification methods, Combining Classifiers: Ideas and Methods focuses on the important and widely studied issue of how to combine several classifiers together in order to achieve improved recognition performance. It is one of the first books to provide unified, coherent, and expansive coverage of the topic and as such will be welcomed by those involved in the area. With case studies that bring the text alive and demonstrate 'real-world' applications it is destined to become essential reading.

Average-case analysis of QuickSort and Binary Insertion Tree height using incompressibility

Brendan Lucier — 2007-08-09T07:46:10-00:00

Information Processing Letters, Vol. 103, No. 2. (16 July 2007), pp. 45-51.

We study the Kolmogorov complexity of a Binary Insertion Tree, and present a succinct encoding scheme for Binary Insertion Trees produced from incompressible permutations. Based on the encoding scheme, we obtain a simple incompressibility argument that yields an asymptotic analysis of the average height of a Binary Insertion Tree. This argument further implies that the QuickSort algorithm sorts a permutation of n elements in [Theta](nlgn) comparisons on average.

Optimal spaced seeds for faster approximate string matching

Martin Farach-Colton — 2007-08-03T16:57:32-00:00

Journal of Computer and System Sciences, Vol. 73, No. 7. (November 2007), pp. 1035-1044.

Filtering is a standard technique for fast approximate string matching in practice. In filtering, a quick first step is used to rule out almost all positions of a text as possible starting positions for a pattern. Typically this step consists of finding the exact matches of small parts of the pattern. In the followup step, a slow method is used to verify or eliminate each remaining position. The running time of such a method depends largely on the quality of the filtering step, as measured by its false positives rate. The quality of such a method depends on the number of true matches that it misses, that is, on its false negative rate. A spaced seed is a recently introduced type of filter pattern that allows gaps (i.e. do not cares) in the small sub-pattern to be searched for. Spaced seeds promise to yield a much lower false positives rate, and thus have been extensively studied, though heretofore only heuristically or statistically. In this paper, we show how to design almost optimal spaced seeds that yield no false negatives.

Combinatorial Group Testing and Its Applications (Applied Mathematics)

Ding-Zhu Du — 2007-07-26T11:37:00-00:00

(01 January 2000)

Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes

David Eppstein — 2006-12-14T06:42:54-00:00

(18 May 2005)

We study practically efficient methods for performing combinatorial group testing. We present efficient non-adaptive and two-stage combinatorial group testing algorithms, which identify the at most d items out of a given set of n items that are defective, using fewer tests for all practical set sizes. For example, our two-stage algorithm matches the information theoretic lower bound for the number of tests in a combinatorial group testing regimen.

Analysis of Sorting Algorithms by Kolmogorov Complexity

Survey Vit — 2006-09-19T15:03:20-00:00

Recently, many results on the computational complexity of sorting algorithms were obtained using Kolmogorov complexity (the incompressibility method). Especially, the usually hard average-case analysis is ammenable to this method. Here we survey such results about Bubblesort, Heapsort, Shellsort, Dobosiewicz-sort, Shakersort, and sorting with stacks and queues in sequential or parallel mode. Especially in the case of Shellsort the uses of Kolmogorov complexity surprisingly easily resolved...

Entropy as a fixed point

Keye Martin — 2007-03-16T09:52:39-00:00

Theor. Comput. Sci., Vol. 350, No. 2. (February 2006), pp. 292-324.

We study complexity and information and introduce the idea that while complexity is relative to a given class of processes, information is process independent: Information is complexity relative to the class of all conceivable processes. In essence, the idea is that information is an extension of the concept ‘algorithmic complexity’ from a class of desirable and concrete processes, such as those represented by binary decision trees, to a class more general that can only in pragmatic terms be regarded as existing in the conception. It is then precisely the fact that information is defined relative to such a large class of processes that it becomes an effective tool for analyzing phenomena in a wide range of disciplines. We test these ideas on the complexity of classical states. A domain is used to specify the class of processes, and both qualitative and quantitative notions of complexity for classical states emerge. The resulting theory is used to give new proofs of fundamental results from classical information theory, to give a new characterization of entropy in quantum mechanics, to establish a rigorous connection between entanglement transformation and computation, and to derive lower bounds on algorithmic complexity. All of this is a consequence of the setting which gives rise to the fixed point theorem: The least fixed point of the copying operator above complexity is information.

Mining the Space of Graph Properties

Glen Jeh — 2005-09-30T09:24:40-00:00

Existing data mining algorithms on graphs look for nodes satisfying specific properties, such as specific notions of structural similarity or specific measures of link-based importance. While such analyses for predetermined properties can be effective in well-understood domains, sometimes identifying an appropriate property for analysis can be a challenge, and focusing on a single property may neglect other important aspects of the data. In this paper, we develop a foundation for...

Algorithmic Information Theory: a brief non-technical guide to the field

Marcus Hutter — 2007-03-07T05:43:07-00:00

Scholarpedia (6 Mar 2007)

This article is a brief guide to the field of algorithmic information theory (AIT), its underlying philosophy, and the most important concepts. AIT arises by mixing information theory and computation theory to obtain an objective and absolute notion of information in an individual object, and in so doing gives rise to an objective and robust notion of randomness of individual objects. This is in contrast to classical information theory that is based on random variables and communication, and has no bearing on information and randomness of individual objects. After a brief overview, the major subfields, applications, history, and a map of the field are presented.

Entropy of cellular automata

Tom Meyerovitch — 2007-03-07T15:59:07-00:00

(6 Mar 2007)

Let $X=S^G$ where $G$ is a countable group and $S$ is a finite set. A cellular automaton (CA) is an endomorphism $T : X \to X$ (continuous, commuting with the action of $G$). Shereshevsky (1993) proved that for $G=Z^d$ with $d>1$ no CA can be forward expansive, raising the following conjecture: For $G=Z^d$, $d>1$ the topological entropy of any CA is either zero or infinite. Morris and Ward (1998), proved this for linear CA's, leaving the original conjecture open. We show that this conjecture is false, proving that for any $d$ there exist a $d$-dimensional CA with finite, nonzero topological entropy. We also discuss a measure-theoretic counterpart of this question for measure-preserving CA's. Our main tool is a construction of a CA by Kari (1994).