OpenRaiser/Intern-Atlas huggingface dataset:
Committee-Based Sample Selection for Probabilistic Classifiers
Venue: arXiv cs.AI 2011
Year: 2011

In many real-world learning tasks, it is expensive to acquire a sufficient number of labeled examples for training. This paper investigates methods for reducing annotation cost by `sample selection'. In this approach, during training the learning program examines many unlabeled examples and selects for labeling only those that are most informative at each stage. This avoids redundantly labeling examples that contribute little new information. Our work follows on previous research on Query By Committee, extending the committee-based paradigm to the context of probabilistic classification. We describe a family of empirical methods for committee-based sample selection in probabilistic classification models, which evaluate the informativeness of an example by measuring the degree of disagreement between several model variants. These variants (the committee) are drawn randomly from a probability distribution conditioned by the training set labeled so far. The method was applied to the real-world natural language processing task of stochastic part-of-speech tagging. We find that all variants of the method achieve a significant reduction in annotation cost, although their computational efficiency differs. In particular, the simplest variant, a two member committee with no parameters to tune, gives excellent results. We also show that sample selection yields a significant reduction in the size of the model used by the tagger.
Evolutionary Algorithms for Reinforcement Learning
Venue: arXiv cs.LG 2011
Year: 2011

There are two distinct approaches to solving reinforcement learning problems, namely, searching in value function space and searching in policy space. Temporal difference methods and evolutionary algorithms are well-known examples of these approaches. Kaelbling, Littman and Moore recently provided an informative survey of temporal difference methods. This article focuses on the application of evolutionary algorithms to the reinforcement learning problem, emphasizing alternative policy representations, credit assignment methods, and problem-specific genetic operators. Strengths and weaknesses of the evolutionary approach to reinforcement learning are presented, along with a survey of representative applications.
Space Efficiency of Propositional Knowledge Representation Formalisms
Venue: arXiv cs.AI 2011
Year: 2011

We investigate the space efficiency of a Propositional Knowledge Representation (PKR) formalism. Intuitively, the space efficiency of a formalism F in representing a certain piece of knowledge A, is the size of the shortest formula of F that represents A. In this paper we assume that knowledge is either a set of propositional interpretations (models) or a set of propositional formulae (theorems). We provide a formal way of talking about the relative ability of PKR formalisms to compactly represent a set of models or a set of theorems. We introduce two new compactness measures, the corresponding classes, and show that the relative space efficiency of a PKR formalism in representing models/theorems is directly related to such classes. In particular, we consider formalisms for nonmonotonic reasoning, such as circumscription and default logic, as well as belief revision operators and the stable model semantics for logic programs with negation. One interesting result is that formalisms with the same time complexity do not necessarily belong to the same space efficiency class.
Backbone Fragility and the Local Search Cost Peak
Venue: arXiv cs.AI 2011
Year: 2011

The local search algorithm WSat is one of the most successful algorithms for solving the satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instances near the so-called `satisfiability threshold', but still shows a peak in search cost near the threshold and large variations in cost over different instances. We make a number of significant contributions to the analysis of WSat on high-cost random instances, using the recently-introduced concept of the backbone of a SAT instance. The backbone is the set of literals which are entailed by an instance. We find that the number of solutions predicts the cost well for small-backbone instances but is much less relevant for the large-backbone instances which appear near the threshold and dominate in the overconstrained region. We show a very strong correlation between search cost and the Hamming distance to the nearest solution early in WSat's search. This pattern leads us to introduce a measure of the backbone fragility of an instance, which indicates how persistent the backbone is as clauses are removed. We propose that high-cost random instances for local search are those with very large backbones which are also backbone-fragile. We suggest that the decay in cost beyond the satisfiability threshold is due to increasing backbone robustness (the opposite of backbone fragility). Our hypothesis makes three correct predictions. First, that the backbone robustness of an instance is negatively correlated with the local search cost when other factors are controlled for. Second, that backbone-minimal instances (which are 3-SAT instances altered so as to be more backbone-fragile) are unusually hard for WSat. Third, that the clauses most often unsatisfied during search are those whose deletion has the most effect on the backbone. In understanding the pathologies of local search methods, we hope to contribute to the development of new and better techniques.
A Transport-Friendly NIC for Multicore/Multiprocessor Systems
Venue: arXiv cs.NI 2011
Year: 2011

Receive side scaling (RSS) is a network interface card (NIC) technology. It provides the benefits of parallel receive processing in multiprocessing environments. However, existing RSS-enabled NICs lack a critical data steering mechanism that would automatically steer incoming network data to the same core on which its application process resides. This absence causes inefficient cache usage if an application is not running on the core on which RSS has scheduled the received traffic to be processed. In Linux systems, it cannot even ensure that packets in a TCP flow are processed by a single core, even if the interrupts for the flow are pinned to a specific core. This results in degraded performance. In this paper, we develop such a data steering mechanism in the NIC for multicore or multiprocessor systems. This data steering mechanism is mainly targeted at TCP, but it can be extended to other transport layer protocols. We term a NIC with such a data steering mechanism "A Transport Friendly NIC" (A-TFN). Experimental results have proven the effectiveness of A-TFN in accelerating TCP/IP performance.
The FF Planning System: Fast Plan Generation Through Heuristic Search
Venue: arXiv cs.AI 2011
Year: 2011

We describe and evaluate the algorithmic techniques that are used in the FF planning system. Like the HSP system, FF relies on forward state space search, using a heuristic that estimates goal distances by ignoring delete lists. Unlike HSP's heuristic, our method does not assume facts to be independent. We introduce a novel search strategy that combines hill-climbing with systematic search, and we show how other powerful heuristic information can be extracted and used to prune the search space. FF was the most successful automatic planner at the recent AIPS-2000 planning competition. We review the results of the competition, give data for other benchmark domains, and investigate the reasons for the runtime performance of FF compared to HSP.
ATTac-2000: An Adaptive Autonomous Bidding Agent
Venue: arXiv cs.AI 2011
Year: 2011

The First Trading Agent Competition (TAC) was held from June 22nd to July 8th, 2000. TAC was designed to create a benchmark problem in the complex domain of e-marketplaces and to motivate researchers to apply unique approaches to a common task. This article describes ATTac-2000, the first-place finisher in TAC. ATTac-2000 uses a principled bidding strategy that includes several elements of adaptivity. In addition to the success at the competition, isolated empirical results are presented indicating the robustness and effectiveness of ATTac-2000's adaptive strategy.
A Simple Characterization of the Minimal Obstruction Sets for Three-State Perfect Phylogenies
Venue: arXiv cs.DS 2011
Year: 2011

Lam, Gusfield, and Sridhar (2009) showed that a set of three-state characters has a perfect phylogeny if and only if every subset of three characters has a perfect phylogeny. They also gave a complete characterization of the sets of three three-state characters that do not have a perfect phylogeny. However, it is not clear from their characterization how to find a subset of three characters that does not have a perfect phylogeny without testing all triples of characters. In this note, we build upon their result by giving a simple characterization of when a set of three-state characters does not have a perfect phylogeny that can be inferred from testing all pairs of characters.
An efficient circle detection scheme in digital images using ant system algorithm
Venue: arXiv cs.CV 2011
Year: 2011

Detection of geometric features in digital images is an important exercise in image analysis and computer vision. The Hough Transform techniques for detection of circles require a huge memory space for data processing hence requiring a lot of time in computing the locations of the data space, writing to and searching through the memory space. In this paper we propose a novel and efficient scheme for detecting circles in edge-detected grayscale digital images. We use Ant-system algorithm for this purpose which has not yet found much application in this field. The main feature of this scheme is that it can detect both intersecting as well as non-intersecting circles with a time efficiency that makes it useful in real time applications. We build up an ant system of new type which finds out closed loops in the image and then tests them for circles.
Nearest Prime Simplicial Complex for Object Recognition
Venue: arXiv cs.LG 2011
Year: 2011

The structure representation of data distribution plays an important role in understanding the underlying mechanism of generating data. In this paper, we propose nearest prime simplicial complex approaches (NSC) by utilizing persistent homology to capture such structures. Assuming that each class is represented with a prime simplicial complex, we classify unlabeled samples based on the nearest projection distances from the samples to the simplicial complexes. We also extend the extrapolation ability of these complexes with a projection constraint term. Experiments in simulated and practical datasets indicate that compared with several published algorithms, the proposed NSC approaches achieve promising performance without losing the structure representation.
Using More Data to Speed-up Training Time
Venue: arXiv cs.LG 2011
Year: 2011

In many recent applications, data is plentiful. By now, we have a rather clear understanding of how more data can be used to improve the accuracy of learning algorithms. Recently, there has been a growing interest in understanding how more data can be leveraged to reduce the required training runtime. In this paper, we study the runtime of learning as a function of the number of available training examples, and underscore the main high-level techniques. We provide some initial positive results showing that the runtime can decrease exponentially while only requiring a polynomial growth of the number of examples, and spell-out several interesting open problems.
Synthesis from Recursive-Components Libraries
Venue: arXiv cs.LO 2011
Year: 2011

Synthesis is the automatic construction of a system from its specification. In classical synthesis algorithms it is always assumed that the system is "constructed from scratch" rather than composed from reusable components. This, of course, rarely happens in real life. In real life, almost every non-trivial commercial software system relies heavily on using libraries of reusable components. Furthermore, other contexts, such as web-service orchestration, can be modeled as synthesis of a system from a library of components. In 2009 we introduced LTL synthesis from libraries of reusable components. Here, we extend the work and study synthesis from component libraries with "call and return"' control flow structure. Such control-flow structure is very common in software systems. We define the problem of Nested-Words Temporal Logic (NWTL) synthesis from recursive component libraries, where NWTL is a specification formalism, richer than LTL, that is suitable for "call and return" computations. We solve the problem, providing a synthesis algorithm, and show the problem is 2EXPTIME-complete, as standard synthesis.
Separation of Test-Free Propositional Dynamic Logics over Context-Free Languages
Venue: arXiv cs.LO 2011
Year: 2011

For a class L of languages let PDL[L] be an extension of Propositional Dynamic Logic which allows programs to be in a language of L rather than just to be regular. If L contains a non-regular language, PDL[L] can express non-regular properties, in contrast to pure PDL. For regular, visibly pushdown and deterministic context-free languages, the separation of the respective PDLs can be proven by automata-theoretic techniques. However, these techniques introduce non-determinism on the automata side. As non-determinism is also the difference between DCFL and CFL, these techniques seem to be inappropriate to separate PDL[DCFL] from PDL[CFL]. Nevertheless, this separation is shown but for programs without test operators.
Repair Optimal Erasure Codes through Hadamard Designs
Venue: arXiv cs.IT 2011
Year: 2011

In distributed storage systems that employ erasure coding, the issue of minimizing the total {\it communication} required to exactly rebuild a storage node after a failure arises. This repair bandwidth depends on the structure of the storage code and the repair strategies used to restore the lost data. Designing high-rate maximum-distance separable (MDS) codes that achieve the optimum repair communication has been a well-known open problem. In this work, we use Hadamard matrices to construct the first explicit 2-parity MDS storage code with optimal repair properties for all single node failures, including the parities. Our construction relies on a novel method of achieving perfect interference alignment over finite fields with a finite file size, or number of extensions. We generalize this construction to design $m$-parity MDS codes that achieve the optimum repair communication for single systematic node failures and show that there is an interesting connection between our $m$-parity codes and the systematic-repair optimal permutation-matrix based codes of Tamo {\it et al.} \cite{Tamo} and Cadambe {\it et al.} \cite{PermCodes_ISIT, PermCodes}.
Sparse Principal Component of a Rank-deficient Matrix
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of identifying the sparse principal component of a rank-deficient matrix. We introduce auxiliary spherical variables and prove that there exists a set of candidate index-sets (that is, sets of indices to the nonzero elements of the vector argument) whose size is polynomially bounded, in terms of rank, and contains the optimal index-set, i.e. the index-set of the nonzero elements of the optimal solution. Finally, we develop an algorithm that computes the optimal sparse principal component in polynomial time for any sparsity degree.
Fusions of Description Logics and Abstract Description Systems
Venue: arXiv cs.AI 2011
Year: 2011

Fusions are a simple way of combining logics. For normal modal logics, fusions have been investigated in detail. In particular, it is known that, under certain conditions, decidability transfers from the component logics to their fusion. Though description logics are closely related to modal logics, they are not necessarily normal. In addition, ABox reasoning in description logics is not covered by the results from modal logics. In this paper, we extend the decidability transfer results from normal modal logics to a large class of description logics. To cover different description logics in a uniform way, we introduce abstract description systems, which can be seen as a common generalization of description and modal logics, and show the transfer results in this general setting.
A Knowledge Compilation Map
Venue: arXiv cs.AI 2011
Year: 2011

We propose a perspective on knowledge compilation which calls for analyzing different compilation approaches according to two key dimensions: the succinctness of the target compilation language, and the class of queries and transformations that the language supports in polytime. We then provide a knowledge compilation map, which analyzes a large number of existing target compilation languages according to their succinctness and their polytime transformations and queries. We argue that such analysis is necessary for placing new compilation approaches within the context of existing ones. We also go beyond classical, flat target compilation languages based on CNF and DNF, and consider a richer, nested class based on directed acyclic graphs (such as OBDDs), which we show to include a relatively large number of target compilation languages.
The Capacity Region of Multiway Relay Channels Over Finite Fields with Full Data Exchange
Venue: arXiv cs.IT 2011
Year: 2011

The multi-way relay channel is a multicast network where L users exchange data through a relay. In this paper, the capacity region of a class of multi-way relay channels is derived, where the channel inputs and outputs take values over finite fields. The cut-set upper bound to the capacity region is derived and is shown to be achievable by our proposed functional-decode-forward coding strategy. More specifically, for the general case where the users can transmit at possibly different rates, functional-decode-forward, combined with rate splitting and joint source-channel decoding, is proved to achieve the capacity region; while for the case where all users transmit at a common rate, rate splitting and joint source-channel decoding are not required to achieve the capacity. That the capacity-achieving coding strategies do not utilize the users' received signals in the users' encoding functions implies that feedback does not increase the capacity region of this class of multi-way relay channels.
Exact Reconstruction of the Rank Order Coding using Frames Theory
Venue: arXiv cs.CV 2011
Year: 2011

Our goal is to revisit rank order coding by proposing an original exact decoding procedure for it. Rank order coding was proposed by Simon Thorpe et al. who stated that the retina represents the visual stimulus by the order in which its cells are activated. A classical rank order coder/decoder was then designed on this basis [1]. Though, it appeared that the decoding procedure employed yields reconstruction errors that limit the model Rate/Quality performances when used as an image codec. The attempts made in the literature to overcome this issue are time consuming and alter the coding procedure, or are lacking mathematical support and feasibility for standard size images. Here we solve this problem in an original fashion by using the frames theory, where a frame of a vector space designates an extension for the notion of basis. First, we prove that the analyzing filter bank considered is a frame, and then we define the corresponding dual frame that is necessary for the exact image reconstruction. Second, to deal with the problem of memory overhead, we design a recursive out-of-core blockwise algorithm for the computation of this dual frame. Our work provides a mathematical formalism for the retinal model under study and defines a simple and exact reverse transform for it with up to 270 dB of PSNR gain compared to [1]. Furthermore, the framework presented here can be extended to several models of the visual cortical areas using redundant representations.
Characterization of 3D surface topography in 5-axis milling
Venue: arXiv cs.OH 2011
Year: 2011

Within the context of 5-axis free-form machining, CAM software offers various ways of tool-path generation, depending on the geometry of the surface to be machined. Therefore, as the manufactured surface quality results from the choice of the machining strategy and machining parameters, the prediction of surface roughness in function of the machining conditions is an important issue in 5-axis machining. The objective of this paper is to propose a simulation model of material removal in 5-axis based on the N-buffer method and integrating the Inverse Kinematics Transformation. The tooth track is linked with the velocity giving the surface topography resulting from actual machining conditions. The model is assessed thanks to a series of sweeping over planes according to various tool axis orientations and cutting conditions. 3D surface topography analyses are performed through the new areal surface roughness parameters proposed by recent standards.
Analysis of Error Floors of Non-Binary LDPC Codes over MBIOS Channel
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we investigate the error floors of non-binary low-density parity-check (LDPC) codes transmitted over the memoryless binary-input output-symmetric (MBIOS) channels. We provide a necessary and sufficient condition for successful decoding of zigzag cycle codes over the MBIOS channel by the belief propagation decoder. We consider an expurgated ensemble of non-binary LDPC codes by using the above necessary and sufficient condition, and hence exhibit lower error floors. Finally, we show lower bounds of the error floors for the expurgated LDPC code ensembles over the MBIOS channel.
An application of Grossone to the study of a family of tilings of the hyperbolic plane
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, we look at the improvement of our knowledge on a family of tilings of the hyperbolic plane which is brought in by the use of Sergeyev's numeral system based on grossone. It appears that the information we can get by using this new numeral system depends on the way we look at the tilings. The ways are significantly different but they confirm some results which were obtained in the traditional but constructive frame and allow us to obtain an additional precision with respect to this information.
Byzantine Fault Tolerance of Regenerating Codes
Venue: arXiv cs.DC 2011
Year: 2011

Recent years have witnessed a slew of coding techniques custom designed for networked storage systems. Network coding inspired regenerating codes are the most prolifically studied among these new age storage centric codes. A lot of effort has been invested in understanding the fundamental achievable trade-offs of storage and bandwidth usage to maintain redundancy in presence of different models of failures, showcasing the efficacy of regenerating codes with respect to traditional erasure coding techniques. For practical usability in open and adversarial environments, as is typical in peer-to-peer systems, we need however not only resilience against erasures, but also from (adversarial) errors. In this paper, we study the resilience of generalized regenerating codes (supporting multi-repairs, using collaboration among newcomers) in the presence of two classes of Byzantine nodes, relatively benign selfish (non-cooperating) nodes, as well as under more active, malicious polluting nodes. We give upper bounds on the resilience capacity of regenerating codes, and show that the advantages of collaborative repair can turn to be detrimental in the presence of Byzantine nodes. We further exhibit that system mechanisms can be combined with regenerating codes to mitigate the effect of rogue nodes.