feature-construction   189

« earlier    

[1607.01117] Anagram-free Graph Colouring
An anagram is a word of the form WP where W is a non-empty word and P is a permutation of W. We study anagram-free graph colouring and give bounds on the chromatic number. Alon et al. (2002) asked whether anagram-free chromatic number is bounded by a function of the maximum degree. We answer this question in the negative by constructing graphs with maximum degree 3 and unbounded anagram-free chromatic number. We also prove upper and lower bounds on the anagram-free chromatic number of trees in terms of their radius and pathwidth. Finally, we explore extensions to edge colouring and k-anagram-free colouring.
graph-theory  algorithms  graph-coloring  feature-construction  nudge-targets  consider:looking-to-see  computational-complexity 
28 days ago by Vaguery
[1802.08995] Using Information Invariants to Compare Swarm Algorithms and General Multi-Robot Algorithms: A Technical Report
Robotic swarms are decentralized multi-robot systems whose members use local information from proximal neighbors to execute simple reactive control laws that result in emergent collective behaviors. In contrast, members of a general multi-robot system may have access to global information, all- to-all communication or sophisticated deliberative collabora- tion. Some algorithms in the literature are applicable to robotic swarms. Others require the extra complexity of general multi- robot systems. Given an application domain, a system designer or supervisory operator must choose an appropriate system or algorithm respectively that will enable them to achieve their goals while satisfying mission constraints (e.g. bandwidth, energy, time limits). In this paper, we compare representative swarm and general multi-robot algorithms in two application domains - navigation and dynamic area coverage - with respect to several metrics (e.g. completion time, distance trav- elled). Our objective is to characterize each class of algorithms to inform offline system design decisions by engineers or online algorithm selection decisions by supervisory operators. Our contributions are (a) an empirical performance comparison of representative swarm and general multi-robot algorithms in two application domains, (b) a comparative analysis of the algorithms based on the theory of information invariants, which provides a theoretical characterization supported by our empirical results.
swarms  robotics  planning  collective-intelligence  information-theory  feature-construction  rather-interesting  to-write-about 
12 weeks ago by Vaguery
[1801.01922] Vectorization of Line Drawings via PolyVector Fields
Image tracing is a foundational component of the workflow in graphic design, engineering, and computer animation, linking hand-drawn concept images to collections of smooth curves needed for geometry processing and editing. Even for clean line drawings, modern algorithms often fail to faithfully vectorize junctions, or points at which curves meet; this produces vector drawings with incorrect connectivity. This subtle issue undermines the practical application of vectorization tools and accounts for hesitance among artists and engineers to use automatic vectorization software. To address this issue, we propose a novel image vectorization method based on state-of-the-art mathematical algorithms for frame field processing. Our algorithm is tailored specifically to disambiguate junctions without sacrificing quality.
graphics  algorithms  inference  rather-interesting  feature-construction  nudge-targets  consider:representation  consider:looking-to-see  consider:performance-measures 
march 2018 by Vaguery
[1606.05381] Deep Image Set Hashing
In applications involving matching of image sets, the information from multiple images must be effectively exploited to represent each set. State-of-the-art methods use probabilistic distribution or subspace to model a set and use specific distance measure to compare two sets. These methods are slow to compute and not compact to use in a large scale scenario. Learning-based hashing is often used in large scale image retrieval as they provide a compact representation of each sample and the Hamming distance can be used to efficiently compare two samples. However, most hashing methods encode each image separately and discard knowledge that multiple images in the same set represent the same object or person. We investigate the set hashing problem by combining both set representation and hashing in a single deep neural network. An image set is first passed to a CNN module to extract image features, then these features are aggregated using two types of set feature to capture both set specific and database-wide distribution information. The computed set feature is then fed into a multilayer perceptron to learn a compact binary embedding. Triplet loss is used to train the network by forming set similarity relations using class labels. We extensively evaluate our approach on datasets used for image matching and show highly competitive performance compared to state-of-the-art methods.
algorithms  machine-learning  rather-interesting  feature-construction  nudge-targets  consider:looking-at-code  consider:performance-measures 
march 2018 by Vaguery
[1709.08119] Analogies between the crossing number and the tangle crossing number
Tanglegrams are special graphs that consist of a pair of rooted binary trees with the same number of leaves, and a perfect matching between the two leaf-sets. These objects are of use in phylogenetics and are represented with straightline drawings where the leaves of the two plane binary trees are on two parallel lines and only the matching edges can cross. The tangle crossing number of a tanglegram is the minimum crossing number over all such drawings and is related to biologically relevant quantities, such as the number of times a parasite switched hosts.
Our main results for tanglegrams which parallel known theorems for crossing numbers are as follows. The removal of a single matching edge in a tanglegram with n leaves decreases the tangle crossing number by at most n−3, and this is sharp. Additionally, if γ(n) is the maximum tangle crossing number of a tanglegram with n leaves, we prove 12(n2)(1−o(1))≤γ(n)<12(n2). Further, we provide an algorithm for computing non-trivial lower bounds on the tangle crossing number in O(n4) time. This lower bound may be tight, even for tanglegrams with tangle crossing number Θ(n2).
graph-theory  feature-construction  phylogenetics  metrics  distance-measures  algorithms  rather-interesting  computational-complexity  nudge-targets 
february 2018 by Vaguery
[1710.02034] Weight = nonlinearity for all small weight Boolean functions
Given a Boolean function f, the (Hamming) weight wt(f) and the nonlinearity N(f) are well known to be important in designing functions that are useful in cryptography. The nonlinearity is expensive to compute, in general, so any shortcuts for doing that for particular functions f are significant. It is clear from the definitions that wt(f) \leq N(f). We give a useful and practical sufficient condition for the weight and nonlinearity to be equal, namely wt(f) \leq (2 to the power n-2) if f has n variables. It is shown that this inequality cannot be improved, in general. This condition can also be used to actually compute the nonlinearity in some cases. As an application, we give a simple proof for the value of the nonlinearity of the well known majority function. Previous proofs relied on many detailed results for the Krawtchouk polynomials.
information-theory  Boolean-functions  representation  distance  cryptography  feature-construction  rather-interesting  to-write-about  consider:genetic-programming 
january 2018 by Vaguery
[1705.00441] Learning Topic-Sensitive Word Representations
Distributed word representations are widely used for modeling words in NLP tasks. Most of the existing models generate one representation per word and do not consider different meanings of a word. We present two approaches to learn multiple topic-sensitive representations per word by using Hierarchical Dirichlet Process. We observe that by modeling topics and integrating topic distributions for each document we obtain representations that are able to distinguish between different meanings of a given word. Our models yield statistically significant improvements for the lexical substitution task indicating that commonly used single word representations, even when combined with contextual information, are insufficient for this task.
natural-language-processing  feature-construction  neural-networks  algorithms  nudge-targets  consider:looking-to-see  consider:performance-measures 
january 2018 by Vaguery
[1710.03568] 321-avoiding affine permutations and their many heaps
We study 321-avoiding affine permutations, and prove a formula for their enumeration with respect to the inversion number by using a combinatorial approach. This is done in two different ways, both related to Viennot's theory of heaps. First, we encode these permutations using certain heaps of monomers and dimers. This method specializes to the case of affine involutions. For the second proof, we introduce periodic parallelogram polyominoes, which are new combinatorial objects of independent interest. We enumerate them by extending the approach of Bousquet-M\'elou and Viennot used for classical parallelogram polyominoes. We finally establish a connection between these new objects and 321-avoiding affine permutations.
permutations  combinatorics  to-understand  representation  feature-construction 
january 2018 by Vaguery
[1703.07856] Testing for the Equality of two Distributions on High Dimensional Object Spaces
Energy statistics are estimators of the energy distance that depend on the distances between observations. The idea behind energy statistics is to consider a statistical potential energy that would parallel Newton's gravitational potential energy. This statistical potential energy is zero if and only if a certain null hypothesis relating two distributions holds true. In Szekely and Rizzo(2004), a nonparametric test for equality of two multivariate distributions was given, based on the Euclidean distance between observations. This test was shown to be effective for high dimensional multivariate data, and was implemented by an appropriate distribution free permutation test. As an extension of Szekely and Rizzo (2013), here we consider the energy distance between to independent random objects X and Y on the object space M, that admits an embedding into an Euclidean space. In the case of a Kendall shape space, we can use its VW-embedding into an Euclidean space of matrices and define the extrinsic distance between two shapes as their VW associated distance. The corresponding energy distance between two distributions of Kendall shapes of k-ads will be called VW-energy distance We test our methodology on, to compare the distributions of Kendall shape of the contour of the midsagittal section of the Corpus Callossum in normal vs ADHD diagnosed individuals. Here we use the VW distance between the shapes of two children CC midsections. Using the CC data coming originally from this http URL 1000.projects.nitrc.org/indi/adhd200/ it appears that the two Kendall shape distributions are not significantly different.
classification  feature-construction  rather-interesting  computer-vision  representation  algorithms  nudge-targets  consider:rediscovery  consider:looking-to-see 
november 2017 by Vaguery
[1710.06993] Improved Search in Hamming Space using Deep Multi-Index Hashing
Similarity-preserving hashing is a widely-used method for nearest neighbour search in large-scale image retrieval tasks. There has been considerable research on generating efficient image representation via the deep-network-based hashing methods. However, the issue of efficient searching in the deep representation space remains largely unsolved. To this end, we propose a simple yet efficient deep-network-based multi-index hashing method for simultaneously learning the powerful image representation and the efficient searching. To achieve these two goals, we introduce the multi-index hashing (MIH) mechanism into the proposed deep architecture, which divides the binary codes into multiple substrings. Due to the non-uniformly distributed codes will result in inefficiency searching, we add the two balanced constraints at feature-level and instance-level, respectively. Extensive evaluations on several benchmark image retrieval datasets show that the learned balanced binary codes bring dramatic speedups and achieve comparable performance over the existing baselines.
metrics  image-processing  deep-learning  performance-space-analysis  feature-construction  machine-learning  rather-interesting  similarity-measures  to-write-about 
november 2017 by Vaguery
[1709.09130] Output Range Analysis for Deep Neural Networks
Deep neural networks (NN) are extensively used for machine learning tasks such as image classification, perception and control of autonomous systems. Increasingly, these deep NNs are also been deployed in high-assurance applications. Thus, there is a pressing need for developing techniques to verify neural networks to check whether certain user-expected properties are satisfied. In this paper, we study a specific verification problem of computing a guaranteed range for the output of a deep neural network given a set of inputs represented as a convex polyhedron. Range estimation is a key primitive for verifying deep NNs. We present an efficient range estimation algorithm that uses a combination of local search and linear programming problems to efficiently find the maximum and minimum values taken by the outputs of the NN over the given input set. In contrast to recently proposed "monolithic" optimization approaches, we use local gradient descent to repeatedly find and eliminate local minima of the function. The final global optimum is certified using a mixed integer programming instance. We implement our approach and compare it with Reluplex, a recently proposed solver for deep neural networks. We demonstrate the effectiveness of the proposed approach for verification of NNs used in automated control as well as those used in classification.
neural-networks  benchmarking  rather-interesting  feature-construction  performance-measure  modeling-is-not-mathematics  algorithms  nudge-targets  consider:looking-to-see  consider:generalizing 
november 2017 by Vaguery
[1504.00212] New results on the stopping time behaviour of the Collatz 3x + 1 function
Let σn=⌊1+n⋅log23⌋. For the Collatz 3x + 1 function exists for each n∈ℕ a set of different residue classes (mod 2σn) of starting numbers s with finite stopping time σ(s)=σn. Let zn be the number of these residue classes for each n≥0 as listed in the OEIS as A100982. It is conjectured that for each n≥4 the value of zn is given by the formula
where δ∈ℤ assumes different values within the sum at intervals of 5 or 6 terms. This allows to create an iterative algorithm which generates zn for each n>12. This has been proved for each n≤10000. The number z10000 has 4527 digits.
number-theory  mathematical-recreations  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  feature-construction 
november 2017 by Vaguery
[1701.07681] Fast and Accurate Time Series Classification with WEASEL
Time series (TS) occur in many scientific and commercial applications, ranging from earth surveillance to industry automation to the smart grids. An important type of TS analysis is classification, which can, for instance, improve energy load forecasting in smart grids by detecting the types of electronic devices based on their energy consumption profiles recorded by automatic sensors. Such sensor-driven applications are very often characterized by (a) very long TS and (b) very large TS datasets needing classification. However, current methods to time series classification (TSC) cannot cope with such data volumes at acceptable accuracy; they are either scalable but offer only inferior classification quality, or they achieve state-of-the-art classification quality but cannot scale to large data volumes.
In this paper, we present WEASEL (Word ExtrAction for time SEries cLassification), a novel TSC method which is both scalable and accurate. Like other state-of-the-art TSC methods, WEASEL transforms time series into feature vectors, using a sliding-window approach, which are then analyzed through a machine learning classifier. The novelty of WEASEL lies in its specific method for deriving features, resulting in a much smaller yet much more discriminative feature set. On the popular UCR benchmark of 85 TS datasets, WEASEL is more accurate than the best current non-ensemble algorithms at orders-of-magnitude lower classification and training times, and it is almost as accurate as ensemble classifiers, whose computational complexity makes them inapplicable even for mid-size datasets. The outstanding robustness of WEASEL is also confirmed by experiments on two real smart grid datasets, where it out-of-the-box achieves almost the same accuracy as highly tuned, domain-specific methods.
time-series  classification  feature-construction  rather-interesting  modeling  to-write-about  to-do  consider:robustness 
november 2017 by Vaguery
[1611.07087] Connectivity in Hypergraphs
In this paper we consider two natural notions of connectivity for hypergraphs: weak and strong. We prove that the strong vertex connectivity of a connected hypergraph is bounded by its weak edge connectivity, thereby extending a theorem of Whitney from graphs to hypergraphs. We find that while determining a minimum weak vertex cut can be done in polynomial time and is equivalent to finding a minimum vertex cut in the 2-section of the hypergraph in question, determining a minimum strong vertex cut is NP-hard for general hypergraphs. Moreover, the problem of finding minimum strong vertex cuts remains NP-hard when restricted to hypergraphs with maximum edge size at most 3. We also discuss the relationship between strong vertex connectivity and the minimum transversal problem for hypergraphs, showing that there are classes of hypergraphs for which one of the problems is NP-hard while the other can be solved in polynomial time.
hypergraphs  combinatorics  define-your-terms  feature-construction  algorithms  computational-complexity  to-write-about 
october 2017 by Vaguery
[1710.00228] Physics-based Motion Planning: Evaluation Criteria and Benchmarking
Motion planning has evolved from coping with simply geometric problems to physics-based ones that incorporate the kinodynamic and the physical constraints imposed by the robot and the physical world. Therefore, the criteria for evaluating physics-based motion planners goes beyond the computational complexity (e.g. in terms of planning time) usually used as a measure for evaluating geometrical planners, in order to consider also the quality of the solution in terms of dynamical parameters. This study proposes an evaluation criteria and analyzes the performance of several kinodynamic planners, which are at the core of physics-based motion planning, using different scenarios with fixed and manipulatable objects. RRT, EST, KPIECE and SyCLoP are used for the benchmarking. The results show that KPIECE computes the time-optimal solution with heighest success rate, whereas, SyCLoP compute the most power-optimal solution among the planners used.
simulation  planning  algorithms  rather-interesting  feature-construction  approximation  nudge-targets  consider:representation 
october 2017 by Vaguery
[1610.00331] Comparing 1D and 2D Real Time on Cellular Automata
We study the influence of the dimension of cellular automata (CA) for real time language recognition of one-dimensional languages with parallel input. Specifically, we focus on the question of determining whether every language that can be recognized in real time on a 2-dimensional CA working on the Moore neighborhood can also be recognized in real time by a 1-dimensional CA working on the standard two-way neighborhood.
We show that 2-dimensional CA in real time can perform a linear number of simulations of a 1-dimensional real time CA. If the two classes are equal then the number of simulated instances can be polynomial.
cellular-automata  rather-interesting  alternative-computational-models  distributed-processing  computer-science  universality  representation  feature-construction  engineering-design  to-write-about 
october 2017 by Vaguery
[math/0103224] On the Minimum Ropelength of Knots and Links
The ropelength of a knot is the quotient of its length and its thickness, the radius of the largest embedded normal tube around the knot. We prove existence and regularity for ropelength minimizers in any knot or link type; these are C1,1 curves, but need not be smoother. We improve the lower bound for the ropelength of a nontrivial knot, and establish new ropelength bounds for small knots and links, including some which are sharp.
knot-theory  optimization  rather-interesting  feature-construction  geometry  engineering-design  nudge-targets  consider:approximation 
october 2017 by Vaguery
[math/0204106] The Second Hull of a Knotted Curve
The convex hull of a set K in space consists of points which are, in a certain sense, "surrounded" by K. When K is a closed curve, we define its higher hulls, consisting of points which are "multiply surrounded" by the curve. Our main theorem shows that if a curve is knotted then it has a nonempty second hull. This provides a new proof of the Fary/Milnor theorem that every knotted curve has total curvature at least 4pi.
knot-theory  geometry  topology  rather-interesting  feature-construction  proof  nudge-targets  consider:representation  consider:looking-to-see 
october 2017 by Vaguery
[1509.07588] Fractional coverings, greedy coverings, and rectifier networks
A rectifier network is a directed acyclic graph with distinguished sources and sinks; it is said to compute a Boolean matrix M that has a 1 in the entry (i,j) iff there is a path from the jth source to the ith sink. The smallest number of edges in a rectifier network computing M is a classic complexity measure on matrices, which has been studied for more than half a century.
We explore two well-known techniques that have hitherto found little to no applications in this theory. Both of them build on a basic fact that depth-2 rectifier networks are essentially weighted coverings of Boolean matrices with rectangles. We obtain new results by using fractional and greedy coverings (defined in the standard way).
First, we show that all fractional coverings of the so-called full triangular matrix have cost at least nlogn. This provides (a fortiori) a new proof of the tight lower bound on its depth-2 complexity (the exact value has been known since 1965, but previous proofs are based on different arguments). Second, we show that the greedy heuristic is instrumental in tightening the upper bound on the depth-2 complexity of the Kneser-Sierpi\'nski (disjointness) matrix. The previous upper bound is O(n1.28), and we improve it to O(n1.17), while the best known lower bound is Ω(n1.16). Third, using fractional coverings, we obtain a form of direct product theorem that gives a lower bound on unbounded-depth complexity of Kronecker (tensor) products of matrices. In this case, the greedy heuristic shows (by an argument due to Lov\'asz) that our result is only a logarithmic factor away from the "full" direct product theorem. Our second and third results constitute progress on open problem 7.3 and resolve, up to a logarithmic factor, open problem 7.5 from a recent book by Jukna and Sergeev (in Foundations and Trends in Theoretical Computer Science (2013)).
network-theory  feature-construction  rather-interesting  graph-theory  representation  nudge-targets  consider:rediscovery 
october 2017 by Vaguery
[1707.03894] The Generalized Nagell-Ljunggren Problem: Powers with Repetitive Representations
We consider a natural generalization of the Nagell-Ljunggren equation to the case where the qth power of an integer y, for q >= 2, has a base-b representation that consists of a length-l block of digits repeated n times, where n >= 2. Assuming the abc conjecture of Masser and Oesterl\'e, we completely characterize those triples (q, n, l) for which there are infinitely many solutions b. In all cases predicted by the abc conjecture, we are able (without any assumptions) to prove there are indeed infinitely many solutions.
number-theory  feature-construction  rather-interesting  mathematical-recreations  nudge-targets  consider:looking-to-see  consider:classification 
october 2017 by Vaguery

« earlier    

related tags

aesthetics  agent-based  algebra  algorithms  also-not-machine-learning  alternative-computational-models  approximation  auto  automata  benchmarking  bioinformatics  biophysics  boolean-functions  cellular-automata  cheminformatics  classification  clustering  collective-intelligence  combinatorics  community-detection  community-formation  compare-to-pareto-gp-features  complexology  compression  computational-complexity  computational-geometry  computer-science  computer-vision  consider:approximation  consider:classification  consider:counterexamples  consider:evolutionary-algorithms  consider:exploration-vs-exploitation  consider:feature-discovery  consider:for-push  consider:generalization  consider:generalizing  consider:genetic-programming  consider:looking-at-code  consider:looking-to-see  consider:performance-measures  consider:performance-space-analysis  consider:prediction-from-graph  consider:prediction  consider:rediscovery  consider:reds  consider:representation  consider:review  consider:robustness  consider:simulation  consider:trying-this-out  consider:variant-overlays  continued-fractions  coupled-oscillators  cryptography  curse-of-dimensionality  data-analysis  data-mining  data-structures  deep-learning  define-your-terms  digital-humanities  dimension-reduction  discrete-mathematics  distance-measures  distance  distributed-processing  dynamic-programming  dynamical-systems  edit-distance  emergent-design  encoders  energy-landscapes  engineering-design  explanation  extreme-values  face-recognition  feature-discovery  feature-extraction  financial-engineering  fitness-landscapes  formal-languages  game-theory  games  generative-art  generative-models  genetic-algorithm  geometry  graph-coloring  graph-layout  graph-theory  graphics  hard-problems  heuristics  hey-i-know-this-guy  hypergraphs  image-analysis  image-processing  image-segmentation  image-synthesis  inference  information-theory  interpretability  introspection  knot-theory  lattice-proteins  learning-from-data  looking-to-see  machine-learning  magic-squares  mathematical-programming  mathematical-recreations  matrices  meta-optimization  metrics  modeling-is-not-mathematics  modeling  natural-language-processing  network-theory  neural-networks  nonlinear-dynamics  nudge-targets  number-theory  numerical-methods  ontology  optimization  out-of-the-box  outliers  parametrization  party-like-its-1999  pattern-discovery  patterns  performance-measure  performance-space-analysis  permutations  pharmaceutical  philosophy-of-engineering  phylogenetics  physiology  plane-geometry  planning  polygons  proof  quantum-computing  quantums  ramanujan  random-walks  rather-interesting  recognition  recommendations  representation  rigidity  robotics  robustness  rotor-router  sandpiles  sentiment-analysis  similarity-measures  simulation  social-networks  speech-synthesis  statistics  storytelling  strings  structural-biology  superresolution  swarms  text-mining  time-series  time-warping  to-do  to-simulate  to-understand  to-write-about  topology  tqsk-decoomposition  universality  updated  variable-selection  visualization  wavelets 

Copy this bookmark: