to-write-about   1164

« earlier    

[1808.00453] The Erdos-Szekeres problem and an induced Ramsey question
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
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
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
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 |
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 
yesterday by Vaguery
[1804.02851] Whale swarm algorithm with the mechanism of identifying and escaping from extreme point for multimodal function optimization
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
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 
yesterday by Vaguery
How many landmarks are enough to characterize shape and size variation?
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
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
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
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 
2 days ago by Vaguery
Remembering Roy Gold, Who was Not Excessively Interested in Books – The Public Domain Review
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
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 
3 days ago by Vaguery
Alan Turing, On computable numbers | Joel David Hamkins
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 
3 days ago by Vaguery
Bending the Law of Sines | The Aperiodical
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 
3 days ago by Vaguery
Stability Criteria for Complex Microbial Communities | bioRxiv
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
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
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
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
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

« earlier    

related tags

(it-ain't)  (totally)  a-bit-backwards-though  academic-culture  activism  actually  aesthetics  algebra  algorithms  also-note-presentation  amusing  analogy  anthropology-of-data  approximation  architecture  artificial-life  astronomy  audio  autobiographical  automata  benchmarking  biological-metaphor-of-the-month  biology  book-art  cannot-read  capitalism  category-theory  cellular-automata  chronology  circuits  cladistics  classes  climate-change  clustering  cognition  collaboration  collective-behavior  colonialism  combinatorics  community-formation  competition  complexology  computability  computational-complexity  computational-criticism  computational-geometry  computational-methods  computer-science  con  conjecture  consequences-of-the-rules  consider:algorithms  consider:classification  consider:evolution-of-code  consider:feature-discovery  consider:genetic-programming  consider:looking-to-see  consider:multiobjective-selection  consider:performance-measures  consider:pragmatics-of-a-tree  consider:rediscovery  consider:representation  consider:req  consider:robustness  consider:simulation  consider:the-mangle  consider:what-are-we-doing-to-our-machines?  constraint-satisfaction  construction  contingency  continued-fractions  cooperation  could-be-clearer  criticism  cultural-assumptions  cultural-engineering  curiosity  data-analysis  data-balancing  deep-learning  define-your-terms  definition  design  developmental-biology  dimension-reduction  discrete-and-continuous-sittin-in-a-tree  ecology  emergence  equivalences-of-motion-over-different-paths  evolutionary-biology  experimentation  explanation  exploding-dots  explorations  extreme-values  fascism  feature-construction  feature-extraction  feature-selection  financial-crisis  floating-point  forgery  foundational-work  frechet-distance  fuzzy  game-theory  games  generalization  generative-art  generative-models  genetic-programming  geometry  graph-layout  graph-theory  grassmannian  group-theory  halting-problem  have-explored  have-read  heterogeneity  heuristics  hey-i-know-this-guy  history-is-a-feature-not-a-bug  history-of-science  history  hoaxes  however  hypergraphs  i-remember-it-well  inference  inspiration  integer-programming  interview  it's-more-complicated-than-you-think  julia-language  knot-theory  languages  learning-from-data  learning-in-public  linear-algebra  linguistics  literary-criticism  looking-to-see  machine-learning  management  materials-science  mathematical-programming  mathematical-recreations  mathematics  medicine  memoir  metafiction  metaheuristics  metrics  microsoft  migration  modeling  models-and-modes  models  motivation  nanohistory  natural-language-processing  neoliberalism  neural-networks  nonlinear-dynamics  nudge-targets  nudge  nudgelike  number-theory  numerical-methods  occam-ain't-evolved  ontology  open-questions  operations-research  optimization  organizational-behavior  out-of-the-box  p2p  parasitism  parataxis  paratext  paratexts  pattern-discovery  patterns  pedagogy  peer-production  performance-measure  performative-writing  permutations  philosophy-of-art  philosophy-of-engineering  philosophy  plane-geometry  planning  political-economy  politics  posthumanism-and-responsibility  pragmatics  probability-theory  problem-solving  programming-language  programming  projects  proof  psychology  public-health  puzzles  python  quotes  rather-interesting  rather-odd  recurrent-networks  reinforcement-learning  remembering-our-dead  representation  req  reworks  robustness  schemes  science-studies  semantics  sequences  series  set-theory  side-effects  signal-processing  simulation  smalltalk  social-affordances  social-dynamics  social-justice  social-networks  social-norms  software-synthesis  sorting  speaking-as  statistics  structions  style-transfer  symbolic-regression  syntax  teams  technology  testing  text-editor  the-ludic-in-law  the-mangle-in-practice  the-use-of-books  theoretical-biology  thinking-about-being  tiling  to-cite  to-do  to-follow  to-generalize  to-promote  to-simulate  to-translate  to-understand  to-watch  training-data  translation  type-theory  user-centric-design  user-interface  utopianism  video  visualization  web  wedge-product  what-gets-possible-gets-done  worldview 

Copy this bookmark:



description:


tags: