OpenRaiser/Intern-Atlas huggingface dataset:
Training Logistic Regression and SVM on 200GB Data Using b-Bit Minwise Hashing and Comparisons with Vowpal Wabbit (VW)
Venue: arXiv cs.LG 2011
Year: 2011

We generated a dataset of 200 GB with 10^9 features, to test our recent b-bit minwise hashing algorithms for training very large-scale logistic regression and SVM. The results confirm our prior work that, compared with the VW hashing algorithm (which has the same variance as random projections), b-bit minwise hashing is substantially more accurate at the same storage. For example, with merely 30 hashed values per data point, b-bit minwise hashing can achieve similar accuracies as VW with 2^14 hashed values per data point. We demonstrate that the preprocessing cost of b-bit minwise hashing is roughly on the same order of magnitude as the data loading time. Furthermore, by using a GPU, the preprocessing cost can be reduced to a small fraction of the data loading time. Minwise hashing has been widely used in industry, at least in the context of search. One reason for its popularity is that one can efficiently simulate permutations by (e.g.,) universal hashing. In other words, there is no need to store the permutation matrix. In this paper, we empirically verify this practice, by demonstrating that even using the simplest 2-universal hashing does not degrade the learning performance.
Regular Expression Matching and Operational Semantics
Venue: arXiv cs.LO 2011
Year: 2011

Many programming languages and tools, ranging from grep to the Java String library, contain regular expression matchers. Rather than first translating a regular expression into a deterministic finite automaton, such implementations typically match the regular expression on the fly. Thus they can be seen as virtual machines interpreting the regular expression much as if it were a program with some non-deterministic constructs such as the Kleene star. We formalize this implementation technique for regular expression matching using operational semantics. Specifically, we derive a series of abstract machines, moving from the abstract definition of matching to increasingly realistic machines. First a continuation is added to the operational semantics to describe what remains to be matched after the current expression. Next, we represent the expression as a data structure using pointers, which enables redundant searches to be eliminated via testing for pointer equality. From there, we arrive both at Thompson's lockstep construction and a machine that performs some operations in parallel, suitable for implementation on a large number of cores, such as a GPU. We formalize the parallel machine using process algebra and report some preliminary experiments with an implementation on a graphics processor using CUDA.
Reiter's Default Logic Is a Logic of Autoepistemic Reasoning And a Good One, Too
Venue: arXiv cs.AI 2011
Year: 2011

A fact apparently not observed earlier in the literature of nonmonotonic reasoning is that Reiter, in his default logic paper, did not directly formalize informal defaults. Instead, he translated a default into a certain natural language proposition and provided a formalization of the latter. A few years later, Moore noted that propositions like the one used by Reiter are fundamentally different than defaults and exhibit a certain autoepistemic nature. Thus, Reiter had developed his default logic as a formalization of autoepistemic propositions rather than of defaults. The first goal of this paper is to show that some problems of Reiter's default logic as a formal way to reason about informal defaults are directly attributable to the autoepistemic nature of default logic and to the mismatch between informal defaults and the Reiter's formal defaults, the latter being a formal expression of the autoepistemic propositions Reiter used as a representation of informal defaults. The second goal of our paper is to compare the work of Reiter and Moore. While each of them attempted to formalize autoepistemic propositions, the modes of reasoning in their respective logics were different. We revisit Moore's and Reiter's intuitions and present them from the perspective of autotheoremhood, where theories can include propositions referring to the theory's own theorems. We then discuss the formalization of this perspective in the logics of Moore and Reiter, respectively, using the unifying semantic framework for default and autoepistemic logics that we developed earlier. We argue that Reiter's default logic is a better formalization of Moore's intuitions about autoepistemic propositions than Moore's own autoepistemic logic.
Origins of Answer-Set Programming - Some Background And Two Personal Accounts
Venue: arXiv cs.AI 2011
Year: 2011

We discuss the evolution of aspects of nonmonotonic reasoning towards the computational paradigm of answer-set programming (ASP). We give a general overview of the roots of ASP and follow up with the personal perspective on research developments that helped verbalize the main principles of ASP and differentiated it from the classical logic programming.
Biologically Inspired Process Calculi, Petri Nets and Membrane Computing
Venue: arXiv cs.DC 2011
Year: 2011

This volume represents the proceedings of the 5th Workshop on Membrane Computing and Biologically Inspired Process Calculi (MeCBIC 2011), held together with the 12th International Conference on Membrane Computing on 23rd August 2011 in Fontainebleau, France.
A Multiagent Simulation for Traffic Flow Management with Evolutionary Optimization
Venue: arXiv cs.MA 2011
Year: 2011

A traffic flow is one of the main transportation issues in nowadays industrialized agglomerations. Configuration of traffic lights is among the key aspects in traffic flow management. This paper proposes an evolutionary optimization tool that utilizes multiagent simulator in order to obtain accurate model. Even though more detailed studies are still necessary, a preliminary research gives an expectation for promising results.
Structured Sparsity and Generalization
Venue: arXiv cs.LG 2011
Year: 2011

We present a data dependent generalization bound for a large class of regularized algorithms which implement structured sparsity constraints. The bound can be applied to standard squared-norm regularization, the Lasso, the group Lasso, some versions of the group Lasso with overlapping groups, multiple kernel learning and other regularization schemes. In all these cases competitive results are obtained. A novel feature of our bound is that it can be applied in an infinite dimensional setting such as the Lasso in a separable Hilbert space or multiple kernel learning with a countable number of kernels.
Feature Reinforcement Learning In Practice
Venue: arXiv cs.AI 2011
Year: 2011

Following a recent surge in using history-based methods for resolving perceptual aliasing in reinforcement learning, we introduce an algorithm based on the feature reinforcement learning framework called PhiMDP. To create a practical algorithm we devise a stochastic search procedure for a class of context trees based on parallel tempering and a specialized proposal distribution. We provide the first empirical evaluation for PhiMDP. Our proposed algorithm achieves superior performance to the classical U-tree algorithm and the recent active-LZ algorithm, and is competitive with MC-AIXI-CTW that maintains a bayesian mixture over all context trees up to a chosen depth.We are encouraged by our ability to compete with this sophisticated method using an algorithm that simply picks one single model, and uses Q-learning on the corresponding MDP. Our PhiMDP algorithm is much simpler, yet consumes less time and memory. These results show promise for our future work on attacking more complex and larger problems.
Pattern 1^j0^i avoiding binary words
Venue: arXiv cs.FL 2011
Year: 2011

In this paper we study the enumeration and the construction, according to the number of ones, of particular binary words avoiding a fixed pattern. The growth of such words can be described by particular jumping and marked succession rules. This approach enables us to obtain an algorithm which constructs all binary words having a fixed number of ones and then kills those containing the forbidden pattern.
Monoids and Maximal Codes
Venue: arXiv cs.FL 2011
Year: 2011

In recent years codes that are not Uniquely Decipherable (UD) are been studied partitioning them in classes that localize the ambiguities of the code. A natural question is how we can extend the notion of maximality to codes that are not UD. In this paper we give an answer to this question. To do this we introduce a partial order in the set of submonoids of a monoid showing the existence, in this poset, of maximal elements that we call full monoids. Then a set of generators of a full monoid is, by definition, a maximal code. We show how this definition extends, in a natural way, the existing definition concerning UD codes and we find a characteristic property of a monoid generated by a maximal UD code.
Unambiguous 1-Uniform Morphisms
Venue: arXiv cs.FL 2011
Year: 2011

A morphism h is unambiguous with respect to a word w if there is no other morphism g that maps w to the same image as h. In the present paper we study the question of whether, for any given word, there exists an unambiguous 1-uniform morphism, i.e., a morphism that maps every letter in the word to an image of length 1.
Word posets, with applications to Coxeter groups
Venue: arXiv cs.DM 2011
Year: 2011

We discuss the theory of certain partially ordered sets that capture the structure of commutation classes of words in monoids. As a first application, it follows readily that counting words in commutation classes is #P-complete. We then apply the partially ordered sets to Coxeter groups. Some results are a proof that enumerating the reduced words of elements of Coxeter groups is #P-complete, a recursive formula for computing the number of commutation classes of reduced words, as well as stronger bounds on the maximum number of commutation classes than were previously known. This also allows us to improve the known bounds on the number of primitive sorting networks.
Permutation complexity of the fixed points of some uniform binary morphisms
Venue: arXiv cs.DM 2011
Year: 2011

An infinite permutation is a linear order on the set N. We study the properties of infinite permutations generated by fixed points of some uniform binary morphisms, and find the formula for their complexity.
AIG Rewriting Using 5-Input Cuts
Venue: arXiv cs.LO 2011
Year: 2011

Rewriting is a common approach to logic optimization based on local transformations. Most commercially available logic synthesis tools include a rewriting engine that may be used multiple times on the same netlist during optimization. This paper presents an And-Inverter graph based rewriting algorithm using 5-input cuts. The best circuits are pre-computed for a subset of NPN classes of 5-variable functions. Cut enumeration and Boolean matching are used to identify replacement candidates. The presented approach is expected to complement existing rewriting approaches which are usually based on 4-input cuts. The experimental results show that, by adding the new rewriting algorithm to ABC synthesis tool, we can further reduce the area of heavily optimized large circuits by 5.57% on average.
Model of skyscraper evacuation with the use of space symmetry and fluid dynamic approximation
Venue: arXiv cs.MA 2011
Year: 2011

The simulation of evacuation of pedestrians from skyscraper is a situation where the symmetry analysis method and equations of fluid dynamics finds to be very useful. When applied, they strongly reduce the number of free parameters used in simulations and in such a way speed up the calculations and make them easier to manage by the programmer and what is even more important, they can give a fresh insight into a problem of evacuation and help with incorporation of "Ambient Intelligent Devices" into future real buildings. We have analyzed various, simplified, cases of evacuation from skyscraper by employing improved "Social Force Model". For each of them we obtained the average force acting on the pedestrian as a function of the evacuation time. The results clearly show that both methods mentioned above, can be successfully implemented in the simulation process and return with satisfactory conclusions.
Using Inverse lambda and Generalization to Translate English to Formal Languages
Venue: arXiv cs.CL 2011
Year: 2011

We present a system to translate natural language sentences to formulas in a formal or a knowledge representation language. Our system uses two inverse lambda-calculus operators and using them can take as input the semantic representation of some words, phrases and sentences and from that derive the semantic representation of other words and phrases. Our inverse lambda operator works on many formal languages including first order logic, database query languages and answer set programming. Our system uses a syntactic combinatorial categorial parser to parse natural language sentences and also to construct the semantic meaning of the sentences as directed by their parsing. The same parser is used for both. In addition to the inverse lambda-calculus operators, our system uses a notion of generalization to learn semantic representation of words from the semantic representation of other words that are of the same category. Together with this, we use an existing statistical learning approach to assign weights to deal with multiple meanings of words. Our system produces improved results on standard corpora on natural language interfaces for robot command and control and database queries.
Finding Community Structure with Performance Guarantees in Complex Networks
Venue: arXiv cs.SI 2011
Year: 2011

Many networks including social networks, computer networks, and biological networks are found to divide naturally into communities of densely connected individuals. Finding community structure is one of fundamental problems in network science. Since Newman's suggestion of using \emph{modularity} as a measure to qualify the goodness of community structures, many efficient methods to maximize modularity have been proposed but without a guarantee of optimality. In this paper, we propose two polynomial-time algorithms to the modularity maximization problem with theoretical performance guarantees. The first algorithm comes with a \emph{priori guarantee} that the modularity of found community structure is within a constant factor of the optimal modularity when the network has the power-law degree distribution. Despite being mainly of theoretical interest, to our best knowledge, this is the first approximation algorithm for finding community structure in networks. In our second algorithm, we propose a \emph{sparse metric}, a substantially faster linear programming method for maximizing modularity and apply a rounding technique based on this sparse metric with a \emph{posteriori approximation guarantee}. Our experiments show that the rounding algorithm returns the optimal solutions in most cases and are very scalable, that is, it can run on a network of a few thousand nodes whereas the LP solution in the literature only ran on a network of at most 235 nodes.
More Jabber about the Collatz Conjecture and a Closed Form for Detecting Cycles on Special Subsequences [Assertion: Collatz cycles]
Venue: arXiv cs.DM 2011
Year: 2011

Professor Cadogan at the University of the West Indies identified special starting points that yield long subsequences where the normalization constant, k, is always one. I studied these special sequences and found an implicit mixed integer equation in closed form which if solved would produce seed values in cycling subsequences. Such cycles only occur among extremely large numbers, causing the equation to be difficult to solve numerically.
Convergence of a Recombination-Based Elitist Evolutionary Algorithm on the Royal Roads Test Function
Venue: arXiv cs.NE 2011
Year: 2011

We present an analysis of the performance of an elitist Evolutionary algorithm using a recombination operator known as 1-Bit-Swap on the Royal Roads test function based on a population. We derive complete, approximate and asymptotic convergence rates for the algorithm. The complete model shows the benefit of the size of the population and re- combination pool.
OSD: A Source Level Bug Localization Technique Incorporating Control Flow and State Information in Object Oriented Program
Venue: arXiv cs.SE 2011
Year: 2011

Bug localization in object oriented program ha s always been an important issue in softeware engineering. In this paper, I propose a source level bug localization technique for object oriented embedded programs. My proposed technique, presents the idea of debugging an object oriented program in class level, incorporating the object state information into the Class Dependence Graph (ClDG). Given a program (having buggy statement) and an input that fails and others pass, my approach uses concrete as well as symbolic execution to synthesize the passing inputs that marginally from the failing input in their control flow behavior. A comparison of the execution traces of the failing input and the passing input provides necessary clues to the root-cause of the failure. A state trace difference, regarding the respective nodes of the ClDG is obtained, which leads to detect the bug in the program.
QoS Routing using OLSR with Optimization for Flooding
Venue: arXiv cs.NI 2011
Year: 2011

Mobile Ad-hoc Network (MANET) is the self organizing collection of mobile nodes. The communication in MANET is done via a wireless media. Ad hoc wireless networks have massive commercial and military potential because of their mobility support. Due to demanding real time multimedia applications, Quality of Services (QoS) support in such infrastructure less networks have become essential. QoS routing in mobile Ad-Hoc networks is challenging due to rapid change in network topology. Consequently, the available state information for routing is inherently imprecise. QoS routing may suffer badly due to several factors including radio interference on available bandwidth, and inefficient flooding of information to the adjacent nodes. As a result the performance of the network degrades substantially. This paper aims at the solution for energy efficient QoS routing by best utilization of network resources such as energy and bandwidth. A comparative study shows that despite the overhead due to QoS management, this solution performs better than classical OLSR protocol in terms of QoS and efficient utilization of energy.
Computational Complexity of Cyclotomic Fast Fourier Transforms over Characteristic-2 Fields
Venue: arXiv cs.IT 2011
Year: 2011

Cyclotomic fast Fourier transforms (CFFTs) are efficient implementations of discrete Fourier transforms over finite fields, which have widespread applications in cryptography and error control codes. They are of great interest because of their low multiplicative and overall complexities. However, their advantages are shown by inspection in the literature, and there is no asymptotic computational complexity analysis for CFFTs. Their high additive complexity also incurs difficulties in hardware implementations. In this paper, we derive the bounds for the multiplicative and additive complexities of CFFTs, respectively. Our results confirm that CFFTs have the smallest multiplicative complexities among all known algorithms while their additive complexities render them asymptotically suboptimal. However, CFFTs remain valuable as they have the smallest overall complexities for most practical lengths. Our additive complexity analysis also leads to a structured addition network, which not only has low complexity but also is suitable for hardware implementations.
Prismatic Algorithm for Discrete D.C. Programming Problems
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we propose the first exact algorithm for minimizing the difference of two submodular functions (D.S.), i.e., the discrete version of the D.C. programming problem. The developed algorithm is a branch-and-bound-based algorithm which responds to the structure of this problem through the relationship between submodularity and convexity. The D.S. programming problem covers a broad range of applications in machine learning because this generalizes the optimization of a wide class of set functions. We empirically investigate the performance of our algorithm, and illustrate the difference between exact and approximate solutions respectively obtained by the proposed and existing algorithms in feature selection and discriminative structure learning.
Complexity of a Single Face in an Arrangement of s-Intersecting Curves
Venue: arXiv cs.CG 2011
Year: 2011

Consider a face F in an arrangement of n Jordan curves in the plane, no two of which intersect more than s times. We prove that the combinatorial complexity of F is O(λ_s(n)), O(λ_{s+1}(n)), and O(λ_{s+2}(n)), when the curves are bi-infinite, semi-infinite, or bounded, respectively; λ_k(n) is the maximum length of a Davenport-Schinzel sequence of order k on an alphabet of n symbols. Our bounds asymptotically match the known worst-case lower bounds. Our proof settles the still apparently open case of semi-infinite curves. Moreover, it treats the three cases in a fairly uniform fashion.
On Compressing Permutations and Adaptive Sorting
Venue: arXiv cs.DS 2011
Year: 2011

Previous compact representations of permutations have focused on adding a small index on top of the plain data $<π(1), π(2),...π(n)>$, in order to efficiently support the application of the inverse or the iterated permutation. In this paper we initiate the study of techniques that exploit the compressibility of the data itself, while retaining efficient computation of $π(i)$ and its inverse. In particular, we focus on exploiting {\em runs}, which are subsets (contiguous or not) of the domain where the permutation is monotonic. Several variants of those types of runs arise in real applications such as inverted indexes and suffix arrays. Furthermore, our improved results on compressed data structures for permutations also yield better adaptive sorting algorithms.
Exploiting the Passive Dynamics of a Compliant Leg to Develop Gait Transitions
Venue: arXiv cs.RO 2011
Year: 2011

In the area of bipedal locomotion, the spring loaded inverted pendulum (SLIP) model has been proposed as a unified framework to explain the dynamics of a wide variety of gaits. In this paper, we present a novel analysis of the mathematical model and its dynamical properties. We use the perspective of hybrid dynamical systems to study the dynamics and define concepts such as partial stability and viability. With this approach, on the one hand, we identified stable and unstable regions of locomotion. On the other hand, we found ways to exploit the unstable regions of locomotion to induce gait transitions at a constant energy regime. Additionally, we show that simple non-constant angle of attack control policies can render the system almost always stable.