**to-write-about**1164

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

yesterday 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
yesterday by Vaguery

[1706.04290] A general method for lower bounds on fluctuations of random variables

yesterday by Vaguery

There are many ways of establishing upper bounds on fluctuations of random variables, but there is no systematic approach for lower bounds. As a result, lower bounds are unknown in many important problems. This paper introduces a general method for lower bounds on fluctuations. The method is used to obtain new results for the stochastic traveling salesman problem, the stochastic minimal matching problem, the random assignment problem, the Sherrington-Kirkpatrick model of spin glasses, first-passage percolation and random matrices. A long list of open problems is provided at the end.

open-questions
extreme-values
probability-theory
representation
rather-odd
nudge-targets
consider:looking-to-see
to-write-about
yesterday by Vaguery

[1802.07029] On a fully fuzzy framework for minimax mixed integer linear programming

yesterday by Vaguery

In this work, we present a modeling framework for minimax mixed 0-1 fuzzy linear problems. It is based on extending the usual rewriting of crisp minimax problems via auxiliary variables to model the maximum of a finite set of fuzzy linear functions. We establish that the considered problem can be equivalently formulated as a multiple objective mixed integer programming problem. The framework is applied to a fully fuzzy version of the capacitated center facility location problem.

representation
fuzzy
operations-research
integer-programming
models-and-modes
to-write-about
could-be-clearer
yesterday by Vaguery

[1811.08759] Using AI to Design Stone Jewelry

yesterday 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
yesterday by Vaguery

Knots and Narnias |

yesterday 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?

yesterday by Vaguery

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

yesterday 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
yesterday by Vaguery

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

yesterday 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.

yesterday by Vaguery

How many landmarks are enough to characterize shape and size variation?

2 days ago by Vaguery

Accurate characterization of morphological variation is crucial for generating reliable results and conclusions concerning changes and differences in form. Despite the prevalence of landmark-based geometric morphometric (GM) data in the scientific literature, a formal treatment of whether sampled landmarks adequately capture shape variation has remained elusive. Here, I introduce LaSEC (Landmark Sampling Evaluation Curve), a computational tool to assess the fidelity of morphological characterization by landmarks. This task is achieved by calculating how subsampled data converge to the pattern of shape variation in the full dataset as landmark sampling is increased incrementally. While the number of landmarks needed for adequate shape variation is dependent on individual datasets, LaSEC helps the user (1) identify under- and oversampling of landmarks; (2) assess robustness of morphological characterization; and (3) determine the number of landmarks that can be removed without compromising shape information. In practice, this knowledge could reduce time and cost associated with data collection, maintain statistical power in certain analyses, and enable the incorporation of incomplete, but important, specimens to the dataset. Results based on simulated shape data also reveal general properties of landmark data, including statistical consistency where sampling additional landmarks has the tendency to asymptotically improve the accuracy of morphological characterization. As landmark-based GM data become more widely adopted, LaSEC provides a systematic approach to evaluate and refine the collection of shape data––a goal paramount for accumulation and analysis of accurate morphological information.

inference
data-analysis
looking-to-see
rather-interesting
training-data
data-balancing
to-write-about
2 days ago by Vaguery

[1811.09620] TimbreTron: A WaveNet(CycleGAN(CQT(Audio))) Pipeline for Musical Timbre Transfer

2 days ago by Vaguery

In this work, we address the problem of musical timbre transfer, where the goal is to manipulate the timbre of a sound sample from one instrument to match another instrument while preserving other musical content, such as pitch, rhythm, and loudness. In principle, one could apply image-based style transfer techniques to a time-frequency representation of an audio signal, but this depends on having a representation that allows independent manipulation of timbre as well as high-quality waveform generation. We introduce TimbreTron, a method for musical timbre transfer which applies "image" domain style transfer to a time-frequency representation of the audio signal, and then produces a high-quality waveform using a conditional WaveNet synthesizer. We show that the Constant Q Transform (CQT) representation is particularly well-suited to convolutional architectures due to its approximate pitch equivariance. Based on human perceptual evaluations, we confirmed that TimbreTron recognizably transferred the timbre while otherwise preserving the musical content, for both monophonic and polyphonic samples.

style-transfer
neural-networks
feature-extraction
signal-processing
audio
to-write-about
consider:performance-measures
2 days ago by Vaguery

[cs/0610153] Most Programs Stop Quickly or Never Halt

2 days ago by Vaguery

Since many real-world problems arising in the fields of compiler optimisation, automated software engineering, formal proof systems, and so forth are equivalent to the Halting Problem--the most notorious undecidable problem--there is a growing interest, not only academically, in understanding the problem better and in providing alternative solutions. Halting computations can be recognised by simply running them; the main difficulty is to detect non-halting programs. Our approach is to have the probability space extend over both space and time and to consider the probability that a random N-bit program has halted by a random time. We postulate an a priori computable probability distribution on all possible runtimes and we prove that given an integer k>0, we can effectively compute a time bound T such that the probability that an N-bit program will eventually halt given that it has not halted by T is smaller than 2^{-k}. We also show that the set of halting programs (which is computably enumerable, but not computable) can be written as a disjoint union of a computable set and a set of effectively vanishing probability. Finally, we show that ``long'' runtimes are effectively rare. More formally, the set of times at which an N-bit program can stop after the time 2^{N+constant} has effectively zero density.

halting-problem
computer-science
rather-interesting
looking-to-see
to-write-about
ReQ
computational-complexity
probability-theory
2 days ago by Vaguery

Reinforcement Learning with Prediction-Based Rewards

2 days ago by Vaguery

We’ve developed Random Network Distillation (RND), a prediction-based method for encouraging reinforcement learning agents to explore their environments through curiosity, which for the first time1 exceeds average human performance on Montezuma’s Revenge. RND achieves state-of-the-art performance, periodically finds all 24 rooms and solves the first level without using demonstrations or having access to the underlying state of the game.

RND incentivizes visiting unfamiliar states by measuring how hard it is to predict the output of a fixed random neural network on visited states. In unfamiliar states it’s hard to guess the output, and hence the reward is high. It can be applied to any reinforcement learning algorithm, is simple to implement and efficient to scale. Below we release a reference implementation of RND that can reproduce the results from our paper.

machine-learning
reinforcement-learning
curiosity
the-mangle-in-practice
to-write-about
also-note-presentation
RND incentivizes visiting unfamiliar states by measuring how hard it is to predict the output of a fixed random neural network on visited states. In unfamiliar states it’s hard to guess the output, and hence the reward is high. It can be applied to any reinforcement learning algorithm, is simple to implement and efficient to scale. Below we release a reference implementation of RND that can reproduce the results from our paper.

2 days ago by Vaguery

Remembering Roy Gold, Who was Not Excessively Interested in Books – The Public Domain Review

3 days ago by Vaguery

In this gentle memorial, Nicholas Jeeves takes us on a turn through a Borgesian library of defacements. Jeeves’ quarry, the (inventive and invented) Professor Roy Gold, would seem to have been an outsider artist of his books, and his dust-jacket daubings leave an ambiguous legacy. Should such biblio-graffiti be accounted irreverent mischief? Does it betray anti-bookishness in the secret heart of a bookish man? Or is something else afoot? Perhaps, under the right conditions, doodling can become something like a theory of reading. After all, what is to be done with all our paper books in an age of textual dematerialization? Roy Gold stands over our shoulders, brush in hand…

parataxis
the-use-of-books
reworks
to-write-about
rather-interesting
memoir
book-art
3 days ago by Vaguery

When Optimising Code Measure

3 days ago by Vaguery

This is a truism that lots of people quote, but it can be hard to remember, especially in the heat of battle (as it were). Rather fortunately it came to mind just when needed, as I found something completely unexpected.

I was writing a simple implementation of the Fermat difference of squares method of factoring. This involves writing the number to be factored as - you guessed it - the difference of two squares. If n=a2−b2

n

=

a

2

−

b

2

then n=(a−b)(a+b)

n

=

(

a

−

b

)

(

a

+

b

)

and we have a factorisation (provided we don't have a−b=1

a

−

b

=

1

).

the-mangle-in-practice
looking-to-see
learning-in-public
computer-science
computational-complexity
rather-interesting
to-write-about
contingency
I was writing a simple implementation of the Fermat difference of squares method of factoring. This involves writing the number to be factored as - you guessed it - the difference of two squares. If n=a2−b2

n

=

a

2

−

b

2

then n=(a−b)(a+b)

n

=

(

a

−

b

)

(

a

+

b

)

and we have a factorisation (provided we don't have a−b=1

a

−

b

=

1

).

3 days ago by Vaguery

Alan Turing, On computable numbers | Joel David Hamkins

3 days ago by Vaguery

What I was extremely surprised to find, however, and what I want to tell you about today, is that despite the title of the article, Turing adopts an incorrect approach to the theory of computable numbers. His central definition is what is now usually regarded as a mistaken way to proceed with this concept.

Let me explain. Turing defines that a computable real number is one whose decimal (or binary) expansion can be enumerated by a finite procedure, by what we now call a Turing machine. You can see this in the very first sentence of his paper, and he elaborates on and confirms this definition in detail later on in the paper.

computability
mathematics
number-theory
algorithms
rather-interesting
history-of-science
representation
to-write-about
ReQ
Let me explain. Turing defines that a computable real number is one whose decimal (or binary) expansion can be enumerated by a finite procedure, by what we now call a Turing machine. You can see this in the very first sentence of his paper, and he elaborates on and confirms this definition in detail later on in the paper.

3 days ago by Vaguery

Bending the Law of Sines | The Aperiodical

3 days ago by Vaguery

You can tile a plane with a repeated single triangle shape. But for most triangles you need to put same sides together, usually to group pairs of triangles into parallelograms, as shown above. You can’t just put any sides together. This of course reflects the Law of Sines, which says the side lengths are proportional to the sines of their opposite angles: you can’t get both the angles AND the side lengths in agreeable proportions.

But something unexpected happens when we add curves. For tiling we need equal amounts of concave and convex arc. The only way to do that is with two shorter concave sides joining a longer convex side, as shown below.

tiling
rather-interesting
learning-in-public
experimentation
construction
to-write-about
But something unexpected happens when we add curves. For tiling we need equal amounts of concave and convex arc. The only way to do that is with two shorter concave sides joining a longer convex side, as shown below.

3 days ago by Vaguery

Stability Criteria for Complex Microbial Communities | bioRxiv

3 days ago by Vaguery

Competition and mutualism are inevitable processes in microbial ecology, and a central question is which and how many taxa will persist in the face of these interactions. Ecological theory has demonstrated that when direct, pairwise interactions among a group of species are too numerous, or too strong, then the coexistence of these species will be unstable to any slight perturbation. This instability worsens when mutualistic interactions complement competition. Here, we refine and to some extent overturn that understanding, by considering explicitly the resources that microbes consume and produce. In contrast to more complex organisms, microbial cells consume primarily abiotic resources, and mutualistic interactions are often mediated by these same abiotic resources through the mechanism of cross-feeding. Our model therefore considers the consumption and production of a set of abiotic resources by a group of microbial species. We show that if microbes consume, but do not produce resources, then any positive equilibrium will always be stable to small perturbations. We go on to show that in the presence of crossfeeding, stability is no longer guaranteed. However, stability still holds when mutualistic interations are either symmetric, or sufficiently weak.

theoretical-biology
community-formation
ecology
competition
cooperation
rather-interesting
nonlinear-dynamics
to-write-about
3 days ago by Vaguery

[1803.09473] code2vec: Learning Distributed Representations of Code

3 days ago by Vaguery

We present a neural model for representing snippets of code as continuous distributed vectors ("code embeddings"). The main idea is to represent a code snippet as a single fixed-length code vector, which can be used to predict semantic properties of the snippet. This is performed by decomposing code to a collection of paths in its abstract syntax tree, and learning the atomic representation of each path simultaneously with learning how to aggregate a set of them. We demonstrate the effectiveness of our approach by using it to predict a method's name from the vector representation of its body. We evaluate our approach by training a model on a dataset of 14M methods. We show that code vectors trained on this dataset can predict method names from files that were completely unobserved during training. Furthermore, we show that our model learns useful method name vectors that capture semantic similarities, combinations, and analogies. Comparing previous techniques over the same data set, our approach obtains a relative improvement of over 75%, being the first to successfully predict method names based on a large, cross-project, corpus. Our trained model, visualizations and vector similarities are available as an interactive online demo at this http URL. The code, data, and trained models are available at this https URL.

representation
genetic-programming
(it-ain't)
deep-learning
neural-networks
feature-construction
to-write-about
discrete-and-continuous-sittin-in-a-tree
3 days ago by Vaguery

[1812.01717] Towards Accurate Generative Models of Video: A New Metric & Challenges

3 days ago by Vaguery

Recent advances in deep generative models have lead to remarkable progress in synthesizing high quality images. Following their successful application in image processing and representation learning, an important next step is to consider videos. Learning generative models of video is a much harder task, requiring a model to capture the temporal dynamics of a scene, in addition to the visual presentation of objects. Although recent attempts at formulating generative models of video have had some success, current progress is hampered by (1) the lack of qualitative metrics that consider visual quality, temporal coherence, and diversity of samples, and (2) the wide gap between purely synthetic video datasets and challenging real-world datasets in terms of complexity. To this extent we propose Fréchet Video Distance (FVD), a new metric for generative models of video based on FID, and StarCraft 2 Videos (SCV), a collection of progressively harder datasets that challenge the capabilities of the current iteration of generative models for video. We conduct a large-scale human study, which confirms that FVD correlates well with qualitative human judgment of generated videos, and provide initial benchmark results on SCV.

metrics
Frechet-distance
generative-models
representation
rather-interesting
video
feature-construction
to-write-about
3 days ago by Vaguery

[1710.00992] DimReader: Axis lines that explain non-linear projections

3 days ago by Vaguery

Non-linear dimensionality reduction (NDR) methods such as LLE and t-SNE are popular with visualization researchers and experienced data analysts, but present serious problems of interpretation. In this paper, we present DimReader, a technique that recovers readable axes from such techniques. DimReader is based on analyzing infinitesimal perturbations of the dataset with respect to variables of interest. The perturbations define exactly how we want to change each point in the original dataset and we measure the effect that these changes have on the projection. The recovered axes are in direct analogy with the axis lines (grid lines) of traditional scatterplots. We also present methods for discovering perturbations on the input data that change the projection the most. The calculation of the perturbations is efficient and easily integrated into programs written in modern programming languages. We present results of DimReader on a variety of NDR methods and datasets both synthetic and real-life, and show how it can be used to compare different NDR methods. Finally, we discuss limitations of our proposal and situations where further research is needed.

user-interface
visualization
dimension-reduction
rather-interesting
data-analysis
explanation
the-mangle-in-practice
to-write-about
to-do
3 days ago by Vaguery

[1811.01721] Rethinking floating point for deep learning

3 days ago by Vaguery

Reducing hardware overhead of neural networks for faster or lower power inference and training is an active area of research. Uniform quantization using integer multiply-add has been thoroughly investigated, which requires learning many quantization parameters, fine-tuning training or other prerequisites. Little effort is made to improve floating point relative to this baseline; it remains energy inefficient, and word size reduction yields drastic loss in needed dynamic range. We improve floating point to be more energy efficient than equivalent bit width integer hardware on a 28 nm ASIC process while retaining accuracy in 8 bits with a novel hybrid log multiply/linear add, Kulisch accumulation and tapered encodings from Gustafson's posit format. With no network retraining, and drop-in replacement of all math and float32 parameters via round-to-nearest-even only, this open-sourced 8-bit log float is within 0.9% top-1 and 0.2% top-5 accuracy of the original float32 ResNet-50 CNN model on ImageNet. Unlike int8 quantization, it is still a general purpose floating point arithmetic, interpretable out-of-the-box. Our 8/38-bit log float multiply-add is synthesized and power profiled at 28 nm at 0.96x the power and 1.12x the area of 8/32-bit integer multiply-add. In 16 bits, our log float multiply-add is 0.59x the power and 0.68x the area of IEEE 754 float16 fused multiply-add, maintaining the same signficand precision and dynamic range, proving useful for training ASICs as well.

numerical-methods
machine-learning
representation
the-mangle-in-practice
to-write-about
to-cite
motivation
3 days ago by Vaguery

**related tags**

Copy this bookmark: