Vaguery + consider:feature-discovery   249

 « earlier
Exactly how bad is the 13 times table? | The Aperiodical
Along the way, OEIS editor Charles R Greathouse IV added this intriguing conjecture:

Conjecture: a(n)≤N
for all n
. Perhaps N
can be taken as 81
.
5 weeks ago by Vaguery
[1709.04109] Empower Sequence Labeling with Task-Aware Neural Language Model
Linguistic sequence labeling is a general modeling approach that encompasses a variety of problems, such as part-of-speech tagging and named entity recognition. Recent advances in neural networks (NNs) make it possible to build reliable models without handcrafted features. However, in many cases, it is hard to obtain sufficient annotations to train these models. In this study, we develop a novel neural framework to extract abundant knowledge hidden in raw texts to empower the sequence labeling task. Besides word-level knowledge contained in pre-trained word embeddings, character-aware neural language models are incorporated to extract character-level knowledge. Transfer learning techniques are further adopted to mediate different components and guide the language model towards the key knowledge. Comparing to previous methods, these task-specific knowledge allows us to adopt a more concise model and conduct more efficient training. Different from most transfer learning methods, the proposed framework does not rely on any additional supervision. It extracts knowledge from self-contained order information of training sequences. Extensive experiments on benchmark datasets demonstrate the effectiveness of leveraging character-level knowledge and the efficiency of co-training. For example, on the CoNLL03 NER task, model training completes in about 6 hours on a single GPU, reaching F1 score of 91.71±0.10 without using any extra annotation.
natural-language-processing  deep-learning  neural-networks  nudge-targets  consider:feature-discovery  consider:representation  to-write-about
7 weeks ago by Vaguery
Estimating barriers to gene flow from distorted isolation by distance patterns | bioRxiv
In continuous populations with local migration, nearby pairs of individuals have on average more similar genotypes than geographically well separated pairs. A barrier to gene flow distorts this classical pattern of isolation by distance. Genetic similarity is decreased for sample pairs on different sides of the barrier and increased for pairs on the same side near the barrier. Here, we introduce an inference scheme that utilizes this signal to detect and estimate the strength of a linear barrier to gene flow in two-dimensions. We use a diffusion approximation to model the effects of a barrier on the geographical spread of ancestry backwards in time. This approach allows us to calculate the chance of recent coalescence and probability of identity by descent. We introduce an inference scheme that fits these theoretical results to the geographical covariance structure of bialleleic genetic markers. It can estimate the strength of the barrier as well as several demographic parameters. We investigate the power of our inference scheme to detect barriers by applying it to a wide range of simulated data. We also showcase an example application to a Antirrhinum majus (snapdragon) flower color hybrid zone, where we do not detect any signal of a strong genome wide barrier to gene flow.
population-biology  theoretical-biology  rather-interesting  simulation  to-write-about  consider:feature-discovery
7 weeks ago by Vaguery
[1712.08373] Notes on complexity of packing coloring
A packing k-coloring for some integer k of a graph G=(V,E) is a mapping
φ:V→{1,…,k} such that any two vertices u,v of color φ(u)=φ(v) are in distance at least φ(u)+1. This concept is motivated by frequency assignment problems. The \emph{packing chromatic number} of G is the smallest k such that there exists a packing k-coloring of G.
Fiala and Golovach showed that determining the packing chromatic number for chordal graphs is \NP-complete for diameter exactly 5. While the problem is easy to solve for diameter 2, we show \NP-completeness for any diameter at least 3. Our reduction also shows that the packing chromatic number is hard to approximate within n1/2−ε for any ε>0.
In addition, we design an \FPT algorithm for interval graphs of bounded diameter. This leads us to exploring the problem of finding a partial coloring that maximizes the number of colored vertices.
graph-theory  algorithms  combinatorics  proof  approximation  nudge-targets  consider:looking-to-see  consider:feature-discovery
8 weeks ago by Vaguery
[1710.02271] Unsupervised Extraction of Representative Concepts from Scientific Literature
This paper studies the automated categorization and extraction of scientific concepts from titles of scientific articles, in order to gain a deeper understanding of their key contributions and facilitate the construction of a generic academic knowledgebase. Towards this goal, we propose an unsupervised, domain-independent, and scalable two-phase algorithm to type and extract key concept mentions into aspects of interest (e.g., Techniques, Applications, etc.). In the first phase of our algorithm we propose PhraseType, a probabilistic generative model which exploits textual features and limited POS tags to broadly segment text snippets into aspect-typed phrases. We extend this model to simultaneously learn aspect-specific features and identify academic domains in multi-domain corpora, since the two tasks mutually enhance each other. In the second phase, we propose an approach based on adaptor grammars to extract fine grained concept mentions from the aspect-typed phrases without the need for any external resources or human effort, in a purely data-driven manner. We apply our technique to study literature from diverse scientific domains and show significant gains over state-of-the-art concept extraction techniques. We also present a qualitative analysis of the results obtained.
natural-language-processing  POS-tagging  algorithms  data-fusion  machine-learning  text-mining  nudge-targets  consider:feature-discovery
11 weeks ago by Vaguery
[1802.08435] Efficient Neural Audio Synthesis
Sequential models achieve state-of-the-art results in audio, visual and textual domains with respect to both estimating the data distribution and generating high-quality samples. Efficient sampling for this class of models has however remained an elusive problem. With a focus on text-to-speech synthesis, we describe a set of general techniques for reducing sampling time while maintaining high output quality. We first describe a single-layer recurrent neural network, the WaveRNN, with a dual softmax layer that matches the quality of the state-of-the-art WaveNet model. The compact form of the network makes it possible to generate 24kHz 16-bit audio 4x faster than real time on a GPU. Second, we apply a weight pruning technique to reduce the number of weights in the WaveRNN. We find that, for a constant number of parameters, large sparse networks perform better than small dense networks and this relationship holds for sparsity levels beyond 96%. The small number of weights in a Sparse WaveRNN makes it possible to sample high-fidelity audio on a mobile CPU in real time. Finally, we propose a new generation scheme based on subscaling that folds a long sequence into a batch of shorter sequences and allows one to generate multiple samples at once. The Subscale WaveRNN produces 16 samples per step without loss of quality and offers an orthogonal method for increasing sampling efficiency.
audio-synthesis  machine-learning  WaveNet  neural-networks  signal-processing  time-series  generative-models  to-write-about  nudge-targets  recurrent-networks  performance-measure  consider:feature-discovery
11 weeks ago by Vaguery
[1506.09039] Scalable Discrete Sampling as a Multi-Armed Bandit Problem
Drawing a sample from a discrete distribution is one of the building components for Monte Carlo methods. Like other sampling algorithms, discrete sampling suffers from the high computational burden in large-scale inference problems. We study the problem of sampling a discrete random variable with a high degree of dependency that is typical in large-scale Bayesian inference and graphical models, and propose an efficient approximate solution with a subsampling approach. We make a novel connection between the discrete sampling and Multi-Armed Bandits problems with a finite reward population and provide three algorithms with theoretical guarantees. Empirical evaluations show the robustness and efficiency of the approximate algorithms in both synthetic and real-world large-scale problems.
sampling  inverse-problems  rather-interesting  probability-theory  simulation  engineering-design  nudge-targets  consider:feature-discovery
12 weeks ago by Vaguery
[1707.05994] Computing Tutte Paths
Tutte paths are one of the most successful tools for attacking Hamiltonicity problems in planar graphs. Unfortunately, results based on them are non-constructive, as their proofs inherently use an induction on overlapping subgraphs and these overlaps hinder to bound the running time to a polynomial. For special cases however, computational results of Tutte paths are known: For 4-connected planar graphs, Tutte paths are in fact Hamiltonian paths and Chiba and Nishizeki showed how to compute such paths in linear time. For 3-connected planar graphs, Tutte paths have a more complicated structure, and it has only recently been shown that they can be computed in polynomial time. However, Tutte paths are defined for general 2-connected planar graphs and this is what most applications need. Unfortunately, no computational results are known. We give the first efficient algorithm that computes a Tutte path (for the general case of 2-connected planar graphs). One of the strongest existence results about such Tutte paths is due to Sanders, which allows to prescribe the end vertices and an intermediate edge of the desired path. Encompassing and strengthening all previous computational results on Tutte paths, we show how to compute this special Tutte path efficiently. Our method refines both, the results of Thomassen and Sanders, and avoids overlapping subgraphs by using a novel iterative decomposition along 2-separators. Finally, we show that our algorithm runs in quadratic time.
graph-theory  algorithms  representation  rather-interesting  to-understand  nudge-targets  consider:representation  consider:feature-discovery
january 2018 by Vaguery
[1710.04640] Hard and Easy Instances of L-Tromino Tilings
In this work we study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we indentify restrictions to the problem where either it remains NP-complete or it has a polynomial time algorithm. First we show that an aztec diamond of order n always has an L-tromino tiling if and only if n(n+1)≡0mod3; if an aztec diamond has at least two defects or holes, however, the problem of deciding a tiling is NP-complete. Then we study tilings of arbitrary regions where only 180∘ rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete, yet, if a region contains certain so-called "forbidden polyominoes" as subregions, then there exists a polynomial time algorithm for deciding a tiling.
polyominoes  tiling  benchmarking  rather-interesting  problem-solving  nudge-targets  consider:feature-discovery  updated
november 2017 by Vaguery
[1405.2378] Covering Folded Shapes
Can folding a piece of paper flat make it larger? We explore whether a shape S must be scaled to cover a flat-folded copy of itself. We consider both single folds and arbitrary folds (continuous piecewise isometries S→R2). The underlying problem is motivated by computational origami, and is related to other covering and fixturing problems, such as Lebesgue's universal cover problem and force closure grasps. In addition to considering special shapes (squares, equilateral triangles, polygons and disks), we give upper and lower bounds on scale factors for single folds of convex objects and arbitrary folds of simply connected objects.
computational-geometry  to-write  paper-folding  rather-interesting  nudge-targets  consider:algorithms  consider:feature-discovery
november 2017 by Vaguery
[1411.6371] Folding a Paper Strip to Minimize Thickness
In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.
paper-folding  computational-geometry  optimization  rather-interesting  to-write-about  to-simulate  nudge-targets  consider:feature-discovery
november 2017 by Vaguery
[1501.00561] A linear-time algorithm for the geodesic center of a simple polygon
Given two points in a simple polygon P of n vertices, its geodesic distance is the length of the shortest path that connects them among all paths that stay within P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack, Sharir and Rote [Disc. \& Comput. Geom. 89] showed an O(nlogn)-time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.
computational-complexity  computational-geometry  optimization  rather-interesting  algorithms  distance  nudge-targets  consider:rediscovery  consider:feature-discovery
november 2017 by Vaguery
[1604.08797] Ortho-polygon Visibility Representations of Embedded Graphs
An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding-preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if G has at most one crossing per edge (i.e., G is a 1-plane graph), an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute an OPVR of G whose vertex complexity is bounded by a constant in O(n) time. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be Ω(n). In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O(n) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs.
graph-layout  computational-geometry  optimization  rather-interesting  to-write-about  nudge-targets  consider:representation  consider:feature-discovery  algorithms  computational-complexity
november 2017 by Vaguery
[1609.06972] Minimal completely asymmetric (4,n)-regular matchstick graphs
A matchstick graph is a graph drawn with straight edges in the plane such that the edges have unit length, and non-adjacent edges do not intersect. We call a matchstick graph $(m,n)$-regular if every vertex has only degree $m$ or $n$. In this article we present the latest known $(4,n)$-regular matchstick graphs for $4\leq n\leq11$ with a minimum number of vertices and a completely asymmetric structure. We call a matchstick graph completely asymmetric, if the following conditions are complied. 1) The graph is rigid. 2) The graph has no point, rotational or mirror symmetry. 3) The graph has an asymmetric outer shape. 4) The graph can not be decomposed into rigid subgraphs and rearrange to a similar graph which contradicts to any of the other conditions.
computational-geometry  graph-theory  rather-interesting  purdy-pitchers  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery
october 2017 by Vaguery
[1512.03421] The extended 1-perfect trades in small hypercubes
An extended 1-perfect trade is a pair (T0,T1) of two disjoint binary distance-4 even-weight codes such that the set of words at distance 1 from T0 coincides with the set of words at distance 1 from T1. Such trade is called primary if any pair of proper subsets of T0 and T1 is not a trade. Using a computer-aided approach, we classify nonequivalent primary extended 1-perfect trades of length 10, constant-weight extended 1-perfect trades of length 12, and Steiner trades derived from them. In particular, all Steiner trades with parameters (5,6,12) are classified.
combinatorics  to-understand  graph-theory  strings  optimization  constraint-satisfaction  looking-to-see  nudge-targets  consider:looking-to-see  consider:classification  consider:feature-discovery
october 2017 by Vaguery
[1006.4176] Unknotting Unknots
A knot is an an embedding of a circle into three-dimensional space. We say that a knot is unknotted if there is an ambient isotopy of the embedding to a standard circle. By representing knots via planar diagrams, we discuss the problem of unknotting a knot diagram when we know that it is unknotted. This problem is surprisingly difficult, since it has been shown that knot diagrams may need to be made more complicated before they may be simplified. We do not yet know, however, how much more complicated they must get. We give an introduction to the work of Dynnikov who discovered the key use of arc--presentations to solve the problem of finding a way to detect the unknot directly from a diagram of the knot. Using Dynnikov's work, we show how to obtain a quadratic upper bound for the number of crossings that must be introduced into a sequence of unknotting moves. We also apply Dynnikov's results to find an upper bound for the number of moves required in an unknotting sequence.
knot-theory  rather-interesting  representation  algorithms  classification  nudge-targets  consider:looking-to-see  consider:feature-discovery
october 2017 by Vaguery
[1605.08396] Robust Downbeat Tracking Using an Ensemble of Convolutional Networks
In this paper, we present a novel state of the art system for automatic downbeat tracking from music signals. The audio signal is first segmented in frames which are synchronized at the tatum level of the music. We then extract different kind of features based on harmony, melody, rhythm and bass content to feed convolutional neural networks that are adapted to take advantage of each feature characteristics. This ensemble of neural networks is combined to obtain one downbeat likelihood per tatum. The downbeat sequence is finally decoded with a flexible and efficient temporal model which takes advantage of the metrical continuity of a song. We then perform an evaluation of our system on a large base of 9 datasets, compare its performance to 4 other published algorithms and obtain a significant increase of 16.8 percent points compared to the second best system, for altogether a moderate cost in test and training. The influence of each step of the method is studied to show its strengths and shortcomings.
neural-networks  music  deep-learning  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery
october 2017 by Vaguery
[cs/0302027] Tiling space and slabs with acute tetrahedra
We show it is possible to tile three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than 77.08∘, and another which tiles a slab in space.
computational-geometry  tiling  rather-interesting  constraint-satisfaction  nudge-targets  consider:feature-discovery  consider:simpler-planar-problem
october 2017 by Vaguery
[1406.5156] Pattern-avoiding permutations and Brownian excursion Part I: Shapes and fluctuations
Permutations that avoid given patterns are among the most classical objects in combinatorics and have strong connections to many fields of mathematics, computer science and biology. In this paper we study the scaling limits of a random permutation avoiding a pattern of length 3 and their relations to Brownian excursion. Exploring this connection to Brownian excursion allows us to strengthen the recent results of Madras and Pehlivan, and Miner and Pak as well as to understand many of the interesting phenomena that had previously gone unexplained.
permutations  combinatorics  review  rather-interesting  feature-extraction  ranimuladom-walks  simulation  nudge-targets  consider:feature-discovery
october 2017 by Vaguery
[1406.0670] Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance
We implement a decision procedure for answering questions about a class of infinite words that might be called (for lack of a better name) "Fibonacci-automatic". This class includes, for example, the famous Fibonacci word f = 01001010..., the fixed point of the morphism 0 -> 01 and 1 -> 0. We then recover many results about the Fibonacci word from the literature (and improve some of them), such as assertions about the occurrences in f of squares, cubes, palindromes, and so forth. As an application of our method we prove a new result: there exists an aperiodic infinite binary word avoiding the pattern x x x^R. This is the first avoidability result concerning a nonuniform morphism proven purely mechanically.
strings  combinatorics  classification  nudge-targets  consider:looking-to-see  consider:feature-discovery
october 2017 by Vaguery
New Shapes Solve Infinite Pool-Table Problem | Quanta Magazine
Two “rare jewels” have illuminated a mysterious multidimensional object that connects a huge variety of mathematical work.
dynamical-systems  geometry  rather-interesting  mathematical-recreations  nudge-targets  consider:looking-to-see  consider:feature-discovery
october 2017 by Vaguery
[1709.05701] Transkingdom Networks: A Systems Biology Approach to Identify Causal Members of Host-Microbiota Interactions
Improvements in sequencing technologies and reduced experimental costs have resulted in a vast number of studies generating high-throughput data. Although the number of methods to analyze these "omics" data has also increased, computational complexity and lack of documentation hinder researchers from analyzing their high-throughput data to its true potential. In this chapter we detail our data-driven, transkingdom network (TransNet) analysis protocol to integrate and interrogate multi-omics data. This systems biology approach has allowed us to successfully identify important causal relationships between different taxonomic kingdoms (e.g. mammals and microbes) using diverse types of data.
rather-interesting  bioinformatics  community-detection  symbiosis  machine-learning  to-write-about  consider:feature-discovery
october 2017 by Vaguery
[1404.6238] Recurrence and transience for the frog model on trees
The frog model is a growing system of random walks where a particle is added whenever a new site is visited. A longstanding open question is how often the root is visited on the infinite d-ary tree. We prove the model undergoes a phase transition, finding it recurrent for d=2 and transient for d≥5. Simulations suggest strong recurrence for d=2, weak recurrence for d=3, and transience for d≥4. Additionally, we prove a 0-1 law for all d-ary trees, and we exhibit a graph on which a 0-1 law does not hold.
To prove recurrence when d=2, we construct a recursive distributional equation for the number of visits to the root in a smaller process and show the unique solution must be infinity a.s. The proof of transience when d=5 relies on computer calculations for the transition probabilities of a large Markov chain. We also include the proof for d≥6, which uses similar techniques but does not require computer assistance.
probability-theory  graph-theory  random-walks  dynamical-systems  rather-interesting  to-understand  to-write-about  consider:feature-discovery  consider:classification
october 2017 by Vaguery
[1608.08087] Equisectional equivalence of triangles
We study equivalence relation of the set of triangles generated by similarity and operation on a triangle to get a new one by joining division points of three edges with the same ratio. Using the moduli space of similarity classes of triangles introduced by Nakamura and Oguiso, we give characterization of equivalent triangles in terms of circles of Apollonius (or hyperbolic pencil of circles) and properties of special equivalent triangles. We also study rationality problem and constructibility problem.
plane-geometry  compass-and-straightedge  looking-to-see  rather-interesting  algebra  nudge-targets  consider:feature-discovery
october 2017 by Vaguery
Unsupervised Sentiment Neuron
It’s interesting to note that the system also makes large updates after the completion of sentences and phrases. For example, in “And about 99.8 percent of that got lost in the film”, there’s a negative update after “lost” and a larger update at the sentence’s end, even though “in the film” has no sentiment content on its own.
sentiment-analysis  neural-networks  machine-learning  natural-language-processing  rather-interesting  to-write-about  consider:cause-and-effect  consider:feature-discovery
september 2017 by Vaguery
[1606.02220] Non-aligned drawings of planar graphs
A non-aligned drawing of a graph is a drawing where no two vertices are in the same row or column. Auber et al. showed that not all planar graphs have non-aligned drawings that are straight-line, planar, and in the minimal-possible n×n-grid. They also showed that such drawings exist if up to n−3 edges may have a bend. In this paper, we give algorithms for non-aligned planar drawings that improve on the results by Auber et al. In particular, we give such drawings in an n×n-grid with significantly fewer bends, and we study what grid-size can be achieved if we insist on having straight-line drawings
graph-layout  computational-geometry  algorithms  constraint-satisfaction  rather-interesting  to-write-about  multiobjective-optimization  nudge-targets  consider:feature-discovery
september 2017 by Vaguery
[0801.3306] Chip-Firing and Rotor-Routing on Directed Graphs
We give a rigorous and self-contained survey of the abelian sandpile model and rotor-router model on finite directed graphs, highlighting the connections between them. We present several intriguing open problems.
sandpiles  complexology  graph-theory  dynamical-systems  feature-construction  to-write-about  nudge-targets  consider:classification  consider:feature-discovery
september 2017 by Vaguery
[1709.05769] Where to Focus: Deep Attention-based Spatially Recurrent Bilinear Networks for Fine-Grained Visual Recognition
Fine-grained visual recognition typically depends on modeling subtle difference from object parts. However, these parts often exhibit dramatic visual variations such as occlusions, viewpoints, and spatial transformations, making it hard to detect. In this paper, we present a novel attention-based model to automatically, selectively and accurately focus on critical object regions with higher importance against appearance variations. Given an image, two different Convolutional Neural Networks (CNNs) are constructed, where the outputs of two CNNs are correlated through bilinear pooling to simultaneously focus on discriminative regions and extract relevant features. To capture spatial distributions among the local regions with visual attention, soft attention based spatial Long-Short Term Memory units (LSTMs) are incorporated to realize spatially recurrent yet visually selective over local input patterns. All the above intuitions equip our network with the following novel model: two-stream CNN layers, bilinear pooling layer, spatial recurrent layer with location attention are jointly trained via an end-to-end fashion to serve as the part detector and feature extractor, whereby relevant features are localized and extracted attentively. We show the significance of our network against two well-known visual recognition tasks: fine-grained image classification and person re-identification.
image-processing  neural-networks  attention  feature-extraction  deep-learning  architecture  constraint-satisfaction  nudge-targets  consider:feature-discovery  consider:representation
september 2017 by Vaguery
[1703.04159] Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm
The problem of finding conflict-free trajectories for multiple agents of identical circular shape, operating in shared 2D workspace, is addressed in the paper and decoupled, e.g., prioritized, approach is used to solve this problem. Agents' workspace is tessellated into the square grid on which any-angle moves are allowed, e.g. each agent can move into an arbitrary direction as long as this move follows the straight line segment whose endpoints are tied to the distinct grid elements. A novel any-angle planner based on Safe Interval Path Planning (SIPP) algorithm is proposed to find trajectories for an agent moving amidst dynamic obstacles (other agents) on a grid. This algorithm is then used as part of a prioritized multi-agent planner AA-SIPP(m). On the theoretical, side we show that AA-SIPP(m) is complete under well-defined conditions. On the experimental side, in simulation tests with up to 200 agents involved, we show that our planner finds much better solutions in terms of cost (up to 20%) compared to the planners relying on cardinal moves only.
collective-intelligence  planning  constraint-satisfaction  algorithms  representation  nudge-targets  consider:feature-discovery
september 2017 by Vaguery
[1212.0649] Optimal packings of congruent circles on a square flat torus
We consider packings of congruent circles on a square flat torus, i.e., periodic (w.r.t. a square lattice) planar circle packings, with the maximal circle radius. This problem is interesting due to a practical reason - the problem of "super resolution of images." We have found optimal arrangements for N=6, 7 and 8 circles. Surprisingly, for the case N=7 there are three different optimal arrangements. Our proof is based on a computer enumeration of toroidal irreducible contact graphs.
packing  computational-geometry  optimization  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery  plane-geometry
september 2017 by Vaguery
[1709.01456] Improved Bounds for Drawing Trees on Fixed Points with L-shaped Edges
Let T be an n-node tree of maximum degree 4, and let P be a set of n points in the plane with no two points on the same horizontal or vertical line. It is an open question whether T always has a planar drawing on P such that each edge is drawn as an orthogonal path with one bend (an "L-shaped" edge). By giving new methods for drawing trees, we improve the bounds on the size of the point set P for which such drawings are possible to: O(n1.55) for maximum degree 4 trees; O(n1.22) for maximum degree 3 (binary) trees; and O(n1.142) for perfect binary trees.
Drawing ordered trees with L-shaped edges is harder---we give an example that cannot be done and a bound of O(nlogn) points for L-shaped drawings of ordered caterpillars, which contrasts with the known linear bound for unordered caterpillars.
graph-layout  computational-geometry  algorithms  rather-interesting  representation  visualization  hard-problems  nudge-targets  constraint-satisfaction  consider:feature-discovery
september 2017 by Vaguery
[1704.06456] A Domain Based Approach to Social Relation Recognition
Social relations are the foundation of human daily life. Developing techniques to analyze such relations from visual data bears great potential to build machines that better understand us and are capable of interacting with us at a social level. Previous investigations have remained partial due to the overwhelming diversity and complexity of the topic and consequently have only focused on a handful of social relations. In this paper, we argue that the domain-based theory from social psychology is a great starting point to systematically approach this problem. The theory provides coverage of all aspects of social relations and equally is concrete and predictive about the visual attributes and behaviors defining the relations included in each domain. We provide the first dataset built on this holistic conceptualization of social life that is composed of a hierarchical label space of social domains and social relations. We also contribute the first models to recognize such domains and relations and find superior performance for attribute based features. Beyond the encouraging performance of the attribute based approach, we also find interpretable features that are in accordance with the predictions from social psychology literature. Beyond our findings, we believe that our contributions more tightly interleave visual recognition and social psychology theory that has the potential to complement the theoretical work in the area with empirical and data-driven models of social life.
image-processing  computer-vision  machine-learning  representation  social-psychology  rather-interesting  to-write-about  consider:feature-discovery
september 2017 by Vaguery
Magnetism – The Inner Frame
Magnetism is played by two players on a strip of squares, who take turns placing + and – tokens onto the strip. The only rule is that no two tokens with the same parity can be placed next to each other.
simple-games  game-theory  to-write-about  consider:looking-to-see  nudge-targets  consider:feature-discovery
september 2017 by Vaguery
[1609.00147] Two-connected spanning subgraphs with at most $frac{10}{7}$OPT edges
We present a 107-approximation algorithm for the minimum two-vertex-connected spanning subgraph problem.
graph-theory  nudge-targets  consider:looking-to-see  consider:feature-discovery
august 2017 by Vaguery
Heesch Numbers, Part 2: Polyforms – Isohedral
In the first post in this series, I introduced the concept of a shape’s Heesch number. In brief, if a shape doesn’t tile the plane, its Heesch number is a measure of the maximum number of times you can surround the shape with layers of copies of itself. (Shapes that do tile are defined to have a Heesch number of infinity.) Shapes with positive, finite Heesch numbers are entertaining mathematical curiosities. Far more mysterious—and infuriating—is the fact that we know of examples of Heesch numbers only up to five, and nothing higher. Learning more about shapes with high Heesch numbers could offer insights into deep unsolved problems in tiling theory.
tiling  combinatorics  mathematical-recreations  rather-interesting  number-theory  looking-to-see  nudge-targets  consider:feature-discovery  to-write-about
august 2017 by Vaguery
[1705.00759] Controllability of Conjunctive Boolean Networks with Application to Gene Regulation
A Boolean network is a finite state discrete time dynamical system. At each step, each variable takes a value from a binary set. The value update rule for each variable is a local function which depends only on a selected subset of variables. Boolean networks have been used in modeling gene regulatory networks. We focus in this paper on a special class of Boolean networks, namely the conjunctive Boolean networks (CBNs), whose value update rule is comprised of only logic AND operations. It is known that any trajectory of a Boolean network will enter a periodic orbit. Periodic orbits of a CBN have been completely understood. In this paper, we investigate the orbit-controllability and state-controllability of a CBN: We ask the question of how one can steer a CBN to enter any periodic orbit or to reach any final state, from any initial state. We establish necessary and sufficient conditions for a CBN to be orbit-controllable and state-controllable. Furthermore, explicit control laws are presented along the analysis.
boolean-networks  Kauffmania  engineering-design  emergent-design  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery  dynamical-systems  complexology
august 2017 by Vaguery
Dynamics Robustness of Cascading Systems | bioRxiv
A most important property of biochemical systems is robustness. Static robustness, e.g., homeostasis, is the insensitivity of a state against perturbations, whereas dynamics robustness, e.g., homeorhesis, is the insensitivity of a dynamic process. In contrast to the extensively studied static robustness, dynamics robustness, i.e., how a system creates an invariant temporal profile against perturbations, is little explored despite transient dynamics being crucial for cellular fates and are reported to be robust experimentally. For example, the duration of a stimulus elicits different phenotypic responses, and signaling networks process and encode temporal information. Hence, robustness in time courses will be necessary for functional biochemical networks. Based on dynamical systems theory, we uncovered a general mechanism to achieve dynamics robustness. Using a three-stage linear signaling cascade as an example, we found that the temporal profiles and response duration post-stimulus is robust to perturbations against certain parameters. Then analyzing the linearized model, we elucidated the criteria of how such dynamics robustness emerges in signaling networks. We found that changes in the upstream modules are masked in the cascade, and that the response duration is mainly controlled by the rate-limiting module and organization of the cascade's kinetics. Specifically, we found two necessary conditions for dynamics robustness in signaling cascades: 1) Constraint on the rate-limiting process: The phosphatase activity in the perturbed module is not the slowest. 2) Constraints on the initial conditions: The kinase activity needs to be fast enough such that each module is saturated even with fast phosphatase activity and upstream information is attenuated. We discussed the relevance of such robustness to several biological examples and the validity of the above conditions therein. Given the applicability of dynamics robustness to a variety of systems, it will provide a general basis for how biological systems function dynamically.
robustness  systems-biology  self-organization  complexology  nonlinear-dynamics  emergent-design  to-write-about  nudge-targets  consider:feature-discovery
june 2017 by Vaguery
[math/0608131] Many sets have more sums than differences
Since addition is commutative but subtraction is not, the sumset S+S of a finite set S is predisposed to be smaller than the difference set S-S. In this paper, however, we show that each of the three possibilities (|S+S|>|S-S|, |S+S|=|S-S|, |S+S|<|S-S|) occur for a positive proportion of the subsets of {0, 1, ..., n-1}. We also show that the difference |S+S| - |S-S| can take any integer value, and we show that the expected number of omitted differences is asymptotically 6 while the expected number of missing sums is asymptotically 10. Other data and conjectures on the distribution of these quantities are also given.
number-theory  rather-interesting  to-write-about  experiment  nudge-targets  consider:feature-discovery
june 2017 by Vaguery
[math/0608148] Sets with more sums than differences
Let A be a finite subset of the integers or, more generally, of any abelian group, written additively. The set A has "more sums than differences" if |A+A|>|A-A|. A set with this property is called an MSTD set. This paper gives explicit constructions of families of MSTD sets of integers.
number-theory  enumeration  combinatorics  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery
june 2017 by Vaguery
[1108.4500] Generalized More Sums Than Differences Sets
A More Sums Than Differences (MSTD, or sum-dominant) set is a finite set A⊂ℤ such that |A+A|<|A−A|. Though it was believed that the percentage of subsets of {0,...,n} that are sum-dominant tends to zero, in 2006 Martin and O'Bryant \cite{MO} proved a positive percentage are sum-dominant. We generalize their result to the many different ways of taking sums and differences of a set. We prove that |ϵ1A+...+ϵkA|>|δ1A+...+δkA| a positive percent of the time for all nontrivial choices of ϵj,δj∈{−1,1}. Previous approaches proved the existence of infinitely many such sets given the existence of one; however, no method existed to construct such a set. We develop a new, explicit construction for one such set, and then extend to a positive percentage of sets.
We extend these results further, finding sets that exhibit different behavior as more sums/differences are taken. For example, notation as above we prove that for any m, |ϵ1A+...+ϵkA|−|δ1A+...+δkA|=m a positive percentage of the time. We find the limiting behavior of kA=A+...+A for an arbitrary set A as k→∞ and an upper bound of k for such behavior to settle down. Finally, we say A is k-generational sum-dominant if A, A+A, ...,kA are all sum-dominant. Numerical searches were unable to find even a 2-generational set (heuristics indicate the probability is at most 10−9, and almost surely significantly less). We prove the surprising result that for any k a positive percentage of sets are k-generational, and no set can be k-generational for all k.
number-theory  rather-interesting  to-write-about  enumeration  nudge-targets  consider:feature-discovery
june 2017 by Vaguery
[1705.00241] Dynamic interdependence and competition in multilayer networks
From critical infrastructure, to physiology and the human brain, complex systems rarely occur in isolation. Instead, the functioning of nodes in one system often promotes or suppresses the functioning of nodes in another. Despite advances in structural interdependence, modeling interdependence and other interactions between dynamic systems has proven elusive. Here we define a broadly applicable dynamic dependency link and develop a general framework for interdependent and competitive interactions between general dynamic systems. We apply our framework to studying interdependent and competitive synchronization in multi-layer oscillator networks and cooperative/competitive contagions in an epidemic model. Using a mean-field theory which we verify numerically, we find explosive transitions and rich behavior which is absent in percolation models including hysteresis, multi-stability and chaos. The framework presented here provides a powerful new way to model and understand many of the interacting complex systems which surround us.
dynamical-systems  coupled-oscillators  network-theory  rather-interesting  to-write-about  simulation  consider:simple-examples  nudge-targets  consider:control-theory  consider:feature-discovery
may 2017 by Vaguery
[1611.05321] Bootstrap, Review, Decode: Using Out-of-Domain Textual Data to Improve Image Captioning
We propose a novel way of using out-of-domain textual data to enhance the performance of existing image captioning systems. We evaluate this learning approach on a newly designed model that uses - and improves upon - building blocks from state-of-the-art methods. This model starts from detecting visual concepts present in an image which are then fed to a reviewer-decoder architecture with an attention mechanism. Unlike previous approaches that encode visual concepts using word embeddings, we instead suggest using regional image features which capture more intrinsic information. The main benefit of this architecture is that it synthesizes meaningful thought vectors that capture salient image properties and then applies a soft attentive decoder to decode the thought vectors and generate image captions. We evaluate our model on both Microsoft COCO and Flickr30K datasets and demonstrate that this model combined with our bootstrap learning method can largely improve performance and help the model to generate more accurate and diverse captions.
data-fusion  image-processing  deep-learning  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery
may 2017 by Vaguery
[1607.01196] Drawing Graphs on Few Lines and Few Planes
We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows.
We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values.
We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing).
We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.
graph-layout  computational-geometry  optimization  graph-theory  topology  rather-interesting  to-write-about  consider:feature-discovery  nudge-targets  consider:classification
may 2017 by Vaguery
[1404.7493] Drawdown: From Practice to Theory and Back Again
Maximum drawdown, the largest cumulative loss from peak to trough, is one of the most widely used indicators of risk in the fund management industry, but one of the least developed in the context of measures of risk. We formalize drawdown risk as Conditional Expected Drawdown (CED), which is the tail mean of maximum drawdown distributions. We show that CED is a degree one positive homogenous risk measure, so that it can be linearly attributed to factors; and convex, so that it can be used in quantitative optimization. We empirically explore the differences in risk attributions based on CED, Expected Shortfall (ES) and volatility. An important feature of CED is its sensitivity to serial correlation. In an empirical study that fits AR(1) models to US Equity and US Bonds, we find substantially higher correlation between the autoregressive parameter and CED than with ES or with volatility.
portfolio-theory  performance-measure  financial-engineering  multiobjective-optimization  consider:feature-discovery  to-write-about  algorithms  representation
may 2017 by Vaguery
[1311.6511] Intransitive Dice
We consider n-sided dice whose face values lie between 1 and n and whose faces sum to n(n+1)/2. For two dice A and B, define A≻B if it is more likely for A to show a higher face than B. Suppose k such dice A1,…,Ak are randomly selected. We conjecture that the probability of ties goes to 0 as n grows. We conjecture and provide some supporting evidence that---contrary to intuition---each of the 2(k2) assignments of ≻ or ≺ to each pair is equally likely asymptotically. For a specific example, suppose we randomly select k dice A1,…,Ak and observe that A1≻A2≻…≻Ak. Then our conjecture asserts that the outcomes Ak≻A1 and A1≺Ak both have probability approaching 1/2 as n→∞.
combinatorics  mathematical-recreations  probability-theory  to-write-about  nudge-targets  consider:engineering-design  consider:feature-discovery
may 2017 by Vaguery
[1505.07363] An Enumeration of the Equivalence Classes of Self-Dual Matrix Codes
As a result of their applications in network coding, space-time coding, and coding for criss-cross errors, matrix codes have garnered significant attention; in various contexts, these codes have also been termed rank-metric codes, space-time codes over finite fields, and array codes. We focus on characterizing matrix codes that are both efficient (have high rate) and effective at error correction (have high minimum rank-distance). It is well known that the inherent trade-off between dimension and minimum distance for a matrix code is reversed for its dual code; specifically, if a matrix code has high dimension and low minimum distance, then its dual code will have low dimension and high minimum distance. With an aim towards finding codes with a perfectly balanced trade-off, we study self-dual matrix codes. In this work, we develop a framework based on double cosets of the matrix-equivalence maps to provide a complete classification of the equivalence classes of self-dual matrix codes, and we employ this method to enumerate the equivalence classes of these codes for small parameters.
information-theory  matrices  combinatorics  rather-interesting  to-write-about  nudge-targets  consider:feature-discovery  consider:rediscovery
may 2017 by Vaguery
[1704.08798] Word Affect Intensities
Words often convey affect -- emotions, feelings, and attitudes. Lexicons of word-affect association have applications in automatic emotion analysis and natural language generation. However, existing lexicons indicate only coarse categories of affect association. Here, for the first time, we create an affect intensity lexicon with real-valued scores of association. We use a technique called best-worst scaling that improves annotation consistency and obtains reliable fine-grained scores. The lexicon includes terms common from both general English and terms specific to social media communications. It has close to 6,000 entries for four basic emotions. We will be adding entries for other affect dimensions shortly.
natural-language-processing  looking-to-see  affect  rather-interesting  to-write-about  consider:feature-discovery
may 2017 by Vaguery
[1703.01143] Why is it hard to beat $O(n^2)$ for Longest Common Weakly Increasing Subsequence?
The Longest Common Weakly Increasing Subsequence problem (LCWIS) is a variant of the classic Longest Common Subsequence problem (LCS). Both problems can be solved with simple quadratic time algorithms. A recent line of research led to a number of matching conditional lower bounds for LCS and other related problems. However, the status of LCWIS remained open.
In this paper we show that LCWIS cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis (SETH) is false.
The ideas which we developed can also be used to obtain a lower bound based on a safer assumption of NC-SETH, i.e. a version of SETH which talks about NC circuits instead of less expressive CNF formulas.
computational-complexity  robustness  algorithms  looking-to-see  rather-interesting  to-write-about  extreme-values  outliers  hard-problems  feature-construction  nudge-targets  consider:feature-discovery
may 2017 by Vaguery
[1610.01861] Efficient Best-Response Computation for Strategic Network Formation under Attack
Strategic network formation models the uncoordinated creation of a network by selfish agents. Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Most of these games have the conceptual drawback of being computationally intractable. For example, computing a best response strategy or checking whether an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find models which incorporate many interesting features and to devise efficient algorithms for solving the entailed computational tasks.
We address this challenge by providing an efficient algorithm to compute a best response strategy for a recently introduced model, thereby answering the open question posed by Goyal et al. [WINE'16]. Their promising model focuses on network robustness by considering an adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes.
Additionally, we augment their model by introducing a less predictable adversary and show that our algorithm, with minor modifications, can cope with this more complex scenario.
community-formation  network-theory  self-organization  rather-interesting  to-write-about  consider:feature-discovery
april 2017 by Vaguery
[1704.07510] Knotting probability and the scaling behavior of self-avoiding polygons under a topological constraint
We define the knotting probability of a knot K by the probability for a random polygon (RP) or self-avoiding polygon (SAP) with N segments having the knot type K. As a model of circular DNA we introduce the SAP consisting of impenetrable cylindrical segments of unit length in which the radius rex of segments corresponds to the screening length of DNA surrounded by counter ions. For various prime and composite knots we numerically show that a compact formula gives good fitted curves to the data of the knotting probabilities for the cylindrical SAP as a function of segment number N and cylindrical radius rex. It connects the small-N to the large-N regions and even to lattice knots for large values of radius rex such as satisfying 2rex=1/4. We suggest that if radius rex is large, the trefoil knot and its composite knots are dominant among the nontrivial knots in SAPs. We then study topological swelling that the mean-square radius of gyration of the cylindrical SAP with fixed knot is much larger than that of under no topological constraint if radius rex is small and N is large enough. We argue that the finite-size effect is significant in it where the characteristic length of the knotting probability gives the topological scale. We show that for any value of radius rex a three-parameter formula gives a good fitted curve to the plot of the mean-square gyration radius of the cylindrical SAP with a given knot K against segment number N. With the curves we evaluate the effective scaling exponent. We suggest that it increases with respect to the upper limit of N and gradually approaches the scaling exponent of self-avoiding walks even in the case of zero thickness as the upper limit of N becomes infinitely large.
knot-theory  inference  rather-interesting  prediction  probability-theory  nudge-targets  consider:looking-to-see  consider:rediscovery  consider:feature-discovery
april 2017 by Vaguery
[1606.07104] Manifolds' Projective Approximation Using The Moving Least-Squares (MMLS)
In order to avoid the curse of dimensionality, frequently encountered in Big Data analysis, there was a vast development in the field of linear and non-linear dimension reduction techniques in recent years. These techniques (sometimes referred to as manifold learning) assume that the scattered input data is lying on a lower dimensional manifold, thus the high dimensionality problem can be overcome by learning the lower dimensionality behavior. However, in real life applications, data is often very noisy. In this work, we propose a method to approximate a d-dimensional Cm+1 smooth submanifold  residing in ℝn (d<<n) based upon scattered data points (i.e., a data cloud). We assume that the data points are located "near" the noisy lower dimensional manifold and perform a non-linear moving least-squares projection on an approximating manifold. Under some mild assumptions, the resulting approximant is shown to be infinitely smooth and of high approximation order (i.e., O(hm+1), where h is the fill distance and m is the degree of the local polynomial approximation). Furthermore, the method presented here assumes no analytic knowledge of the approximated manifold and the approximation algorithm is linear in the large dimension n.
models  machine-learning  curse-of-dimensionality  compressed-sensing  feature-extraction  nudge-targets  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[1308.0419] Inverse Procedural Modeling of Facade Layouts
In this paper, we address the following research problem: How can we generate a meaningful split grammar that explains a given facade layout? To evaluate if a grammar is meaningful, we propose a cost function based on the description length and minimize this cost using an approximate dynamic programming framework. Our evaluation indicates that our framework extracts meaningful split grammars that are competitive with those of expert users, while some users and all competing automatic solutions are less successful.
grammar  L-systems  generative-models  image-processing  learning-from-data  machine-learning  inverse-problems  nudge-targets  consider:representation  consider:feature-discovery
april 2017 by Vaguery
[1110.5348] Packing Squares in a Torus
The densest packings of N unit squares in a torus are studied using analytical methods as well as simulated annealing. A rich array of dense packing solutions are found: density-one packings when N is the sum of two square integers; a family of "gapped bricklayer" Bravais lattice solutions with density N/(N+1); and some surprising non-Bravais lattice configurations, including lattices of holes as well as a configuration for N=23 in which not all squares share the same orientation. The entropy of some of these configurations and the frequency and orientation of density-one solutions as N goes to infinity are discussed.
packing  topology  optimization  rather-interesting  simulation  nudge-targets  consider:feature-discovery  consider:looking-to-see
april 2017 by Vaguery
[1312.1793] "Nice" Rational Functions
We consider simple rational functions Rmn(x)=Pm(x)/Qn(x), with Pm and Qn polynomials of degree m and n respectively. We look for "nice" functions, which we define to be ones where as many as possible of the roots, poles, critical points and (possibly) points of inflexion are integer or, at worst, rational.
algebra  number-theory  rather-interesting  constraint-satisfaction  stamp-collecting  nudge-targets  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[1612.06701] A family of multimagic squares based on large sets of orthogonal arrays
Large set of orthogonal arrays (LOA) were introduced by D. R. Stinson, and it is also used to construct multimagic squares recently. In this paper, multimagic squares based on strong double LOA are further investigated. It is proved that there exists an MS(q2t−1,t) for any prime power q≥2t−1 with t≥3, which provided a new family of multimagic squares.
combinatorics  magic-squares  constraint-satisfaction  mathematical-recreations  number-theory  rather-interesting  nudge-targets  consider:generalizations  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[1505.02547] The $plambda n$ fractal decomposition: Nontrivial partitions of conserved physical quantities
A mathematical method for constructing fractal curves and surfaces, termed the pλn fractal decomposition, is presented. It allows any function to be split into a finite set of fractal discontinuous functions whose sum is equal everywhere to the original function. Thus, the method is specially suited for constructing families of fractal objects arising from a conserved physical quantity, the decomposition yielding an exact partition of the quantity in question. Most prominent classes of examples are provided by Hamiltonians and partition functions of statistical ensembles: By using this method, any such function can be decomposed in the ordinary sum of a specified number of terms (generally fractal functions), the decomposition being both exact and valid everywhere on the domain of the function.
representation  composition  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[1212.6102] On Curling Numbers of Integer Sequences
Given a finite nonempty sequence S of integers, write it as XY^k, where Y^k is a power of greatest exponent that is a suffix of S: this k is the curling number of S. The Curling Number Conjecture is that if one starts with any initial sequence S, and extends it by repeatedly appending the curling number of the current sequence, the sequence will eventually reach 1. The conjecture remains open. In this paper we discuss the special case when S consists just of 2's and 3's. Even this case remains open, but we determine how far a sequence of n 2's and 3's can extend before reaching a 1, conjecturally for n <= 80. We investigate several related combinatorial problems, such as finding c(n,k), the number of binary sequences of length n and curling number k, and t(n,i), the number of sequences of length n which extend for i steps before reaching a 1. A number of interesting combinatorial problems remain unsolved.
combinatorics  rather-interesting  sequences  open-questions  nudge-targets  consider:looking-to-see  consider:feature-discovery  consider:rediscovery  to-write-about
april 2017 by Vaguery
[1307.0453] 2178 And All That
For integers g >= 3, k >= 2, call a number N a (g,k)-reverse multiple if the reversal of N in base g is equal to k times N. The numbers 1089 and 2178 are the two smallest (10,k)-reverse multiples, their reversals being 9801 = 9x1089 and 8712 = 4x2178. In 1992, A. L. Young introduced certain trees in order to study the problem of finding all (g,k)-reverse multiples. By using modified versions of her trees, which we call Young graphs, we determine the possible values of k for bases g = 2 through 100, and then show how to apply the transfer-matrix method to enumerate the (g,k)-reverse multiples with a given number of base-g digits. These Young graphs are interesting finite directed graphs, whose structure is not at all well understood.
number-theory  rather-interesting  feature-construction  mathematical-recreations  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[1004.3036] The Toothpick Sequence and Other Sequences from Cellular Automata
A two-dimensional arrangement of toothpicks is constructed by the following iterative procedure. At stage 1, place a single toothpick of length 1 on a square grid, aligned with the y-axis. At each subsequent stage, for every exposed toothpick end, place an orthogonal toothpick centered at that end. The resulting structure has a fractal-like appearance. We will analyze the toothpick sequence, which gives the total number of toothpicks after n steps. We also study several related sequences that arise from enumerating active cells in cellular automata. Some unusual recurrences appear: a typical example is that instead of the Fibonacci recurrence, which we may write as a(2+i) = a(i) + a(i+1), we set n = 2^k+i (0 <= i < 2^k), and then a(n)=a(2^k+i)=2a(i)+a(i+1). The corresponding generating functions look like Prod{k >= 0} (1+x^{2^k-1}+2x^{2^k}) and variations thereof.
combinatorics  cellular-automata  mathematical-recreations  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery  sequences  number-theory
april 2017 by Vaguery
[0912.2394] Seven Staggering Sequences
When my "Handbook of Integer Sequences" came out in 1973, Philip Morrison gave it an enthusiastic review in the Scientific American and Martin Gardner was kind enough to say in his Mathematical Games column that "every recreational mathematician should buy a copy forthwith." That book contained 2372 sequences. Today the "On-Line Encyclopedia of Integer Sequences" contains 117000 sequences. This paper will describe seven that I find especially interesting. These are the EKG sequence, Gijswijt's sequence, a numerical analog of Aronson's sequence, approximate squaring, the integrality of n-th roots of generating functions, dissections, and the kissing number problem. (Paper for conference in honor of Martin Gardner's 91st birthday.)
combinatorics  Martin-Gardner  mathematical-recreations  sequences  number-theory  nudge-targets  to-write-about  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[math/0611293] Descending Dungeons and Iterated Base-Changing
For real numbers a, b> 1, let as a_b denote the result of interpreting a in base b instead of base 10. We define dungeons'' (as opposed to towers'') to be numbers of the form a_b_c_d_..._e, parenthesized either from the bottom upwards (preferred) or from the top downwards. Among other things, we show that the sequences of dungeons with n-th terms 10_11_12_..._(n-1)_n or n_(n-1)_..._12_11_10 grow roughly like 10^{10^{n log log n}}, where the logarithms are to the base 10. We also investigate the behavior as n increases of the sequence a_a_a_..._a, with n a's, parenthesized from the bottom upwards. This converges either to a single number (e.g. to the golden ratio if a = 1.1), to a two-term limit cycle (e.g. if a = 1.05) or else diverges (e.g. if a = frac{100{99).
number-theory  mathematical-recreations  representation  rather-interesting  to-write-about  nudge-targets  consider:representation  consider:feature-discovery  sequences
april 2017 by Vaguery
[1101.4274] 10 conjectures in additive number theory
Following an idea of Rowland we give a conjectural way to generate increasing sequences of primes using algorithms involving the gcd. These algorithms seem not so useless for searching primes since it appears we found sometime primes much more greater than the number of required iterations. In an other hand we propose new formulations of famous conjectures from the additive theory of numbers (the weak twin prime conjecture, the Polignac conjecture, the Goldbach conjecture or the very general Schinzel's hypothesis H). For the moment these are experimental results obtained using pari-gp.
number-theory  conjecture  open-questions  nudge-targets  consider:looking-to-see  consider:feature-discovery  consider:rediscovery
april 2017 by Vaguery
[math/0305308] Numerical Analogues of Aronson's Sequence
Aronson's sequence 1, 4, 11, 16, ... is defined by the English sentence t is the first, fourth, eleventh, sixteenth, ... letter of this sentence.'' This paper introduces some numerical analogues, such as: a(n) is taken to be the smallest positive integer greater than a(n-1) which is consistent with the condition n is a member of the sequence if and only if a(n) is odd.'' This sequence can also be characterized by its square'', the sequence a^(2)(n) = a(a(n)), which equals 2n+3 for n >= 1. There are many generalizations of this sequence, some of which are new, while others throw new light on previously known sequences.
number-theory  sequences  looking-to-see  define-your-terms  nudge-targets  consider:feature-discovery  consider:performance-measures
april 2017 by Vaguery
[math/0505295] Sloping Binary Numbers: A New Sequence Related to the Binary Numbers
If the list of binary numbers is read by upward-sloping diagonals, the resulting sloping binary numbers'' 0, 11, 110, 101, 100, 1111, 1010, ... (or 0, 3, 6, 5, 4, 15, 10, ...) have some surprising properties. We give formulae for the n-th term and the n-th missing term, and discuss a number of related sequences.
april 2017 by Vaguery
[1212.5106] Balance properties of Arnoux-Rauzy words
The paper deals with balances and imbalances in Arnoux-Rauzy words. We provide sufficient conditions for C-balancedness, but our results indicate that even a characterization of 2-balanced Arnoux-Rauzy words on a 3-letter alphabet is not immediate.
strings  formal-languages  to-understand  dynamical-systems  substitution-systems  rewriting-systems  nudge-targets  consider:looking-to-see  consider:feature-discovery
april 2017 by Vaguery
[1607.04474] The Influence of Canalization on the Robustness of Boolean Networks
Time- and state-discrete dynamical systems are frequently used to model molecular networks. This paper provides a collection of mathematical and computational tools for the study of robustness in Boolean network models. The focus is on networks governed by k-canalizing functions, a recently introduced class of Boolean functions that contains the well-studied class of nested canalizing functions. The activities and sensitivity of a function quantify the impact of input changes on the function output. This paper generalizes the latter concept to c-sensitivity and provides formulas for the activities and c-sensitivity of general k-canalizing functions as well as canalizing functions with more precisely defined structure. A popular measure for the robustness of a network, the Derrida value, can be expressed as a weighted sum of the c-sensitivities of the governing canalizing functions, and can also be calculated for a stochastic extension of Boolean networks. These findings provide a computationally efficient way to obtain Derrida values of Boolean networks, deterministic or stochastic, that does not involve simulation.
boolean-networks  Kauffmania  nonlinear-dynamics  complexology  systems-biology  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery  open-questions
april 2017 by Vaguery
[1305.2537] On Creativity of Elementary Cellular Automata
We map cell-state transition rules of elementary cellular automata (ECA) onto the cognitive control versus schizotypy spectrum phase space and interpret cellular automaton behaviour in terms of creativity. To implement the mapping we draw analogies between a degree of schizotypy and generative diversity of ECA rules, and between cognitive control and robustness of ECA rules (expressed via Derrida coefficient). We found that null and fixed point ECA rules lie in the autistic domain and chaotic rules are 'schizophrenic'. There are no highly articulated 'creative' ECA rules. Rules closest to 'creativity' domains are two-cycle rules exhibiting wave-like patterns in the space-time evolution.
hey-I-know-this-guy  cellular-automata  emergent-design  complexology  stamp-collecting  to-write-about  consider:feature-discovery
march 2017 by Vaguery
[1606.06940] Minimum Rectilinear Polygons for Given Angle Sequences
A rectilinear polygon is a polygon whose edges are axis-aligned. Walking counterclockwise on the boundary of such a polygon yields a sequence of left turns and right turns. The number of left turns always equals the number of right turns plus 4. It is known that any such sequence can be realized by a rectilinear polygon. In this paper, we consider the problem of finding realizations that minimize the perimeter or the area of the polygon or the area of the bounding box of the polygon. We show that all three problems are NP-hard in general. Then we consider the special cases of x-monotone and xy-monotone rectilinear polygons. For these, we can optimize the three objectives efficiently.
optimization  computational-geometry  inverse-problems  rather-interesting  constraint-satisfaction  nudge-targets  consider:looking-to-see  consider:feature-discovery
march 2017 by Vaguery
[1509.02627] Rectilinear convex hull with minimum area
Let P be a planar set of n points in general position. We consider the problem of computing an orientation of the plane for which the Rectilinear Convex Hull of P has minimum area. Bae et al. (Computational Geometry: Theory and Applications, Vol. 42, 2009) solved the problem in quadratic time and linear space. We describe an algorithm that reduces this time complexity to Θ(nlogn).
computational-geometry  rather-interesting  optimization  convex-hulls  constraint-satisfaction  nudge-targets  consider:looking-to-see  consider:feature-discovery
march 2017 by Vaguery
[1304.4635] Patterns In The Coefficients Of Powers Of Polynomials Over A Finite Field
We examine the behavior of the coefficients of powers of polynomials over a finite field of prime order. Extending the work of Allouche-Berthe, 1997, we study a(n), the number of occurring strings of length n among coefficients of any power of a polynomial f reduced modulo a prime p. The sequence of line complexity a(n) is p-regular in the sense of Allouche-Shalit. For f=1+x and general p, we derive a recursion relation for a(n) then find a new formula for the generating function for a(n). We use the generating function to compute the asymptotics of a(n)/n^2 as n approaches infinity, which is an explicitly computable piecewise quadratic in x with n= [p^m/x] and x is a real number between 1/p and 1. Analyzing other cases, we form a conjecture about the generating function for general a(n). We examine the matrix B associated with f and p used to compute the count of a coefficient, which applies to the theory of linear cellular automata and fractals. For p=2 and polynomials of small degree we compute the largest positive eigenvalue, \lambda, of B, related to the fractal dimension d of the corresponding fractal by d= \log_2(\lambda). We find proofs and make a number of conjectures for some bounds on \lambda, and upper bounds on its degree.
via:Khovanova  combinatorics  Pascal's-triangle  mathematical-recreations  rather-interesting  pattern-discovery  permutations  nudge-targets  consider:looking-to-see  consider:feature-discovery
march 2017 by Vaguery
[1506.00990] Unsupervised Learning on Neural Network Outputs: with Application in Zero-shot Learning
The outputs of a trained neural network contain much richer information than just an one-hot classifier. For example, a neural network might give an image of a dog the probability of one in a million of being a cat but it is still much larger than the probability of being a car. To reveal the hidden structure in them, we apply two unsupervised learning algorithms, PCA and ICA, to the outputs of a deep Convolutional Neural Network trained on the ImageNet of 1000 classes. The PCA/ICA embedding of the object classes reveals their visual similarity and the PCA/ICA components can be interpreted as common visual features shared by similar object classes. For an application, we proposed a new zero-shot learning method, in which the visual features learned by PCA/ICA are employed. Our zero-shot learning method achieves the state-of-the-art results on the ImageNet of over 20000 classes.
machine-learning  approximation  neural-networks  classification  rather-interesting  to-write-about  like-the-Soft-Push-scheme  consider:looking-to-see  consider:feature-discovery
march 2017 by Vaguery
[1702.04854] Two-stage Plant Species Recognition by Combining Local K-NN and Weighted Sparse Representation
In classical sparse representation based classification and weighted SRC algorithms, the test samples are sparely represented by all training samples. They emphasize the sparsity of the coding coefficients but without considering the local structure of the input data. To overcome the shortcoming, aiming at the difficult problem of plant leaf recognition on the large-scale database, a two-stage local similarity based classification learning method is proposed by combining local mean-based classification method and local WSRC. In the first stage, LMC is applied to coarsely classifying the test sample. nearest neighbors of the test sample, as a neighbor subset, is selected from each training class, then the local geometric center of each class is calculated. S candidate neighbor subsets of the test sample are determined with the first smallest distances between the test sample and each local geometric center. In the second stage, LWSRC is proposed to approximately represent the test sample through a linear weighted sum of all samples of the candidate neighbor subsets. The rationale of the proposed method is as follows: the first stage aims to eliminate the training samples that are far from the test sample and assume that these samples have no effects on the ultimate classification decision, then select the candidate neighbor subsets of the test sample. Thus the classification problem becomes simple with fewer subsets; the second stage pays more attention to those training samples of the candidate neighbor subsets in weighted representing the test sample. This is helpful to accurately represent the test sample. Experimental results on the leaf image database demonstrate that the proposed method not only has a high accuracy and low time cost, but also can be clearly interpreted.
benchmarks  image-processing  classification  machine-learning  nudge-targets  consider:looking-to-see  consider:feature-discovery
march 2017 by Vaguery
[1512.05749] Knot Probabilities in Random Diagrams
We consider a natural model of random knotting- choose a knot diagram at random from the finite set of diagrams with n crossings. We tabulate diagrams with 10 and fewer crossings and classify the diagrams by knot type, allowing us to compute exact probabilities for knots in this model. As expected, most diagrams with 10 and fewer crossings are unknots (about 78% of the roughly 1.6 billion 10 crossing diagrams). For these crossing numbers, the unknot fraction is mostly explained by the prevalence of tree-like diagrams which are unknots for any assignment of over/under information at crossings. The data shows a roughly linear relationship between the log of knot type probability and the log of the frequency rank of the knot type, analogous to Zipf's law for word frequency. All knot frequencies are available as ancillary data.
knot-theory  random-sampling  probability-theory  combinatorics  rather-interesting  mathematical-recreations  to-write-about  nudge-targets  consider:feature-discovery  consider:representation
march 2017 by Vaguery
[1702.08260] Topologically weakly mixing polygonal billiards
We show that in a typical polygon the billiard map as well as its associated subshift obtained by coding orbits by the sequence of sides they visit are topologically weakly mixing.
nonlinear-dynamics  plane-geometry  classification  rather-interesting  nudge-targets  consider:rediscovery  consider:feature-discovery
march 2017 by Vaguery
[1701.05855] Judicious partitions of uniform hypergraphs
The vertices of any graph with m edges may be partitioned into two parts so that each part meets at least 2m3 edges. Bollob\'as and Thomason conjectured that the vertices of any r-uniform hypergraph with m edges may likewise be partitioned into r classes such that each part meets at least r2r−1m edges. In this paper we prove the weaker statement that, for each r≥4, a partition into r classes may be found in which each class meets at least r3r−4m edges, a substantial improvement on previous bounds.
graph-theory  hypergraphs  conjecture  rather-interesting  nudge-targets  consider:looking-to-see  consider:feature-discovery
march 2017 by Vaguery
[1311.3867] The Robber Locating game
We consider a game in which a cop searches for a moving robber on a graph using distance probes, studied by Carragher, Choi, Delcourt, Erickson and West, which is a slight variation on one introduced by Seager. Carragher, Choi, Delcourt, Erickson and West show that for any fixed graph G there is a winning strategy for the cop on the graph G1/m, obtained by replacing each edge of G by a path of length m, if m is sufficiently large. They conjecture that the cop does not have a winning strategy on K1/mn if m<n; we show that in fact the cop wins if and only if m⩾n/2, for all but a few small values of n. They also show that the robber can avoid capture on any graph of girth 3, 4 or 5, and ask whether there is any graph of girth 6 on which the cop wins. We show that there is, but that no such graph can be bipartite; in the process we give a counterexample for their conjecture that the set of graphs on which the cop wins is closed under the operation of subdividing edges. We also give a complete answer to the question of when the cop has a winning strategy on K1/ma,b.
graph-theory  feature-construction  game-theory  rather-interesting  nudge-targets  consider:rediscovery  consider:feature-discovery
march 2017 by Vaguery
[1609.08455] Stratified construction of neural network based interatomic models for multicomponent materials
Recent application of neural networks (NNs) to modeling interatomic interactions has shown the learning machines' encouragingly accurate performance for select elemental and multicomponent systems. In this study, we explore the possibility of building a library of NN-based models by introducing a hierarchical NN training. In such a stratified procedure NNs for multicomponent systems are obtained by sequential training from the bottom up: first unaries, then binaries, and so on. Advantages of constructing NN sets with shared parameters include acceleration of the training process and intact description of the constituent systems. We use an automated generation of diverse structure sets for NN training on density functional theory-level reference energies. In the test case of Cu, Pd, Ag, Cu-Pd, Cu-Ag, Pd-Ag, and Cu-Pd-Ag systems, NNs trained in the traditional and stratified fashions are found to have essentially identical accuracy for defect energies, phonon dispersions, formation energies, etc. The models' robustness is further illustrated via unconstrained evolutionary structure searches in which the NN is used for the local optimization of crystal unit cells.
neural-networks  metaheuristics  materials-science  rather-interesting  learning-from-data  empirical-models  to-write-about  nudge-targets  consider:feature-discovery  consider:representation  consider:interpretability
february 2017 by Vaguery
[1605.06644] Deep convolutional networks on the pitch spiral for musical instrument recognition
Musical performance combines a wide range of pitches, nuances, and expressive techniques. Audio-based classification of musical instruments thus requires to build signal representations that are invariant to such transformations. This article investigates the construction of learned convolutional architectures for instrument recognition, given a limited amount of annotated training data. In this context, we benchmark three different weight sharing strategies for deep convolutional networks in the time-frequency domain: temporal kernels; time-frequency kernels; and a linear combination of time-frequency kernels which are one octave apart, akin to a Shepard pitch spiral. We provide an acoustical interpretation of these strategies within the source-filter framework of quasi-harmonic sounds with a fixed spectral envelope, which are archetypal of musical notes. The best classification accuracy is obtained by hybridizing all three convolutional layers into a single deep learning architecture.
deep-learning  music  classification  acoustics  signal-processing  rather-interesting  representation  nudge-targets  consider:representation  consider:feature-discovery
february 2017 by Vaguery
[1606.05496] Majority dynamics with one nonconformist
We consider a system in which a group of agents represented by the vertices of a graph synchronously update their opinion based on that of their neighbours. If each agent adopts a positive opinion if and only if that opinion is sufficiently popular among his neighbours, the system will eventually settle into a fixed state or alternate between two states. If one agent acts in a different way, other periods may arise. We show that only a small number of periods may arise if natural restrictions are placed either on the neighbourhood structure or on the way in which the nonconforming agent may act; without either of these restrictions any period is possible.
agent-based  complexology  feature-construction  graph-theory  dynamical-systems  to-write-about  to-do  nudge-targets  consider:classification  consider:prediction  consider:feature-discovery
february 2017 by Vaguery
[1701.00652] Semidefinite tests for latent causal structures
Testing whether a probability distribution is compatible with a given Bayesian network is a fundamental task in the field of causal inference, where Bayesian networks model causal relations. Here we consider the class of causal structures where all correlations between observed quantities are solely due to the influence from latent variables. We show that each model of this type imposes a certain signature on the observable covariance matrix in terms of a particular decomposition into positive semidefinite components. This signature, and thus the underlying hypothetical latent structure, can be tested in a computationally efficient manner via semidefinite programming. This stands in stark contrast with the algebraic geometric tools required if the full observable probability distribution is taken into account. The semidefinite test is compared with tests based on entropic inequalities.
statistics  bayesian  graphical-models  causality  inference  rather-interesting  to-understand  consider:feature-discovery
february 2017 by Vaguery
per page:    204080120160

Copy this bookmark:

description:

tags: