**Vaguery + rather-interesting**
2245

Towards experimental P-systems using multivesicular liposomes | SpringerLink

2 days ago by Vaguery

P-systems are abstract computational models inspired by the phospholipid bilayer membranes generated by biological cells. Illustrated here is a mechanism by which recursive liposome structures (multivesicular liposomes) may be experimentally produced through electroformation of dipalmitoylphosphatidylcholine films for use in ‘real’ P-systems. We first present the electroformation protocol and microscopic characterisation of incident liposomes towards estimating the size of computing elements, level of internal compartment recursion, fault tolerance and stability. Following, we demonstrate multiple routes towards embedding symbols, namely modification of swelling solutions, passive diffusion, and microinjection. Finally, we discuss how computing devices based on P-systems can be produced and their current limitations.

unconventional-computing
molecular-machinery
rather-interesting
vesicular-computing
experiment
nanotechnology
to-write-about
to-simulate
2 days ago by Vaguery

Elliptic curve calculator | Complex Projective 4-Space

2 days ago by Vaguery

It all boils down to the fact that the points on an elliptic curve form an Abelian group. This has a similar structure to the real numbers, which means that we can interchange between the two. (This is not so straightforward, requiring a transcendental function related to the Weierstrass P-function. I used repeated interval bisection and polynomial interpolation to obtain a good approximation instead.)

mathematical-recreations
rather-interesting
2 days ago by Vaguery

Notes from JMM 2018 | bit-player

3 days ago by Vaguery

The annual Joint Mathematics Meeting always charges my batteries. Here are few items from this year’s gathering in San Diego.

mathematical-recreations
various-items
rather-interesting
to-write-about
to-simulate
3 days ago by Vaguery

img cmprssn w/ svd – Almost looks like work

3 days ago by Vaguery

Let’s get pedagogical. Often when analysing a system, it is useful to break a component down into pieces, and figure out which are the important ones (if any). There are many techniques for this, here I’ll look at one called ‘singular value decomposition’ in the context of image compression.

Let’s start with the usual dry explanation of singular value decomposition (SVD). For any matrix , it is possible to write as

algorithms
looking-to-see
performance-measure
rather-interesting
parametrization
to-write-about
to-simulate
Let’s start with the usual dry explanation of singular value decomposition (SVD). For any matrix , it is possible to write as

3 days ago by Vaguery

You clicked 0 times

3 days ago by Vaguery

When I first heard about ClojureScript, I looked at it through the lens of my JavaScript experience. I assumed it would be like CoffeeScript, you pretty much know the JavaScript you are generating, but now you get to type less. With ClojureScript there’s a gap between the code I write and the code that’s generated, and this gap provides powerful leverage.

I’ve often felt the ClojureScript community should seek to understand and exploit React better. Too many times, by trying to make React easier and more convenient, most ClojureScript libraries obscure many of its important features.

clojurescript
reactjs
software-development-is-not-programming
library
rather-interesting
to-do
I’ve often felt the ClojureScript community should seek to understand and exploit React better. Too many times, by trying to make React easier and more convenient, most ClojureScript libraries obscure many of its important features.

3 days ago by Vaguery

Social learning strategies regulate the wisdom and madness of interactive crowds | bioRxiv

3 days ago by Vaguery

Why groups of individuals sometimes exhibit collective 'wisdom' and other times maladaptive `herding' is an enduring conundrum. Here we show that this apparent conflict is regulated by the social learning strategies deployed. We examined the patterns of human social learning through an interactive online experiment with 699 participants, varying both task uncertainty and group size, then used hierarchical Bayesian model-fitting to identify the individual learning strategies exhibited by participants. Challenging tasks elicit greater conformity amongst individuals, with rates of copying increasing with group size, leading to high probabilities of herding amongst large groups confronted with uncertainty. Conversely, the reduced social learning of small groups, and the greater probability that social information would be accurate for less-challenging tasks, generated `wisdom of the crowd' effects in other circumstances. Our model-based approach provides evidence that the likelihood of collective intelligence versus herding can be predicted, resolving a longstanding puzzle in the literature.

wisdom-of-crowds
collective-intelligence
collective-behavior
sociology
simulation
aggregation
data-fusion
rather-interesting
to-write-about
3 days ago by Vaguery

[1902.01023] Enhanced Hierarchical Music Structure Annotations via Feature Level Similarity Fusion

3 days ago by Vaguery

We describe a novel pipeline to automatically discover hierarchies of repeated sections in musical audio. The proposed method uses similarity network fusion (SNF) to combine different frame-level features into clean affinity matrices, which are then used as input to spectral clustering. While prior spectral clustering approaches to music structure analysis have pre-processed affinity matrices with heuristics specifically designed for this task, we show that the SNF approach directly yields segmentations which agree better with human annotators, as measured by the ``L-measure'' metric for hierarchical annotations. Furthermore, the SNF approach immediately supports arbitrarily many input features, allowing us to simultaneously discover structure encoded in timbral, harmonic, and rhythmic representations without any changes to the base algorithm.

classification
clustering
music
feature-construction
rather-interesting
indexing
to-write-about
performance-measure
3 days ago by Vaguery

[1812.01382] A new Bound for the Maker-Breaker Triangle Game

3 days ago by Vaguery

The triangle game introduced by Chvátal and Erdős (1978) is one of the most famous combinatorial games. For n,q∈ℕ, the (n,q)-triangle game is played by two players, called Maker and Breaker, on the complete graph Kn. Alternately Maker claims one edge and thereafter Breaker claims q edges of the graph. Maker wins the game if he can claim all three edges of a triangle, otherwise Breaker wins. Chvátal and Erdős (1978) proved that for q<2n+2‾‾‾‾‾‾√−5/2≈1.414n‾√ Maker has a winning strategy, and for q≥2n‾√ Breaker has a winning strategy. Since then, the problem of finding the exact leading constant for the threshold bias of the triangle game has been one of the famous open problems in combinatorial game theory. In fact, the constant is not known for any graph with a cycle and we do not even know if such a constant exists. Balogh and Samotij (2011) slightly improved the Chvátal-Erdős constant for Breaker's winning strategy from 2 to 1.935 with a randomized approach. Since then no progress was made. In this work, we present a new deterministic strategy for Breaker's win whenever n is sufficiently large and q≥(8/3+o(1))n‾‾‾‾‾‾‾‾‾‾‾‾√≈1.633n‾√, significantly reducing the gap towards the lower bound. In previous strategies Breaker chooses his edges such that one node is part of the last edge chosen by Maker, whereas the remaining node is chosen more or less arbitrarily. In contrast, we introduce a suitable potential function on the set of nodes. This allows Breaker to pick edges that connect the most `dangerous' nodes. The total potential of the game may still increase, even for several turns, but finally Breaker's strategy prevents the total potential of the game from exceeding a critical level and leads to Breaker's win.

combinatorics
game-theory
rather-interesting
feature-construction
open-questions
nudge-targets
consider:looking-to-see
3 days ago by Vaguery

[1809.04209] Bidirectional Evaluation with Direct Manipulation

3 days ago by Vaguery

We present an evaluation update (or simply, update) algorithm for a full-featured functional programming language, which synthesizes program changes based on output changes. Intuitively, the update algorithm retraces the steps of the original evaluation, rewriting the program as needed to reconcile differences between the original and updated output values. Our approach, furthermore, allows expert users to define custom lenses that augment the update algorithm with more advanced or domain-specific program updates.

To demonstrate the utility of evaluation update, we implement the algorithm in Sketch-n-Sketch, a novel direct manipulation programming system for generating HTML documents. In Sketch-n-Sketch, the user writes an ML-style functional program to generate HTML output. When the user directly manipulates the output using a graphical user interface, the update algorithm reconciles the changes. We evaluate bidirectional evaluation in Sketch-n-Sketch by authoring ten examples comprising approximately 1400 lines of code in total. These examples demonstrate how a variety of HTML documents and applications can be developed and edited interactively in Sketch-n-Sketch, mitigating the tedious edit-run-view cycle in traditional programming environments.

rather-interesting
usability
functional-languages
computer-science
programming-language
to-understand
inference
ReQ
genetic-programming
consider:GP
To demonstrate the utility of evaluation update, we implement the algorithm in Sketch-n-Sketch, a novel direct manipulation programming system for generating HTML documents. In Sketch-n-Sketch, the user writes an ML-style functional program to generate HTML output. When the user directly manipulates the output using a graphical user interface, the update algorithm reconciles the changes. We evaluate bidirectional evaluation in Sketch-n-Sketch by authoring ten examples comprising approximately 1400 lines of code in total. These examples demonstrate how a variety of HTML documents and applications can be developed and edited interactively in Sketch-n-Sketch, mitigating the tedious edit-run-view cycle in traditional programming environments.

3 days ago by Vaguery

[1811.06837] A Grammar-Based Structural CNN Decoder for Code Generation

3 days ago by Vaguery

Code generation maps a program description to executable source code in a programming language. Existing approaches mainly rely on a recurrent neural network (RNN) as the decoder. However, we find that a program contains significantly more tokens than a natural language sentence, and thus it may be inappropriate for RNN to capture such a long sequence. In this paper, we propose a grammar-based structural convolutional neural network (CNN) for code generation. Our model generates a program by predicting the grammar rules of the programming language; we design several CNN modules, including the tree-based convolution and pre-order convolution, whose information is further aggregated by dedicated attentive pooling layers. Experimental results on the HearthStone benchmark dataset show that our CNN code generator significantly outperforms the previous state-of-the-art method by 5 percentage points; additional experiments on several semantic parsing tasks demonstrate the robustness of our model. We also conduct in-depth ablation test to better understand each component of our model.

rather-interesting
machine-learning
generative-models
natural-language-processing
software-synthesis
structured-data
to-write-about
3 days ago by Vaguery

[1812.05433] Lenia - Biology of Artificial Life

3 days ago by Vaguery

We report a new model of artificial life called Lenia (from Latin lenis "smooth"), a two-dimensional cellular automaton with continuous space-time-state and generalized local rule. Computer simulations show that Lenia supports a great diversity of complex autonomous patterns or "lifeforms" bearing resemblance to real-world microscopic organisms. More than 400 species in 18 families have been identified, many discovered via interactive evolutionary computation. They differ from other cellular automata patterns in being geometric, metameric, fuzzy, resilient, adaptive, and rule-generic.

We present basic observations of the model regarding the properties of space-time and basic settings. We provide a board survey of the lifeforms, categorize them into a hierarchical taxonomy, and map their distribution in the parameter hyperspace. We describe their morphological structures and behavioral dynamics, propose possible mechanisms of their self-propulsion, self-organization and plasticity. Finally, we discuss how the study of Lenia would be related to biology, artificial life, and artificial intelligence.

artificial-life
representation
cellular-automata
rather-interesting
to-write-about
to-implement
consider:simulation
consider:abstraction
We present basic observations of the model regarding the properties of space-time and basic settings. We provide a board survey of the lifeforms, categorize them into a hierarchical taxonomy, and map their distribution in the parameter hyperspace. We describe their morphological structures and behavioral dynamics, propose possible mechanisms of their self-propulsion, self-organization and plasticity. Finally, we discuss how the study of Lenia would be related to biology, artificial life, and artificial intelligence.

3 days ago by Vaguery

[1811.00607] Exploring the Equivalence between Dynamic Dataflow Model and Gamma - General Abstract Model for Multiset mAnipulation

3 days ago by Vaguery

With the increase of the search for computational models where the expression of parallelism occurs naturally, some paradigms arise as options for the next generation of computers. In this context, dynamic Dataflow and Gamma - General Abstract Model for Multiset mAnipulation) - emerge as interesting computational models choices. In the dynamic Dataflow model, operations are performed as soon as their associated operators are available, without rely on a Program Counter to dictate the execution order of instructions. The Gamma paradigm is based on a parallel multiset rewriting scheme. It provides a non-deterministic execution model inspired by an abstract chemical machine metaphor, where operations are formulated as reactions that occur freely among matching elements belonging to the multiset. In this work, equivalence relations between the dynamic Dataflow and Gamma paradigms are exposed and explored, while methods to convert from Dataflow to Gamma paradigm and vice versa are provided. It is shown that vertices and edges of a dynamic Dataflow graph can correspond, respectively, to reactions and multiset elements in the Gamma paradigm. Implementation aspects of execution environments that could be mutually beneficial to both models are also discussed. This work provides the scientific community with the possibility of taking profit of both parallel programming models, contributing with a versatility component to researchers and developers. Finally, it is important to state that, to the best of our knowledge, the similarity relations between both dynamic Dataflow and Gamma models presented here have not been reported in any previous work.

concurrency
rather-interesting
to-understand
coordination
computer-science
ReQ
3 days ago by Vaguery

[1810.09202] Graph Convolutional Reinforcement Learning for Multi-Agent Cooperation

3 days ago by Vaguery

Learning to cooperate is crucially important in multi-agent environments. The key is to understand the mutual interplay between agents. However, multi-agent environments are highly dynamic, which makes it hard to learn abstract representations of their mutual interplay. In this paper, we propose graph convolutional reinforcement learning for multi-agent cooperation, where graph convolution adapts to the dynamics of the underlying graph of the multi-agent environment, and relation kernels capture the interplay between agents by their relation representations. Latent features produced by convolutional layers from gradually increased receptive fields are exploited to learn cooperation, and the cooperation is further boosted by temporal relation regularization for consistency. Empirically, we show that our method substantially outperforms existing methods in a variety of cooperative scenarios.

machine-learning
agent-based
coordination
rather-interesting
reinforcement-learning
teams
to-understand
rather-convoluted-(heh)
collective-behavior
3 days ago by Vaguery

BBC Radio 4 - James Burke's Web of Knowledge

3 days ago by Vaguery

For James Burke knowledge doesn't go in predictable straight lines. Here he proves that random connections between people can result in profound and unpredictable consequences.

podcast
wish-it-were-in-podcast-format
history
history-of-science
rather-interesting
3 days ago by Vaguery

[1901.10861] A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance

3 days ago by Vaguery

The existence of adversarial examples in which an imperceptible change in the input can fool well trained neural networks was experimentally discovered by Szegedy et al in 2013, who called them "Intriguing properties of neural networks". Since then, this topic had become one of the hottest research areas within machine learning, but the ease with which we can switch between any two decisions in targeted attacks is still far from being understood, and in particular it is not clear which parameters determine the number of input coordinates we have to change in order to mislead the network. In this paper we develop a simple mathematical framework which enables us to think about this baffling phenomenon from a fresh perspective, turning it into a natural consequence of the geometry of ℝn with the L0 (Hamming) metric, which can be quantitatively analyzed. In particular, we explain why we should expect to find targeted adversarial examples with Hamming distance of roughly m in arbitrarily deep neural networks which are designed to distinguish between m input classes.

machine-learning
robustness
adversarial-examples
rather-interesting
good-explanations
to-write-about
computational-vs-systems
generalization
feature-construction
saliency
3 days ago by Vaguery

Genome graphs and the evolution of genome inference

3 days ago by Vaguery

The human reference genome is part of the foundation of modern human biology and a monumental scientific achievement. However, because it excludes a great deal of common human variation, it introduces a pervasive reference bias into the field of human genomics. To reduce this bias, it makes sense to draw on representative collections of human genomes, brought together into reference cohorts. There are a number of techniques to represent and organize data gleaned from these cohorts, many using ideas implicitly or explicitly borrowed from graph-based models. Here, we survey various projects underway to build and apply these graph-based structures—which we collectively refer to as genome graphs—and discuss the improvements in read mapping, variant calling, and haplotype determination that genome graphs are expected to produce.

via:arthegall
review
bioinformatics
clustering
visualization
data-analysis
rather-interesting
consider:nonbiological-genomes
3 days ago by Vaguery

[1808.06091] Clock theorems for triangulated surfaces

6 days ago by Vaguery

We investigate triangulations of the two-dimensional sphere and torus with the faces properly colored white and black. We focus on matchings between white triangles and incident vertices. On the torus our objects are perfect pairings, whereas on the sphere this is only true after removing one triangle and its vertices. In the latter case, such matchings (first studied by Tutte) extend the notion of state in Kauffman's formal knot theory and we show that his Clock Theorem, in its form due to Gilmer and Litherland, also extends: the set of matchings naturally forms a distributive lattice. Here the role of state transposition is played by a simple local operation about black triangles. By contrast, on the torus, the analogous state transition graph is usually disconnected: some of its components still form distributive lattices with global maxima and minima, while other components contain directed cycles and are without local extrema.

combinatorics
graph-theory
topology
rather-interesting
feature-construction
6 days ago by Vaguery

Prioritized Grammar Enumeration: A novel method for symbolic regression - ProQuest

7 days ago by Vaguery

Prioritized Grammar Enumeration: A novel method for symbolic regression

genetic-programming
thesis
algorithms
to-read
archives-and-caches
have-done
rather-interesting
compare-notes
7 days ago by Vaguery

Birds have balance organs in their butts. Why is no-one talking about this?! | Sauropod Vertebra Picture of the Week

9 days ago by Vaguery

I was equally blown away by the fact that I’d never heard about this from inside the world of science and sci-comm. Necker’s discovery seemed to have been almost entirely overlooked in the broader comparative anatomy community. I searched for weaknesses in the evidence or reasoning, and I also searched for people debunking the idea that birds have balance organs in their butts, and in both cases I came up empty-handed (if you know of counter-evidence, please let me know!). It’s relevant to paleontology, too: because the lumbosacral canals occupy transverse recesses in the roof of the sacral neural canal, they should be discoverable in fossil taxa. I’ve never heard of them being identified in a non-avian dinosaur, but then, I’ve never heard of anyone looking. You can also see the lumbosacral canals for yourself, or at least the spaces they occupy, for about three bucks, as I will show in an upcoming post.

Incidentally, I’m pretty sure this system underlies the axiomatic ability of birds to run around with their heads cut off. I grew up on a farm and raised and slaughtered chickens, so I’ve observed this firsthand. A decapitated chicken can get up on its hind legs and run around. It won’t go very far or in a straight line, hence the jokey expression, but it can actually run on flat ground. It hadn’t occurred to me until recently how weird that is. All vertebrates have central pattern generators in their spinal cords that can produce the basic locomotor movements of the trunk and limbs, but if you decapitate most vertebrates the body will just lie there and twitch. The limbs may even make rudimentary running motions, but the decapitated body can’t stand up and successfully walk or run. Central pattern generators aren’t enough, to run you need an organ of balance. A decapitated bird can successfully stand and run around because it still has a balance organ, in its lumbosacral spinal cord.

physiology
biology
anatomy
rather-interesting
learning-by-doing
life-finds-a-way
Incidentally, I’m pretty sure this system underlies the axiomatic ability of birds to run around with their heads cut off. I grew up on a farm and raised and slaughtered chickens, so I’ve observed this firsthand. A decapitated chicken can get up on its hind legs and run around. It won’t go very far or in a straight line, hence the jokey expression, but it can actually run on flat ground. It hadn’t occurred to me until recently how weird that is. All vertebrates have central pattern generators in their spinal cords that can produce the basic locomotor movements of the trunk and limbs, but if you decapitate most vertebrates the body will just lie there and twitch. The limbs may even make rudimentary running motions, but the decapitated body can’t stand up and successfully walk or run. Central pattern generators aren’t enough, to run you need an organ of balance. A decapitated bird can successfully stand and run around because it still has a balance organ, in its lumbosacral spinal cord.

9 days ago by Vaguery

[1811.11909] Synchronization of chaotic systems: A microscopic description

9 days ago by Vaguery

The synchronization of coupled chaotic systems represents a fundamental example of self organization and collective behavior. This well-studied phenomenon is classically characterized in terms of macroscopic parameters, such as Lyapunov exponents, that help predict the systems transitions into globally organized states. However, the local, microscopic, description of this emergent process continues to elude us. Here we show that at the microscopic level, synchronization is captured through a gradual process of topological adjustment in phase space, in which the strange attractors of the two coupled systems continuously converge, taking similar form, until complete topological synchronization ensues. We observe the local nucleation of topological synchronization in specific regions of the systems attractor, providing early signals of synchrony, that appear significantly before the onset of complete synchronization. This local synchronization initiates at the regions of the attractor characterized by lower expansion rates, in which the chaotic trajectories are least sensitive to slight changes in initial conditions. Our findings offer an alternative description of synchronization in chaotic systems, exposing its local embryonic stages that are overlooked by the currently established global analysis. Such local topological synchronization enables the identification of configurations where prediction of the state of one system is possible from measurements on that of the other, even in the absence of global synchronization.

nonlinear-dynamics
coupled-oscillators
rather-interesting
synchronization
to-read
complexology
physics!
dynamical-systems
9 days ago by Vaguery

A nice proof for the Law of Cosines | Continuous Everywhere but Differentiable Nowhere

11 days ago by Vaguery

And I kinda told them what to do… Meh. I was jumping way ahead to get to the formula. We weren’t savoring the thinking to get to the formula. Now we are.

That being said, I ran across something quite beautiful. A stunning proof of the Law of Cosines (at least for acute triangles) on the site trigonography.

geometry
pedagogy
visualization
rather-interesting
visual-proof
feature-construction
explanation
consider:the-mangle
That being said, I ran across something quite beautiful. A stunning proof of the Law of Cosines (at least for acute triangles) on the site trigonography.

11 days ago by Vaguery

[1706.05423] Weighted counting of integer points in a subspace

11 days ago by Vaguery

Given complex numbers w1,…,wn, we define the weight w(X) of a set X of non-negative integer n-vectors as the sum of wx11⋯wxnn over all vectors (x1,…,xn) in X. We present an algorithm, which for a set X of 0-1 vectors defined by a system of homogeneous linear equations with at most r variables per equation and at most c equations per variable, computes w(X) within relative error ϵ>0 in (rc)O(lnn−lnϵ) time provided |wj|≤β(rc√)−1 for an absolute constant β>0 and all j=1,…,n. A similar algorithm is constructed for computing the weight of a set of non-negative integer vectors satisfying linear constraints and the weight of a linear code over 𝔽p. Applications include counting weighted perfect matchings in hypergraphs, counting weighted graph homomorphisms, computing weight enumerators of linear codes with sparse code generating matrices, computing the partition function of the ferromagnetic Potts model at low temperatures and computing the hard-core model at large fugacity on biregular bipartite graphs.

representation
combinatorics
rather-interesting
graph-theory
feature-construction
indirect-representations
to-understand
11 days ago by Vaguery

Unsupervised discovery of temporal sequences in high-dimensional datasets, with applications to neuroscience | bioRxiv

11 days ago by Vaguery

Identifying low-dimensional features that describe large-scale neural recordings is a major challenge in neuroscience. Repeated temporal patterns (sequences) are thought to be a salient feature of neural dynamics, but are not succinctly captured by traditional dimensionality reduction techniques. Here we describe a software toolbox -- called seqNMF -- with new methods for extracting informative, non-redundant, sequences from high-dimensional neural data, testing the significance of these extracted patterns, and assessing the prevalence of sequential structure in data. We test these methods on simulated data under multiple noise conditions, and on several real neural and behavioral data sets. In hippocampal data, seqNMF identifies neural sequences that match those calculated manually by reference to behavioral events. In songbird data, seqNMF discovers neural sequences in untutored birds that lack stereotyped songs. Thus, by identifying temporal structure directly from neural data, seqNMF enables dissection of complex neural circuits without relying on temporal references from stimuli or behavioral outputs.

time-series
unsupervised-learning
machine-learning
algorithms
rather-interesting
consider:representation
to-understand
11 days ago by Vaguery

[1808.06423] What Stands-in for a Missing Tool? A Prototypical Grounded Knowledge-based Approach to Tool Substitution

11 days ago by Vaguery

When a robot is operating in a dynamic environment, it cannot be assumed that a tool required to solve a given task will always be available. In case of a missing tool, an ideal response would be to find a substitute to complete the task. In this paper, we present a proof of concept of a grounded knowledge-based approach to tool substitution. In order to validate the suitability of a substitute, we conducted experiments involving 22 substitution scenarios. The substitutes computed by the proposed approach were validated on the basis of the experts' choices for each scenario. Our evaluation showed, in 20 out of 22 scenarios (91%), the approach identified the same substitutes as experts.

artificial-intelligence
feature-construction
learning-from-data
rather-interesting
to-write-about
consider:looking-to-see
11 days ago by Vaguery

[1809.04243] Self-foldability of monohedral quadrilateral origami tessellations

11 days ago by Vaguery

Using a mathematical model for self-foldability of rigid origami, we determine which monohedral quadrilateral tilings of the plane are uniquely self-foldable. In particular, the Miura-ori and Chicken Wire patterns are not self-foldable under our definition, but such tilings that are rotationally-symmetric about the midpoints of the tile are uniquely self-foldable.

origami
constraint-satisfaction
geometry
classification
rather-interesting
to-write-about
consider:algorithms
11 days ago by Vaguery

[1701.01370] Learning from Synthetic Humans

11 days ago by Vaguery

Estimating human pose, shape, and motion from images and videos are fundamental challenges with many applications. Recent advances in 2D human pose estimation use large amounts of manually-labeled training data for learning convolutional neural networks (CNNs). Such data is time consuming to acquire and difficult to extend. Moreover, manual labeling of 3D pose, depth and motion is impractical. In this work we present SURREAL (Synthetic hUmans foR REAL tasks): a new large-scale dataset with synthetically-generated but realistic images of people rendered from 3D sequences of human motion capture data. We generate more than 6 million frames together with ground truth pose, depth maps, and segmentation masks. We show that CNNs trained on our synthetic dataset allow for accurate human depth estimation and human part segmentation in real RGB images. Our results and the new dataset open up new possibilities for advancing person analysis using cheap and large-scale synthetic data.

computer-vision
synthetic-data
dreaming-about-people
training-data
data-generation
rather-interesting
to-write-about
pose-estimation
image-segmentation
11 days ago by Vaguery

[1704.08679] Age-Minimal Transmission in Energy Harvesting Two-hop Networks

11 days ago by Vaguery

We consider an energy harvesting two-hop network where a source is communicating to a destination through a relay. During a given communication session time, the source collects measurement updates from a physical phenomenon and sends them to the relay, which then forwards them to the destination. The objective is to send these updates to the destination as timely as possible; namely, such that the total age of information is minimized by the end of the communication session, subject to energy causality constraints at the source and the relay, and data causality constraints at the relay. Both the source and the relay use fixed, yet possibly different, transmission rates. Hence, each update packet incurs fixed non-zero transmission delays. We first solve the single-hop version of this problem, and then show that the two-hop problem is solved by treating the source and relay nodes as one combined node, with some parameter transformations, and solving a single-hop problem between that combined node and the destination.

queueing-theory
information-theory
multiobjective-optimization
rather-interesting
to-write-about
to-simulate
consider:looking-to-see
11 days ago by Vaguery

Understanding Society: The mind of government

19 days ago by Vaguery

Ideally we would like to imagine a process of government decision-making that proceeds along these lines: careful gathering and assessment of the best available scientific evidence about an issue through expert specialist panels and sections; careful analysis of the consequences of available policy choices measured against a clear understanding of goals and priorities of the government; and selection of a policy or action that is best, all things considered, for forwarding the public interest and minimizing public harms. Unfortunately, as the experience of government policies concerning climate change in both the Bush administration and the Trump administration illustrates, ideology and private interest distort every phase of this idealized process.

sociology
public-policy
collective-behavior
corporatism
rather-interesting
to-write-about
19 days ago by Vaguery

[1811.04960] Molecular computers

22 days ago by Vaguery

We propose the chemlambda artificial chemistry, whose behavior strongly suggests that real molecules which embed Interaction Nets patterns and real chemical reactions which resemble Interaction Nets graph rewrites could be a realistic path towards molecular computers, in the sense explained in the article.

artificial-chemistry
graph-rewriting
artificial-life
rather-interesting
to-simulate
to-write-about
concurrency
consider:the-algorithm-loop-dichotomy
consider:the-edges-of-things
22 days ago by Vaguery

[1812.11592] A Geometric Theory of Higher-Order Automatic Differentiation

22 days ago by Vaguery

First-order automatic differentiation is a ubiquitous tool across statistics, machine learning, and computer science. Higher-order implementations of automatic differentiation, however, have yet to realize the same utility. In this paper I derive a comprehensive, differential geometric treatment of automatic differentiation that naturally identifies the higher-order differential operators amenable to automatic differentiation as well as explicit procedures that provide a scaffolding for high-performance implementations.

gradient-descent
automatic-differentiation
algorithms
topology
algebraic-topology
the-shape-of-data
machine-learning
rather-interesting
to-understand
22 days ago by Vaguery

How AI Training Scales

22 days ago by Vaguery

We’ve discovered that the gradient noise scale, a simple statistical metric, predicts the parallelizability of neural network training on a wide range of tasks. Since complex tasks tend to have noisier gradients, increasingly large batch sizes are likely to become useful in the future, removing one potential limit to further growth of AI systems. More broadly, these results show that neural network training need not be considered a mysterious art, but can be rigorized and systematized.

stochastic-systems
machine-learning
problem-solving
feature-construction
rather-interesting
to-write-about
consider:nongradient-methods
consider:lexicase
consider:data-balancing
22 days ago by Vaguery

Anytime algorithm - Wikipedia

24 days ago by Vaguery

In computer science, an anytime algorithm is an algorithm that can return a valid solution to a problem even if it is interrupted before it ends. The algorithm is expected to find better and better solutions the longer it keeps running.

Most algorithms run to completion: they provide a single answer after performing some fixed amount of computation. In some cases, however, the user may wish to terminate the algorithm prior to completion. The amount of computation required may be substantial, for example, and computational resources might need to be reallocated. Most algorithms either run to completion or they provide no useful solution information. Anytime algorithms, however, are able to return a partial answer, whose quality depends on the amount of computation they were able to perform. The answer generated by anytime algorithms is an approximation of the correct answer.

via:nprnncbl
algorithms
computer-science
rather-interesting
to-understand
ReQ
approximation
Most algorithms run to completion: they provide a single answer after performing some fixed amount of computation. In some cases, however, the user may wish to terminate the algorithm prior to completion. The amount of computation required may be substantial, for example, and computational resources might need to be reallocated. Most algorithms either run to completion or they provide no useful solution information. Anytime algorithms, however, are able to return a partial answer, whose quality depends on the amount of computation they were able to perform. The answer generated by anytime algorithms is an approximation of the correct answer.

24 days ago by Vaguery

[PDF] APPROXIMATE REASONING USING ANYTIME ALGORITHMS

24 days ago by Vaguery

The complexity of reasoning in intelligent systems makes it undesirable, and some- times infeasible, to find the optimal action in every situation since the deliberation process itself degrades the performance of the system. The problem is then to con- struct intelligent systems that react to a situation after performing the “right” amount of thinking. It is by now widely accepted that a successful system must trade off decision quality against the computational requirements of decision-making. Anytime algorithms, introduced by Dean, Horvitz and others in the late 1980’s, were designed to offer such a trade-off. We have extended their work to the construction of complex systems that are composed of anytime algorithms. This paper describes the compila- tion and monitoring mechanisms that are required to build intelligent systems that can efficiently control their deliberation time. We present theoretical results showing that the compilation and monitoring problems are tractable in a wide range of cases, and provide two applications to illustrate the ideas.

computer-science
representation
algorithms
rather-interesting
to-do
to-understand
ReQ
approximation
24 days ago by Vaguery

[1704.00454] Clustering in Hilbert simplex geometry

5 weeks ago by Vaguery

Clustering categorical distributions in the probability simplex is a fundamental task met in many applications dealing with normalized histograms. Traditionally, the differential-geometric structures of the probability simplex have been used either by (i) setting the Riemannian metric tensor to the Fisher information matrix of the categorical distributions, or (ii) defining the dualistic information-geometric structure induced by a smooth dissimilarity measure, the Kullback-Leibler divergence. In this work, we introduce for this clustering task a novel computationally-friendly framework for modeling the probability simplex termed {\em Hilbert simplex geometry}. In the Hilbert simplex geometry, the distance function is described by a polytope. We discuss the pros and cons of those different statistical modelings, and benchmark experimentally these geometries for center-based k-means and k-center clusterings. We show that Hilbert metric in the probability simplex satisfies the property of information monotonicity. Furthermore, since a canonical Hilbert metric distance can be defined on any bounded convex subset of the Euclidean space, we also consider Hilbert's projective geometry of the elliptope of correlation matrices and study its clustering performances.

clustering
representation
categorical-variables
rather-interesting
machine-learning
to-understand
5 weeks ago by Vaguery

[1802.04148] On Dendrites Generated By Symmetric Polygonal Systems: The Case of Regular Polygons

5 weeks ago by Vaguery

We define G-symmetric polygonal systems of similarities and study the properties of symmetric dendrites, which appear as their attractors. This allows us to find the conditions under which the attractor of a zipper becomes a dendrite.

fractals
geometry
nonlinear-dynamics
rather-interesting
purdy-pitchers
5 weeks ago by Vaguery

[1312.1001] Optimal detection of intersections between convex polyhedra

5 weeks ago by Vaguery

For a polyhedron P in ℝd, denote by |P| its combinatorial complexity, i.e., the number of faces of all dimensions of the polyhedra. In this paper, we revisit the classic problem of preprocessing polyhedra independently so that given two preprocessed polyhedra P and Q in ℝd, each translated and rotated, their intersection can be tested rapidly.

For d=3 we show how to perform such a test in O(log|P|+log|Q|) time after linear preprocessing time and space. This running time is the best possible and improves upon the last best known query time of O(log|P|log|Q|) by Dobkin and Kirkpatrick (1990).

We then generalize our method to any constant dimension d, achieving the same optimal O(log|P|+log|Q|) query time using a representation of size O(|P|⌊d/2⌋+ε) for any ε>0 arbitrarily small. This answers an even older question posed by Dobkin and Kirkpatrick 30 years ago.

In addition, we provide an alternative O(log|P|+log|Q|) algorithm to test the intersection of two convex polygons P and Q in the plane.

computational-complexity
computational-geometry
algorithms
rather-interesting
consider:performance-measures
to-write-about
nudge-targets
For d=3 we show how to perform such a test in O(log|P|+log|Q|) time after linear preprocessing time and space. This running time is the best possible and improves upon the last best known query time of O(log|P|log|Q|) by Dobkin and Kirkpatrick (1990).

We then generalize our method to any constant dimension d, achieving the same optimal O(log|P|+log|Q|) query time using a representation of size O(|P|⌊d/2⌋+ε) for any ε>0 arbitrarily small. This answers an even older question posed by Dobkin and Kirkpatrick 30 years ago.

In addition, we provide an alternative O(log|P|+log|Q|) algorithm to test the intersection of two convex polygons P and Q in the plane.

5 weeks ago by Vaguery

[1806.04609] Streaming PCA and Subspace Tracking: The Missing Data Case

6 weeks ago by Vaguery

For many modern applications in science and engineering, data are collected in a streaming fashion carrying time-varying information, and practitioners need to process them with a limited amount of memory and computational resources in a timely manner for decision making. This often is coupled with the missing data problem, such that only a small fraction of data attributes are observed. These complications impose significant, and unconventional, constraints on the problem of streaming Principal Component Analysis (PCA) and subspace tracking, which is an essential building block for many inference tasks in signal processing and machine learning. This survey article reviews a variety of classical and recent algorithms for solving this problem with low computational and memory complexities, particularly those applicable in the big data regime with missing data. We illustrate that streaming PCA and subspace tracking algorithms can be understood through algebraic and geometric perspectives, and they need to be adjusted carefully to handle missing data. Both asymptotic and non-asymptotic convergence guarantees are reviewed. Finally, we benchmark the performance of several competitive algorithms in the presence of missing data for both well-conditioned and ill-conditioned systems.

online-learning
algorithms
machine-learning
data-balancing
streaming-algorithms
performance-measure
rather-interesting
to-write-about
to-generalize
consider:multiobjective-versions
6 weeks ago by Vaguery

[1804.00746] The simple essence of automatic differentiation

6 weeks ago by Vaguery

Automatic differentiation (AD) in reverse mode (RAD) is a central component of deep learning and other uses of large-scale optimization. Commonly used RAD algorithms such as backpropagation, however, are complex and stateful, hindering deep understanding, improvement, and parallel execution. This paper develops a simple, generalized AD algorithm calculated from a simple, natural specification. The general algorithm is then specialized by varying the representation of derivatives. In particular, applying well-known constructions to a naive representation yields two RAD algorithms that are far simpler than previously known. In contrast to commonly used RAD implementations, the algorithms defined here involve no graphs, tapes, variables, partial derivatives, or mutation. They are inherently parallel-friendly, correct by construction, and usable directly from an existing programming language with no need for new data types or programming style, thanks to use of an AD-agnostic compiler plugin.

computer-science
differentiation
gradients
numerical-methods
machine-learning
algorithms
category-theory
rather-interesting
to-understand
6 weeks ago by Vaguery

The Fermat primality test and the GCD test | The Math Less Traveled

6 weeks ago by Vaguery

In my previous post we proved that if shares a nontrivial common factor with , then , and this in turn proves that is not prime (by Fermat’s Little Theorem).

But wait a minute, this is silly: if shares a common factor with , then we don’t need anything as complex as Fermat’s Little Theorem to figure out that is not prime! All we have to do is compute using the Euclidean Algorithm, and when we find out that the result isn’t , we can immediately conclude that isn’t prime since it has a nontrivial divisor.

algorithms
number-theory
rather-interesting
nudge-targets
consider:looking-to-see
But wait a minute, this is silly: if shares a common factor with , then we don’t need anything as complex as Fermat’s Little Theorem to figure out that is not prime! All we have to do is compute using the Euclidean Algorithm, and when we find out that the result isn’t , we can immediately conclude that isn’t prime since it has a nontrivial divisor.

6 weeks ago by Vaguery

Tanya Khovanova's Math Blog » Blog Archive » 3-Symmetric Graphs

6 weeks ago by Vaguery

In my previous post I described 3-symmetric permutations. Now I want to define 3-symmetric graphs.

A reminder: a k-symmetric permutation is such that the densities of all permutations of size k in it are the same. In particular a 2-symmetric permutation has the same number of inversions and non-inversions. How do we translate this to graphs? I call a graph 2-symmetric if it has the same number of edges as non-edges. 2-symmetric graphs are easy to construct, but they only exist if the number of vertices, n, is such that n choose 2 is even. The simplest non-trivial examples are graphs with 4 vertices and three edges.

graph-theory
feature-construction
rather-interesting
mathematical-recreations
A reminder: a k-symmetric permutation is such that the densities of all permutations of size k in it are the same. In particular a 2-symmetric permutation has the same number of inversions and non-inversions. How do we translate this to graphs? I call a graph 2-symmetric if it has the same number of edges as non-edges. 2-symmetric graphs are easy to construct, but they only exist if the number of vertices, n, is such that n choose 2 is even. The simplest non-trivial examples are graphs with 4 vertices and three edges.

6 weeks ago by Vaguery

[1807.04271] A quantum-inspired classical algorithm for recommendation systems

6 weeks ago by Vaguery

A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an m×n matrix of small rank k. We give the first classical algorithm to produce a recommendation in O(poly(k)polylog(m,n)) time, which is an exponential improvement on previous algorithms that run in time linear in m and n. Our strategy is inspired by a quantum algorithm by Kerenidis and Prakash: like the quantum algorithm, instead of reconstructing a user's full list of preferences, we only seek a randomized sample from the user's preferences. Our main result is an algorithm that samples high-weight entries from a low-rank approximation of the input matrix in time independent of m and n, given natural sampling assumptions on that input matrix. As a consequence, we show that Kerenidis and Prakash's quantum machine learning (QML) algorithm, one of the strongest candidates for provably exponential speedups in QML, does not in fact give an exponential speedup over classical algorithms.

recommendations
algorithms
quantum-computing
classical-computing
rather-interesting
information-theory
to-understand
6 weeks ago by Vaguery

Friendship Paradox | Math Section

6 weeks ago by Vaguery

Your friends are more popular than you. In the year 1991, the sociologist Scott L. Feld made an interesting discovery. He realized that on average, most individual’s friends have more friends than the individual. This phenomenon is called the friendship paradox. [1] In this article, we describe the friendship paradox using graph theory, provide a mathematical proof, and give examples for possible applications. Furthermore, we talk about its applications in monitoring disease outbreaks.

graph-theory
rather-interesting
network-theory
to-write-about
6 weeks ago by Vaguery

An overview of semantic image segmentation.

6 weeks ago by Vaguery

More specifically, the goal of semantic image segmentation is to label each pixel of an image with a corresponding class of what is being represented. Because we're predicting for every pixel in the image, this task is commonly referred to as dense prediction.

image-segmentation
image-processing
distributed-processing
rather-interesting
neural-networks
to-write-about
to-do
nudge-targets
consider:representation
6 weeks ago by Vaguery

[1811.11888] Reality Inspired Voter Models: A Mini-review

6 weeks ago by Vaguery

This mini-review presents extensions of the voter model that incorporate a number of plausible features of real decision-making processes of individuals. Although these generalizations are not calibrated by empirical data, the resulting dynamics are suggestive of real collective social behaviors.

collective-behavior
voting
social-networks
social-dynamics
abstraction
simulation
to-write-about
review
rather-interesting
6 weeks ago by Vaguery

[1601.05613] Partial Sum Minimization of Singular Values Representation on Grassmann Manifolds

6 weeks ago by Vaguery

As a significant subspace clustering method, low rank representation (LRR) has attracted great attention in recent years. To further improve the performance of LRR and extend its applications, there are several issues to be resolved. The nuclear norm in LRR does not sufficiently use the prior knowledge of the rank which is known in many practical problems. The LRR is designed for vectorial data from linear spaces, thus not suitable for high dimensional data with intrinsic non-linear manifold structure. This paper proposes an extended LRR model for manifold-valued Grassmann data which incorporates prior knowledge by minimizing partial sum of singular values instead of the nuclear norm, namely Partial Sum minimization of Singular Values Representation (GPSSVR). The new model not only enforces the global structure of data in low rank, but also retains important information by minimizing only smaller singular values. To further maintain the local structures among Grassmann points, we also integrate the Laplacian penalty with GPSSVR. An effective algorithm is proposed to solve the optimization problem based on the GPSSVR model. The proposed model and algorithms are assessed on some widely used human action video datasets and a real scenery dataset. The experimental results show that the proposed methods obviously outperform other state-of-the-art methods.

dimension-reduction
feature-selection
spatial-embedding
metrics
define-your-terms
rather-interesting
representation
to-write-about
to-simulate
consider:performance-measures
consider:data-balancing
6 weeks ago by Vaguery

[1807.05283] When Are Two Gossips the Same? Types of Communication in Epistemic Gossip Protocols

6 weeks ago by Vaguery

We provide an in-depth study of the knowledge-theoretic aspects of communication in so-called gossip protocols. Pairs of agents communicate by means of calls in order to spread information---so-called secrets---within the group. Depending on the nature of such calls knowledge spreads in different ways within the group. Systematizing existing literature, we identify 18 different types of communication, and model their epistemic effects through corresponding indistinguishability relations. We then provide a classification of these relations and show its usefulness for an epistemic analysis in presence of different communication types. Finally, we explain how to formalise the assumption that the agents have common knowledge of a distributed epistemic gossip protocol.

agent-based
graph-theory
communication
artificial-life
collective-behavior
simulation
define-your-terms
rather-interesting
to-simulate
6 weeks ago by Vaguery

[1808.00722] On the Harborth constant of $C_3 oplus C_{3n}$

6 weeks ago by Vaguery

For a finite abelian group (G,+,0) the Harborth constant 𝗀(G) is the smallest integer k such that each squarefree sequence over G of length k, equivalently each subset of G of cardinality at least k, has a subsequence of length exp(G) whose sum is 0. In this paper, it is established that 𝗀(G)=3n+3 for prime n≠3 and 𝗀(C3⊕C9)=13.

group-theory
combinatorics
algorithms
rather-interesting
feature-construction
to-understand
to-write-about
an-example-would-be-useful-about-now
6 weeks ago by Vaguery

[1712.02950] CycleGAN, a Master of Steganography

6 weeks ago by Vaguery

CycleGAN (Zhu et al. 2017) is one recent successful approach to learn a transformation between two image distributions. In a series of experiments, we demonstrate an intriguing property of the model: CycleGAN learns to "hide" information about a source image into the images it generates in a nearly imperceptible, high-frequency signal. This trick ensures that the generator can recover the original sample and thus satisfy the cyclic consistency requirement, while the generated image remains realistic. We connect this phenomenon with adversarial attacks by viewing CycleGAN's training procedure as training a generator of adversarial examples and demonstrate that the cyclic consistency loss causes CycleGAN to be especially vulnerable to adversarial attacks.

adversarial-attacks
machine-learning
deep-learning
generative-models
tricksy-humans
steganography-as-a-side-effect
rather-interesting
to-write-about
6 weeks ago by Vaguery

[1808.02679] Age of Information Upon Decisions

6 weeks ago by Vaguery

We consider an M/M/1 update-and-decide system where Poisson distributed decisions are made based on the received updates. We propose to characterize the freshness of the received updates at decision epochs with Age upon Decisions (AuD). Under the first-come-first-served policy (FCFS), the closed form average AuD is derived. We show that the average AuD of the system is determined by the arrival rate and the service rate, and is independent of the decision rate. Thus, merely increasing the decision rate does not improve the timeliness of decisions. Nevertheless, increasing the arrival rate and the service rate simultaneously can decrease the average AuD efficiently.

queueing-theory
information-theory
planning
simulation
rather-interesting
to-write-about
6 weeks ago by Vaguery

"Created Facts and the Flawed Ontology of Copyright Law" by Justin Hughes

6 weeks ago by Vaguery

It is black letter doctrine that facts are not copyrightable: facts are discovered, not created—so they will always lack the originality needed for copyright protection. As straightforward as this reasoning seems, it is fundamentally flawed. Using the “social facts” theory of philosopher John Searle, this Article explores a variety of “created facts” cases—designation systems, systematic evaluations, and privately written laws—in which original expression from private individuals is adopted by social convention and generates facts in our social reality. In the course of this discussion, the paper places facts in their historical and philosophical context, explores how courts conflate facts with expressions of fact, and explains the difference between social facts created by expression and the “facts” of literature and fiction. Having established that the copyrighted works discussed in these cases produce facts, the question arises whether copyright's merger doctrine eliminates the copyright protection—a result that is both seemingly harsh and seemingly necessary. This Article proposes a recalibration of the merger doctrine to acknowledge that “created facts” are a unique situation in which the incentive of copyright is needed not just to generate the expression, but also needed to generate the facts. Reprinted by permission of the publisher.

law
pragmatism
philosophy
rather-interesting
to-understand
6 weeks ago by Vaguery

CTK Insights » Blog Archive A pizza with a hole - CTK Insights

7 weeks ago by Vaguery

Now we are in a position to tackle the problem from the Crux. Any line through the center of the rectangular pizza divides it into equal parts. One of these lines stands out. It's the one that divides into equal parts the circular hole, that's the line that passes through the hole's center. Thus to solve the problem we cut through the centers of the rectangle and that of the hole.

But that's not the only solution. In fact there are infinitely many more, although to find any of these in a constructive manner is rather difficult, if not impossible.

mathematical-recreations
plane-geometry
rather-interesting
open-questions
nudge-targets
consider:looking-to-see
compass-and-straightedge
But that's not the only solution. In fact there are infinitely many more, although to find any of these in a constructive manner is rather difficult, if not impossible.

7 weeks ago by Vaguery

Supermultiplexed optical imaging and barcoding with engineered polyynes | Nature Methods

7 weeks ago by Vaguery

Optical multiplexing has a large impact in photonics, the life sciences and biomedicine. However, current technology is limited by a 'multiplexing ceiling' from existing optical materials. Here we engineered a class of polyyne-based materials for optical supermultiplexing. We achieved 20 distinct Raman frequencies, as 'Carbon rainbow', through rational engineering of conjugation length, bond-selective isotope doping and end-capping substitution of polyynes. With further probe functionalization, we demonstrated ten-color organelle imaging in individual living cells with high specificity, sensitivity and photostability. Moreover, we realized optical data storage and identification by combinatorial barcoding, yielding to our knowledge the largest number of distinct spectral barcodes to date. Therefore, these polyynes hold great promise in live-cell imaging and sorting as well as in high-throughput diagnostics and screening.

materials-science
nanotechnology
indistinguishable-from-magic
molecular-design
molecular-biology
to-write-about
rather-interesting
7 weeks ago by Vaguery

@dynamicCallable: Unix Tools as Swift Functions – The Always Right Institute – Almost always sometimes definitely right.

7 weeks ago by Vaguery

A new feature in Swift 5 are Dynamic Callable’s. We combine this with the related Dynamic Member Lookup feature to expose the filesystem and Unix shell commands as regular Swift objects and functions.

Wait what?!

swift
programming-language
library
rather-interesting
to-do
Wait what?!

7 weeks ago by Vaguery

CTK Insights » Blog Archive It Never Stops with Pythagoras - CTK Insights

7 weeks ago by Vaguery

In the previous blog I described a discovery of Hirotaka Ebisui and an observation by Thanos Kalogerakis, both concerning what's known as Vecten's configuration. Vecten's configuration is a generalization of the famous Bride's Chair that underlies Euclid I.47, generally identified as the proof of the Pythagorean Theorem, although by now there are hundreds of them. In response to the previous post, Long Huynh Huu has expanded the two results, with the tools from linear algebra. To cut that introduction short, earlier today I was informed by Thanos Kalogerakis of a post by Carlos Hugo Olivera Días at the Peru Geometrico facebook group that adds another (and most fundamental at that) link to the just described chain of discoveries.

plane-geometry
mathematical-recreations
rather-interesting
discovery
feature-construction
to-write-about
7 weeks ago by Vaguery

[1706.06571] The Distribution of Knots in the Petaluma Model

7 weeks ago by Vaguery

The representation of knots by petal diagrams (Adams et al. 2012) naturally defines a sequence of distributions on the set of knots. In this article we establish some basic properties of this randomized knot model. We prove that in the random n-petal model the probability of obtaining every specific knot type decays to zero as n, the number of petals, grows. In addition we improve the bounds relating the crossing number and the petal number of a knot. This implies that the n-petal model represents at least exponentially many distinct knots.

Past approaches to showing, in some random models, that individual knot types occur with vanishing probability, rely on the prevalence of localized connect summands as the complexity of the knot increases. However this phenomenon is not clear in other models, including petal diagrams, random grid diagrams, and uniform random polygons. Thus we provide a new approach to investigate this question.

knot-theory
representation
rather-interesting
to-write-about
topology
feature-construction
Past approaches to showing, in some random models, that individual knot types occur with vanishing probability, rely on the prevalence of localized connect summands as the complexity of the knot increases. However this phenomenon is not clear in other models, including petal diagrams, random grid diagrams, and uniform random polygons. Thus we provide a new approach to investigate this question.

7 weeks ago by Vaguery

Are Pop Lyrics Getting More Repetitive?

7 weeks ago by Vaguery

In 1977, the great computer scientist Donald Knuth published a paper called The Complexity of Songs, which is basically one long joke about the repetitive lyrics of newfangled music (example quote: "the advent of modern drugs has led to demands for still less memory, and the ultimate improvement of Theorem 1 has consequently just been announced").

I'm going to try to test this hypothesis with data. I'll be analyzing the repetitiveness of a dataset of 15,000 songs that charted on the Billboard Hot 100 between 1958 and 2017.

visualization
graphic-design
data-analysis
essay
looking-to-see
javascript
rather-interesting
via:cdzombak
I'm going to try to test this hypothesis with data. I'll be analyzing the repetitiveness of a dataset of 15,000 songs that charted on the Billboard Hot 100 between 1958 and 2017.

7 weeks ago by Vaguery

[1808.08414] Unsupervised Hypergraph Feature Selection via a Novel Point-Weighting Framework and Low-Rank Representation

8 weeks ago by Vaguery

Feature selection methods are widely used in order to solve the 'curse of dimensionality' problem. Many proposed feature selection frameworks, treat all data points equally; neglecting their different representation power and importance. In this paper, we propose an unsupervised hypergraph feature selection method via a novel point-weighting framework and low-rank representation that captures the importance of different data points. We introduce a novel soft hypergraph with low complexity to model data. Then, we formulate the feature selection as an optimization problem to preserve local relationships and also global structure of data. Our approach for global structure preservation helps the framework overcome the problem of unavailability of data labels in unsupervised learning. The proposed feature selection method treats with different data points based on their importance in defining data structure and representation power. Moreover, since the robustness of feature selection methods against noise and outlier is of great importance, we adopt low-rank representation in our model. Also, we provide an efficient algorithm to solve the proposed optimization problem. The computational cost of the proposed algorithm is lower than many state-of-the-art methods which is of high importance in feature selection tasks. We conducted comprehensive experiments with various evaluation methods on different benchmark data sets. These experiments indicate significant improvement, compared with state-of-the-art feature selection methods.

classification
feature-selection
rather-interesting
hypergraphs
to-understand
machine-learning
to-do
8 weeks ago by Vaguery

[1807.10492] Limits with Signed Digit Streams

8 weeks ago by Vaguery

We work with the signed digit representation of abstract real numbers, which roughly is the binary representation enriched by the additional digit -1. The main objective of this paper is an algorithm which takes a sequence of signed digit representations of reals and returns the signed digit representation of their limit, if the sequence converges. As a first application we use this algorithm together with Heron's method to build up an algorithm which converts the signed digit representation of a non-negative real number into the signed digit representation of its square root. Instead of writing the algorithms first and proving their correctness afterwards, we work the other way round, in the tradition of program extraction from proofs. In fact we first give constructive proofs, and from these proofs we then compute the extracted terms, which is the desired algorithm. The correctness of the extracted term follows directly by the Soundness Theorem of program extraction. In order to get the extracted term from some proofs which are often quite long, we use the proof assistant Minlog. However, to apply the extracted terms, the programming language Haskell is useful. Therefore after each proof we show a notation of the extracted term, which can be easily rewritten as a definition in Haskell.

algebra
representation
algorithms
rather-interesting
to-write-about
consider:looking-to-see
nudge-targets
consider:simulation
8 weeks ago by Vaguery

[1806.01823] Integrating Flexible Normalization into Mid-Level Representations of Deep Convolutional Neural Networks

8 weeks ago by Vaguery

Deep convolutional neural networks (CNNs) are becoming increasingly popular models to predict neural responses in visual cortex. However, contextual effects, which are prevalent in neural processing and in perception, are not explicitly handled by current CNNs, including those used for neural prediction. In primary visual cortex, neural responses are modulated by stimuli spatially surrounding the classical receptive field in rich ways. These effects have been modeled with divisive normalization approaches, including flexible models where spatial normalization is recruited only to the degree responses from center and surround locations are deemed statistically dependent. We propose a flexible normalization model applied to mid-level representations of deep CNNs as a tractable way to study contextual normalization mechanisms in mid-level visual areas. This approach captures non-trivial spatial dependencies among mid-level features in CNNs, such as those present in textures and other visual stimuli that arise from tiling high order features, geometrically. We expect that the proposed approach can make predictions about when spatial normalization might be recruited in mid-level cortical areas. We also expect this approach to be useful as part of the CNN toolkit, therefore going beyond more restrictive fixed forms of normalization.

neural-networks
deep-learning
design-patterns
rather-interesting
to-write-about
consider:other-design-patterns
8 weeks ago by Vaguery

[1309.3441] On the shape of subword complexity sequences of finite words

8 weeks ago by Vaguery

The subword complexity of a word w over a finite alphabet is a function that assigns for each positive integer n, the number of distinct subwords of length n in w. The subword complexity of a word is a good measure of the randomness of the word and gives insight to what the word itself looks like. In this paper, we discuss the properties of subword complexity sequences, and consider different variables that influence their shape. We also compute the number of distinct subword complexity sequences for certain lengths of words over different alphabets, and state some conjectures about the growth of these numbers.

strings
combinatorics
enumeration
pattern-discovery
complexity-measures
information-theory
rather-interesting
to-write-about
for-puzzles
you-know-for-kids
8 weeks ago by Vaguery

[1810.04909] Tangent method for the arctic curve arising from freezing boundaries

8 weeks ago by Vaguery

In the paper arXiv:1803.11463, the authors study the arctic curve arising in random tilings of some planar domains with an arbitrary distribution of defects on one edge. Using the tangent method they derive a parametric equation for portions of arctic curve in terms of an arbitrary piecewise differentiable function that describes the defect distribution. When this distribution presents "freezing" intervals, other portions of arctic curve appear and typically have a cusp. These freezing boundaries can be of two types, respectively with maximal or minimal density of defects. Our purpose here is to extend the tangent method derivation of arXiv:1803.11463 to include these portions, hence providing the proof of the conjectures made in arXiv:1803.11463.

combinatorics
tiling
phase-transitions
arctic-curve
statistical-mechanics
looking-to-see
rather-interesting
to-write-about
to-simulate
8 weeks ago by Vaguery

[1812.02907] Caustics of Poncelet polygons and classical extremal polynomials

8 weeks ago by Vaguery

A comprehensive analysis of periodic trajectories of billiards within ellipses in the Euclidean plane is presented. The novelty of the approach is based on a relationship recently established by the authors between periodic billiard trajectories and extremal polynomials on the systems of d intervals on the real line and ellipsoidal billiards in d-dimensional space. Even in the planar case, systematically studied in the present paper it leads to new results in characterizing n periodic trajectories vs. so-called n elliptic periodic trajectories, which are n-periodic in elliptical coordinates. The characterizations are done both in terms of the underlying elliptic curve and divisors on it and in terms of polynomial functional equations, like Pell's equation. This new approach also sheds light on some classical results. In particular we connect search for caustics which generate periodic trajectories with three classical classes of extremal polynomials on two intervals, introduced by Zolotarev and Akhiezer. The main classifying tool are winding numbers, for which we provide several interpretations, including one in terms of numbers of points of alternance of extremal polynomials. The latter implies important inequality between the winding numbers, which as a consequence, provides another proof of monotonicity of rotation numbers. A complete catalog of billiard trajectories with small periods is provided for n=3,4,5,6 along with an effective search for caustics. As a byproduct, an intriguing connection between Cayle type conditions and discriminantly separable polynomials has been observed for all those small periods.

dynamical-systems
billiards
polynomials
plane-geometry
rather-interesting
8 weeks ago by Vaguery

Largest and Smallest Convex Hulls for Imprecise Points | SpringerLink

8 weeks ago by Vaguery

Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls, measured by length and by area. Generally we assume the imprecision region to be a square, but we discuss the case where it is a segment or circle as well. We give polynomial time algorithms for several variants of this problem, ranging in running time from O(nlog n) to O(n 13), and prove NP-hardness for some other variants.

computational-geometry
plane-geometry
optimization
uncertainty
imprecision
rather-interesting
to-write-about
nudge-targets
8 weeks ago by Vaguery

[1712.08911] Largest and Smallest Area Triangles on Imprecise Points

8 weeks ago by Vaguery

Assume we are given a set of parallel line segments in the plane, and we wish to place a point on each line segment such that the resulting point set maximizes or minimizes the area of the largest or smallest triangle in the set. We analyze the complexity of the four resulting computational problems, and we show that three of them admit polynomial-time algorithms, while the fourth is NP-hard. Specifically, we show that maximizing the largest triangle can be done in O(n2) time (or in O(nlogn) time for unit segments); minimizing the largest triangle can be done in O(n2logn) time; maximizing the smallest triangle is NP-hard; but minimizing the smallest triangle can be done in O(n2) time. We also discuss to what extent our results can be generalized to polygons with k>3 sides.

computational-geometry
rather-interesting
approximation
plane-geometry
optimization
to-write-about
nudge-targets
consider:looking-to-see
8 weeks ago by Vaguery

[1712.05081] Linear time Minimum Area All-flush Triangles Circumscribing a Convex Polygon

8 weeks ago by Vaguery

We study the problem of computing the minimum area triangle that circumscribes a given n-sided convex polygon touching edge-to-edge. In other words, we compute the minimum area triangle that is the intersection of 3 half-planes out of n half-planes defined by a given convex polygon. Building on the Rotate-and-Kill technique {arXiv:1707.04071}, we propose an algorithm that solves the problem in O(n) time, improving the best-known O(nlogn) time algorithms given in [A. Aggarwal et. al. DCG94; B. Schieber. SODA95}. Our algorithm computes all the locally minimal area circumscribing triangles touching edge-to-edge.

computational-geometry
algorithms
plane-geometry
rather-interesting
to-write-about
nudge-targets
consider:looking-to-see
8 weeks ago by Vaguery

[1705.11035] Maximum-Area Triangle in a Convex Polygon, Revisited

8 weeks ago by Vaguery

We revisit the following problem: Given a convex polygon P, find the largest-area inscribed triangle. We show by example that the linear-time algorithm presented in 1979 by Dobkin and Snyder for solving this problem fails. We then proceed to show that with a small adaptation, their approach does lead to a quadratic-time algorithm. We also present a more involved O(nlogn) time divide-and-conquer algorithm. Also we show by example that the algorithm presented in 1979 by Dobkin and Snyder for finding the largest-area k-gon that is inscribed in a convex polygon fails to find the optimal solution for k=4. Finally, we discuss the implications of our discoveries on the literature.

computational-geometry
optimization
plane-geometry
rather-interesting
to-write-about
oopsie
nudge-targets
consider:looking-to-see
8 weeks ago by Vaguery

[1707.04071] Maximal Area Triangles in a Convex Polygon

8 weeks ago by Vaguery

The widely known linear time algorithm for computing the maximum area triangle in a convex polygon was found incorrect recently by Keikha et. al.(arXiv:1705.11035). We present an alternative algorithm in this paper. Comparing to the only previously known correct solution, ours is much simpler and more efficient. More importantly, our new approach is powerful in solving related problems.

computational-geometry
algorithms
plane-geometry
rather-interesting
nudge-targets
consider:looking-to-see
to-write-about
8 weeks ago by Vaguery

The coolest way to generate combinations - ScienceDirect

8 weeks ago by Vaguery

We present a practical and elegant method for generating all

-combinations (binary strings with

zeros and

ones): Identify the shortest prefix ending in 010 or 011 (or the entire string if no such prefix exists), and rotate it by one position to the right. This iterative rule gives an order to

-combinations that is circular and genlex. Moreover, the rotated portion of the string always contains at most four contiguous runs of zeros and ones, so every iteration can be achieved by transposing at most two pairs of bits. This leads to an efficient loopless and branchless implementation that consists only of two variables and six assignment statements. The order also has a number of striking similarities to colex order, especially its recursive definition and ranking algorithm. In the light of these similarities we have named our order cool-lex!

combinatorics
algorithms
rather-interesting
to-write-about
-combinations (binary strings with

zeros and

ones): Identify the shortest prefix ending in 010 or 011 (or the entire string if no such prefix exists), and rotate it by one position to the right. This iterative rule gives an order to

-combinations that is circular and genlex. Moreover, the rotated portion of the string always contains at most four contiguous runs of zeros and ones, so every iteration can be achieved by transposing at most two pairs of bits. This leads to an efficient loopless and branchless implementation that consists only of two variables and six assignment statements. The order also has a number of striking similarities to colex order, especially its recursive definition and ranking algorithm. In the light of these similarities we have named our order cool-lex!

8 weeks ago by Vaguery

[1807.08178] DP-Colorings of Hypergraphs

8 weeks ago by Vaguery

Classical problems in hypergraph coloring theory are to estimate the minimum number of edges, m2(r) (respectively, m∗2(r)), in a non-2-colorable r-uniform (respectively, r-uniform and simple) hypergraph. The best currently known bounds are

c⋅r/logr‾‾‾‾‾‾√⋅2r⩽m2(r)⩽C⋅r2⋅2randc′⋅r−ε⋅4r⩽m∗2(r)⩽C′⋅r4⋅4r,

for any fixed ε>0 and some c, c′, C, C′>0 (where c′ may depend on ε). In this paper we consider the same problems in the context of DP-coloring (also known as correspondence coloring), which is a generalization of list coloring introduced by Dvořák and Postle and related to local conflict coloring studied independently by Fraigniaud, Heinrich, and Kosowski. Let m̃2(r) (respectively, m̃∗2(r)) denote the minimum number of edges in a non-2-DP-colorable r-uniform (respectively, r-uniform and simple) hypergraph. By definition, m̃2(r)⩽m2(r) and m̃∗2(r)⩽m∗2(r).

While the proof of the bound m∗2(r)=Ω(r−34r) due to Erdős and Lovász also works for m̃∗2(r), we show that the trivial lower bound m̃2(r)⩾2r−1 is asymptotically tight, i.e., m̃2(r)⩽(1+o(1))2r−1. On the other hand, when r⩾2 is even, we prove that the lower bound m̃2(r)⩾2r−1 is not sharp, i.e., m̃2(r)⩾2r−1+1. Whether this result holds for any odd r remains an open problem. Nevertheless, we find it tempting to conjecture that the difference m̃2(r)−2r−1 tends to infinity with r.

set-theory
hypergraphs
graph-theory
graph-coloring
combinatorics
rather-interesting
to-write-about
c⋅r/logr‾‾‾‾‾‾√⋅2r⩽m2(r)⩽C⋅r2⋅2randc′⋅r−ε⋅4r⩽m∗2(r)⩽C′⋅r4⋅4r,

for any fixed ε>0 and some c, c′, C, C′>0 (where c′ may depend on ε). In this paper we consider the same problems in the context of DP-coloring (also known as correspondence coloring), which is a generalization of list coloring introduced by Dvořák and Postle and related to local conflict coloring studied independently by Fraigniaud, Heinrich, and Kosowski. Let m̃2(r) (respectively, m̃∗2(r)) denote the minimum number of edges in a non-2-DP-colorable r-uniform (respectively, r-uniform and simple) hypergraph. By definition, m̃2(r)⩽m2(r) and m̃∗2(r)⩽m∗2(r).

While the proof of the bound m∗2(r)=Ω(r−34r) due to Erdős and Lovász also works for m̃∗2(r), we show that the trivial lower bound m̃2(r)⩾2r−1 is asymptotically tight, i.e., m̃2(r)⩽(1+o(1))2r−1. On the other hand, when r⩾2 is even, we prove that the lower bound m̃2(r)⩾2r−1 is not sharp, i.e., m̃2(r)⩾2r−1+1. Whether this result holds for any odd r remains an open problem. Nevertheless, we find it tempting to conjecture that the difference m̃2(r)−2r−1 tends to infinity with r.

8 weeks ago by Vaguery

[1807.09885] A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time

8 weeks ago by Vaguery

We consider the classic scheduling problem of minimizing the total weighted flow-time on a single machine (min-WPFT), when preemption is allowed. In this problem, we are given a set of n jobs, each job having a release time rj, a processing time pj, and a weight wj. The flow-time of a job is defined as the amount of time the job spends in the system before it completes; that is, Fj=Cj−rj, where Cj is the completion time of job. The objective is to minimize the total weighted flow-time of jobs.

This NP-hard problem has been studied quite extensively for decades. In a recent breakthrough, Batra, Garg, and Kumar presented a {\em pseudo-polynomial} time algorithm that has an O(1) approximation ratio. The design of a truly polynomial time algorithm, however, remained an open problem. In this paper, we show a transformation from pseudo-polynomial time algorithms to polynomial time algorithms in the context of min-WPFT. Our result combined with the result of Batra, Garg, and Kumar settles the long standing conjecture that there is a polynomial time algorithm with O(1)-approximation for min-WPFT.

approximation
mathematical-programming
optimization
computational-complexity
NP-hard
heuristics
rather-interesting
to-write-about
This NP-hard problem has been studied quite extensively for decades. In a recent breakthrough, Batra, Garg, and Kumar presented a {\em pseudo-polynomial} time algorithm that has an O(1) approximation ratio. The design of a truly polynomial time algorithm, however, remained an open problem. In this paper, we show a transformation from pseudo-polynomial time algorithms to polynomial time algorithms in the context of min-WPFT. Our result combined with the result of Batra, Garg, and Kumar settles the long standing conjecture that there is a polynomial time algorithm with O(1)-approximation for min-WPFT.

8 weeks ago by Vaguery

[1808.06313] Binomial coefficients and multifactorial numbers through generative grammars

8 weeks ago by Vaguery

In this paper, the formal derivative operator defined with respect to context-free grammars is used to prove some properties about binomial coefficients and multifactorial numbers. In addition, we extend the formal derivative operator to matrix grammars and show that multifactorial numbers can also be generated.

combinatorics
strings
rather-interesting
counting
to-write-about
8 weeks ago by Vaguery

[1809.07390] A general framework for secondary constructions of bent and plateaued functions

8 weeks ago by Vaguery

In this work, we employ the concept of {\em composite representation} of Boolean functions, which represents an arbitrary Boolean function as a composition of one Boolean function and one vectorial function, for the purpose of specifying new secondary constructions of bent/plateaued functions. This representation gives a better understanding of the existing secondary constructions and it also allows us to provide a general construction framework of these objects. This framework essentially gives rise to an {\em infinite number} of possibilities to specify such secondary construction methods (with some induced sufficient conditions imposed on initial functions) and in particular we solve several open problems in this context. We provide several explicit methods for specifying new classes of bent/plateaued functions and demonstrate through examples that the imposed initial conditions can be easily satisfied. Our approach is especially efficient when defining new bent/plateaued functions on larger variable spaces than initial functions. For instance, it is shown that the indirect sum methods and Rothaus' construction are just special cases of this general framework and some explicit extensions of these methods are given. In particular, similarly to the basic indirect sum method of Carlet, we show that it is possible to derive (many) secondary constructions of bent functions without any additional condition on initial functions apart from the requirement that these are bent functions. In another direction, a few construction methods that generalize the secondary constructions which do not extend the variable space of the employed initial functions are also proposed.

representation
boolean-functions
decomposition
construction
inverse-problems
rather-interesting
Walsh-polynomials
to-write-about
consider:feature-discovery
8 weeks ago by Vaguery

[1810.04692] Probability distributions related to tilings of non-convex Polygons

8 weeks ago by Vaguery

This paper is based on the study of random lozenge tilings of non-convex polygonal regions with interacting non-convexities (cuts) and the corresponding asymptotic kernel as in [3] and [4] (discrete tacnode kernel). Here this kernel is used to find the probability distributions and joint probability distributions for the fluctuation of tiles along lines in between the cuts. These distributions are new.

combinatorics
tiling
counting
rather-interesting
phase-transitions
condensed-matter
statistical-mechanics
feature-extraction
representation
to-write-about
consider:feature-discovery
8 weeks ago by Vaguery

[1808.00453] The Erdos-Szekeres problem and an induced Ramsey question

9 weeks ago by Vaguery

Motivated by the Erdos-Szekeres convex polytope conjecture in Rd, we initiate the study of the following induced Ramsey problem for hypergraphs. Given integers n>k≥5, what is the minimum integer gk(n) such that any k-uniform hypergraph on gk(n) vertices with the property that any set of k+1 vertices induces 0, 2, or 4 edges, contains an independent set of size n. Our main result shows that gk(n)>2cnk−4, where c=c(k).

combinatorics
hypergraphs
constraint-satisfaction
consequences-of-the-rules
rather-interesting
to-write-about
9 weeks ago by Vaguery

QAnon and Pinterest Is Just the Beginning | Hapgood

9 weeks ago by Vaguery

How Pinterest’s Aggressive Recommendation Engine Makes This Worse

About a year ago I wrote an article on how Pinterest’s recommendation engine makes this situation far worse. I showed how after just 14 minutes of browsing, a new user with some questions about vaccines could move from pins on “How to Make the Perfect Egg” to something out of the Infowarverse:

social-media
recommendation-engines
spam
propaganda
rather-interesting
cultural-predation
About a year ago I wrote an article on how Pinterest’s recommendation engine makes this situation far worse. I showed how after just 14 minutes of browsing, a new user with some questions about vaccines could move from pins on “How to Make the Perfect Egg” to something out of the Infowarverse:

9 weeks ago by Vaguery

Democracy as an information system — Crooked Timber

9 weeks ago by Vaguery

Democracy is an information system.

That’s the starting place of our new paper: “Common-Knowledge Attacks on Democracy.” In it, we look at democracy through the lens of information security, trying to understand the current waves of Internet disinformation attacks. Specifically, we wanted to explain why the same disinformation campaigns that act as a stabilizing influence in Russia are destabilizing in the United States.

The answer revolves around the different ways autocracies and democracies work as information systems. We start by differentiating between two types of knowledge that societies use in their political systems. The first is common political knowledge, which is the body of information that people in a society broadly agree on. People agree on who the rulers are and what their claim to legitimacy is. People agree broadly on how their government works, even if they don’t like it. In a democracy, people agree about how elections work: how districts are created and defined, how candidates are chosen, and that their votes count—even if only roughly and imperfectly.

social-norms
democracy
cultural-dynamics
propaganda
public-policy
political-economy
rather-interesting
epidemiology
feature-construction
discriminators
fascism
signaling
That’s the starting place of our new paper: “Common-Knowledge Attacks on Democracy.” In it, we look at democracy through the lens of information security, trying to understand the current waves of Internet disinformation attacks. Specifically, we wanted to explain why the same disinformation campaigns that act as a stabilizing influence in Russia are destabilizing in the United States.

The answer revolves around the different ways autocracies and democracies work as information systems. We start by differentiating between two types of knowledge that societies use in their political systems. The first is common political knowledge, which is the body of information that people in a society broadly agree on. People agree on who the rulers are and what their claim to legitimacy is. People agree broadly on how their government works, even if they don’t like it. In a democracy, people agree about how elections work: how districts are created and defined, how candidates are chosen, and that their votes count—even if only roughly and imperfectly.

9 weeks ago by Vaguery

[1811.08759] Using AI to Design Stone Jewelry

9 weeks ago by Vaguery

Jewelry has been an integral part of human culture since ages. One of the most popular styles of jewelry is created by putting together precious and semi-precious stones in diverse patterns. While technology is finding its way in the production process of such jewelry, designing it remains a time-consuming and involved task. In this paper, we propose a unique approach using optimization methods coupled with machine learning techniques to generate novel stone jewelry designs at scale. Our evaluation shows that designs generated by our approach are highly likeable and visually appealing.

generative-art
design
aesthetics
rather-interesting
performance-measure
to-write-about
user-centric-design
9 weeks ago by Vaguery

Knots and Narnias |

9 weeks ago by Vaguery

Say you’re walking north across a meadow surrounded by hills when you come across a solitary doorframe with no door inside it. Stranger still, through the doorway you see not the hills to the north of the field but a desert vista. Consumed by curiosity and heedless of danger, you cross the threshold into the desert. The sun beats down on your bare head; you see a vulture off in the distance. In sudden panic you spin around; fortunately the doorway is still there. You run through the doorway back into the field, grateful that the portal works both ways.

Now what?

knot-theory
mathematical-recreations
rather-interesting
inspiration
to-write-about
Now what?

9 weeks ago by Vaguery

[1804.02851] Whale swarm algorithm with the mechanism of identifying and escaping from extreme point for multimodal function optimization

9 weeks ago by Vaguery

Most real-world optimization problems often come with multiple global optima or local optima. Therefore, increasing niching metaheuristic algorithms, which devote to finding multiple optima in a single run, are developed to solve these multimodal optimization problems. However, there are two difficulties urgently to be solved for most existing niching metaheuristic algorithms: how to set the optimal values of niching parameters for different optimization problems, and how to jump out of the local optima efficiently. These two difficulties limited their practicality largely. Based on Whale Swarm Algorithm (WSA) we proposed previously, this paper presents a new multimodal optimizer named WSA with Iterative Counter (WSA-IC) to address these two difficulties. In the one hand, WSA-IC improves the iteration rule of the original WSA for multimodal optimization, which removes the need of specifying different values of attenuation coefficient for different problems to form multiple subpopulations, without introducing any niching parameter. In the other hand, WSA-IC enables the identification of extreme point during iterations relying on two new parameters (i.e., stability threshold Ts and fitness threshold Tf), to jump out of the located extreme point. Moreover, the convergence of WSA-IC is proved. Finally, the proposed WSA-IC is compared with several niching metaheuristic algorithms on CEC2015 niching benchmark test functions and five additional classical multimodal functions with high dimensions. The experimental results demonstrate that WSA-IC statistically outperforms other niching metaheuristic algorithms on most test functions.

metaheuristics
biological-metaphor-of-the-month
to-write-about
actually
rather-interesting
9 weeks ago by Vaguery

[1706.07900] Tree-Residue Vertex-Breaking: a new tool for proving hardness

9 weeks ago by Vaguery

In this paper, we introduce a new problem called Tree-Residue Vertex-Breaking (TRVB): given a multigraph $G$ some of whose vertices are marked "breakable," is it possible to convert $G$ into a tree via a sequence of "vertex-breaking" operations (replacing a degree-$k$ breakable vertex by $k$ degree-$1$ vertices, disconnecting the $k$ incident edges)?

We characterize the computational complexity of TRVB with any combination of the following additional constraints: $G$ must be planar, $G$ must be a simple graph, the degree of every breakable vertex must belong to an allowed list $B$, and the degree of every unbreakable vertex must belong to an allowed list $U$. The two results which we expect to be most generally applicable are that (1) TRVB is polynomially solvable when breakable vertices are restricted to have degree at most $3$; and (2) for any $k \ge 4$, TRVB is NP-complete when the given multigraph is restricted to be planar and to consist entirely of degree-$k$ breakable vertices. To demonstrate the use of TRVB, we give a simple proof of the known result that Hamiltonicity in max-degree-$3$ square grid graphs is NP-hard.

We also demonstrate a connection between TRVB and the Hypergraph Spanning Tree problem. This connection allows us to show that the Hypergraph Spanning Tree problem in $k$-uniform $2$-regular hypergraphs is NP-complete for any $k \ge 4$, even when the incidence graph of the hypergraph is planar.

feature-construction
graph-theory
computational-complexity
rather-interesting
explanation
to-write-about
We characterize the computational complexity of TRVB with any combination of the following additional constraints: $G$ must be planar, $G$ must be a simple graph, the degree of every breakable vertex must belong to an allowed list $B$, and the degree of every unbreakable vertex must belong to an allowed list $U$. The two results which we expect to be most generally applicable are that (1) TRVB is polynomially solvable when breakable vertices are restricted to have degree at most $3$; and (2) for any $k \ge 4$, TRVB is NP-complete when the given multigraph is restricted to be planar and to consist entirely of degree-$k$ breakable vertices. To demonstrate the use of TRVB, we give a simple proof of the known result that Hamiltonicity in max-degree-$3$ square grid graphs is NP-hard.

We also demonstrate a connection between TRVB and the Hypergraph Spanning Tree problem. This connection allows us to show that the Hypergraph Spanning Tree problem in $k$-uniform $2$-regular hypergraphs is NP-complete for any $k \ge 4$, even when the incidence graph of the hypergraph is planar.

9 weeks ago by Vaguery

**related tags**

Copy this bookmark: