**rather-interesting**2047

[1612.09443] Transversals in Latin arrays with many distinct symbols

23 hours ago by Vaguery

An array is row-Latin if no symbol is repeated within any row. An array is Latin if it and its transpose are both row-Latin. A transversal in an n×n array is a selection of n different symbols from different rows and different columns. We prove that every n×n Latin array containing at least (2−2‾√)n2 distinct symbols has a transversal. Also, every n×n row-Latin array containing at least 14(5−5‾√)n2 distinct symbols has a transversal. Finally, we show by computation that every Latin array of order 7 has a transversal, and we describe all smaller Latin arrays that have no transversal.

combinatorics
existence-proof
rather-interesting
nudge-targets
consider:looking-to-see
23 hours ago by Vaguery

[1708.09571] Anagram-free colourings of graph subdivisions

23 hours ago by Vaguery

An anagram is a word of the form WP where W is a non-empty word and P is a permutation of W. A vertex colouring of a graph is anagram-free if no subpath of the graph is an anagram. Anagram-free graph colouring was independently introduced by Kam\v{c}ev, {\L}uczak and Sudakov and ourselves. In this paper we introduce the study of anagram-free colourings of graph subdivisions. We show that every graph has an anagram-free 8-colourable subdivision. The number of division vertices per edge is exponential in the number of edges. For trees, we construct anagram-free 10-colourable subdivisions with fewer division vertices per edge. Conversely, we prove lower bounds, in terms of division vertices per edge, on the anagram-free chromatic number for subdivisions of the complete graph and subdivisions of complete trees of bounded degree.

combinatorics
graph-theory
graph-coloring
computational-complexity
rather-interesting
nudge-targets
consider:looking-to-see
23 hours ago by Vaguery

[1803.07694] Defective and Clustered Graph Colouring

23 hours ago by Vaguery

Consider the following two ways to colour the vertices of a graph where the requirement that adjacent vertices get distinct colours is relaxed. A colouring has "defect" d if each monochromatic component has maximum degree at most d. A colouring has "clustering" c if each monochromatic component has at most c vertices. This paper surveys research on these types of colourings, where the first priority is to minimise the number of colours, with small defect or small clustering as a secondary goal. List colouring variants are also considered. The following graph classes are studied: outerplanar graphs, planar graphs, graphs embeddable in surfaces, graphs with given maximum degree, graphs with given maximum average degree, graphs excluding a given subgraph, graphs with linear crossing number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdi\`ere parameter, graphs with given circumference, graphs excluding a fixed graph as an immersion, graphs with given thickness, graphs with given stack- or queue-number, graphs excluding Kt as a minor, graphs excluding Ks,t as a minor, and graphs excluding an arbitrary graph H as a minor. Several open problems are discussed.

combinatorics
graph-theory
algorithms
rather-interesting
computational-complexity
nudge-targets
consider:performance-measures
23 hours ago by Vaguery

[1805.02356] Multimodal Machine Translation with Reinforcement Learning

23 hours ago by Vaguery

Multimodal machine translation is one of the applications that integrates computer vision and language processing. It is a unique task given that in the field of machine translation, many state-of-the-arts algorithms still only employ textual information. In this work, we explore the effectiveness of reinforcement learning in multimodal machine translation. We present a novel algorithm based on the Advantage Actor-Critic (A2C) algorithm that specifically cater to the multimodal machine translation task of the EMNLP 2018 Third Conference on Machine Translation (WMT18). We experiment our proposed algorithm on the Multi30K multilingual English-German image description dataset and the Flickr30K image entity dataset. Our model takes two channels of inputs, image and text, uses translation evaluation metrics as training rewards, and achieves better results than supervised learning MLE baseline models. Furthermore, we discuss the prospects and limitations of using reinforcement learning for machine translation. Our experiment results suggest a promising reinforcement learning solution to the general task of multimodal sequence to sequence learning.

natural-language-processing
machine-learning
multitask-learning
rather-interesting
algorithms
performance-measure
to-write-about
23 hours ago by Vaguery

With Great Power Comes Poor Latent Codes: Representation Learning in VAEs (Pt. 2)

23 hours ago by Vaguery

A machine learning idea I find particularly compelling is that of embeddings, representations, encodings: all of these vector spaces that can seem nigh-on magical when you zoom in and see the ways that a web of concepts can be beautifully mapped into mathematical space. I’ve spent enough time in the weeds of parameter optimization and vector algebra to know that calling any aspect of machine learning “magical” is starry-eyed even as I say it, but: approaches like this are unavoidably tantalizing because they offer the possibility of finding some optimal representation of concepts, a “optimal mathematical language” with which we can feed all of the world’s information to our machines.

machine-learning
the-mangle-in-practice
neural-networks
representation
rather-interesting
to-write-about
23 hours ago by Vaguery

[1802.03676] Differentiable Dynamic Programming for Structured Prediction and Attention

11 days ago by Vaguery

Dynamic programming (DP) solves a variety of structured combinatorial problems by iteratively breaking them down into smaller subproblems. In spite of their versatility, DP algorithms are usually non-differentiable, which hampers their use as a layer in neural networks trained by backpropagation. To address this issue, we propose to smooth the max operator in the dynamic programming recursion, using a strongly convex regularizer. This allows to relax both the optimal value and solution of the original combinatorial problem, and turns a broad class of DP algorithms into differentiable operators. Theoretically, we provide a new probabilistic perspective on backpropagating through these DP operators, and relate them to inference in graphical models. We derive two particular instantiations of our framework, a smoothed Viterbi algorithm for sequence prediction and a smoothed DTW algorithm for time-series alignment. We showcase these instantiations on two structured prediction tasks and on structured and sparse attention for neural machine translation.

representation
time-series
numerical-methods
deep-learning
rather-interesting
nudge-targets
consider:representation
11 days ago by Vaguery

[1803.05859v3] Neural Network Quine

11 days ago by Vaguery

Self-replication is a key aspect of biological life that has been largely overlooked in Artificial Intelligence systems. Here we describe how to build and train self-replicating neural networks. The network replicates itself by learning to output its own weights. The network is designed using a loss function that can be optimized with either gradient-based or non-gradient-based methods. We also describe a method we call regeneration to train the network without explicit optimization, by injecting the network with predictions of its own parameters. The best solution for a self-replicating network was found by alternating between regeneration and optimization steps. Finally, we describe a design for a self-replicating neural network that can solve an auxiliary task such as MNIST image classification. We observe that there is a trade-off between the network's ability to classify images and its ability to replicate, but training is biased towards increasing its specialization at image classification at the expense of replication. This is analogous to the trade-off between reproduction and other tasks observed in nature. We suggest that a self-replication mechanism for artificial intelligence is useful because it introduces the possibility of continual improvement through natural selection.

artificial-life
machine-learning
quines
rather-interesting
to-write-about
hey-I-know-this-guy
11 days ago by Vaguery

[1801.07155] Continued fractions and orderings on the Markov numbers

19 days ago by Vaguery

Markov numbers are integers that appear in the solution triples of the Diophantine equation, x2+y2+z2=3xyz, called the Markov equation. A classical topic in number theory, these numbers are related to many areas of mathematics such as combinatorics, hyperbolic geometry, approximation theory and cluster algebras.

There is a natural map from the rational numbers between zero and one to the Markov numbers. In this paper, we prove two conjectures seen in Martin Aigner's book, Markov's theorem and 100 years of the uniqueness conjecture, that determine an ordering on subsets of the Markov numbers based on their corresponding rational.

The proof uses the cluster algebra of the torus with one puncture and a resulting reformulation of the conjectures in terms of continued fractions. The key step is to analyze the difference in the numerator of a continued fraction when an operation is applied to its entries.

number-theory
continued-fractions
rather-interesting
to-write-about
consider:looking-to-see
consider:generalizations
There is a natural map from the rational numbers between zero and one to the Markov numbers. In this paper, we prove two conjectures seen in Martin Aigner's book, Markov's theorem and 100 years of the uniqueness conjecture, that determine an ordering on subsets of the Markov numbers based on their corresponding rational.

The proof uses the cluster algebra of the torus with one puncture and a resulting reformulation of the conjectures in terms of continued fractions. The key step is to analyze the difference in the numerator of a continued fraction when an operation is applied to its entries.

19 days ago by Vaguery

[1803.08823] A high-bias, low-variance introduction to Machine Learning for physicists

19 days ago by Vaguery

Machine Learning (ML) is one of the most exciting and dynamic areas of modern research and application. The purpose of this review is to provide an introduction to the core concepts and tools of machine learning in a manner easily understood and intuitive to physicists. The review begins by covering fundamental concepts in ML and modern statistics such as the bias-variance tradeoff, overfitting, regularization, and generalization before moving on to more advanced topics in both supervised and unsupervised learning. Topics covered in the review include ensemble models, deep learning and neural networks, clustering and data visualization, energy-based models (including MaxEnt models and Restricted Boltzmann Machines), and variational methods. Throughout, we emphasize the many natural connections between ML and statistical physics. A notable aspect of the review is the use of Python notebooks to introduce modern ML/statistical packages to readers using physics-inspired datasets (the Ising Model and Monte-Carlo simulations of supersymmetric decays of proton-proton collisions). We conclude with an extended outlook discussing possible uses of machine learning for furthering our understanding of the physical world as well as open problems in ML where physicists maybe able to contribute. (Notebooks are available at this https URL )

rather-interesting
machine-learning
text
review
19 days ago by Vaguery

Cooking the books – Almost looks like work

24 days ago by Vaguery

Since Christmas, at my house we’ve been cooking with 5 ingredients or fewer thanks to the acquisition of Jamie Oliver’s new book, the contents of which are mostly available online here. The recipes are unanimously very tasty, but that’s besides the point. The real mark of culinary excellence (in my humble opinion) is how efficiently one can buy ingredients to make as many of the recipes as possible in one shopping trip. Let’s investigate while the lamb is on.

Each of the 135 recipes in the book consists of 5 ingredients, some of which overlap. It is therefore not necessary to purchase 675 ingredients, there are actually only 239 unique ones. (Yes, I did spend a Sunday morning typing 675 individual ingredients into a spreadsheet.)

The question is then this:

In which order should I buy my ingredients to maximise the number of possible recipes as a function of number of ingredients?

Let’s start simply, and look at the frequency of occurrence of the ingredients.

mathematical-recreations
looking-to-see
cooking
data-analysis
leading-questions
rather-interesting
Each of the 135 recipes in the book consists of 5 ingredients, some of which overlap. It is therefore not necessary to purchase 675 ingredients, there are actually only 239 unique ones. (Yes, I did spend a Sunday morning typing 675 individual ingredients into a spreadsheet.)

The question is then this:

In which order should I buy my ingredients to maximise the number of possible recipes as a function of number of ingredients?

Let’s start simply, and look at the frequency of occurrence of the ingredients.

24 days ago by Vaguery

Props in Network Theory | Azimuth

26 days ago by WMTrenfield

We start with circuits made solely of ideal perfectly conductive wires. Then we consider circuits with passive linear components like resistors, capacitors and inductors. Finally we turn on the power and consider circuits that also have voltage and current sources.

And here’s the cool part: each kind of circuit corresponds to a prop that pure mathematicians would eventually invent on their own! So, what’s good for engineers is often mathematically natural too.

commentary: while abstract, it might be worth trying to understand this stuff

network-theory
abstraction
rather-interesting
models-and-modes
circles-and-arrows
bond-diagrams
to-write-about
to-understand
functional-programming
category-theory
via:Vaguery
And here’s the cool part: each kind of circuit corresponds to a prop that pure mathematicians would eventually invent on their own! So, what’s good for engineers is often mathematically natural too.

commentary: while abstract, it might be worth trying to understand this stuff

26 days ago by WMTrenfield

Props in Network Theory | Azimuth

27 days ago by Vaguery

We start with circuits made solely of ideal perfectly conductive wires. Then we consider circuits with passive linear components like resistors, capacitors and inductors. Finally we turn on the power and consider circuits that also have voltage and current sources.

And here’s the cool part: each kind of circuit corresponds to a prop that pure mathematicians would eventually invent on their own! So, what’s good for engineers is often mathematically natural too.

network-theory
abstraction
rather-interesting
models-and-modes
circles-and-arrows
bond-diagrams
to-write-about
to-understand
functional-programming
category-theory
And here’s the cool part: each kind of circuit corresponds to a prop that pure mathematicians would eventually invent on their own! So, what’s good for engineers is often mathematically natural too.

27 days ago by Vaguery

Solved: A Decades-Old Ansel Adams Mystery - Atlas Obscura

27 days ago by Vaguery

WHEN YOU LOOK AT THE image above, what do you think of? Most will probably take in the beauty of its subjects, the mountain Denali and nearby Wonder Lake. A photographer might admire the skill of its creator, Ansel Adams. Adventurers may feel the urge to climb.

Donald Olson sees all that and something else: a mystery. He wants to know the moment it was taken. An astrophysicist and forensic astronomer, Olson uses quantitative methods to answer questions raised by artwork, literature, and historical accounts—not the heady ones, but the basic, surprisingly slippery who, what, when, and where.

photography
art-history
rather-interesting
inverse-problems
astronomy
via:kottke.org
Donald Olson sees all that and something else: a mystery. He wants to know the moment it was taken. An astrophysicist and forensic astronomer, Olson uses quantitative methods to answer questions raised by artwork, literature, and historical accounts—not the heady ones, but the basic, surprisingly slippery who, what, when, and where.

27 days ago by Vaguery

Generating function - Wikipedia

4 weeks ago by Vaguery

In mathematics, a generating function is a way of encoding an infinite sequence of numbers (an) by treating them as the coefficients of a power series. The sum of this infinite series is the generating function. Unlike an ordinary series, this formal series is allowed to diverge, meaning that the generating function is not always a true function and the "variable" is actually an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem.[1] One can generalize to formal series in more than one indeterminate, to encode information about arrays of numbers indexed by several natural numbers.

There are various types of generating functions, including ordinary generating functions, exponential generating functions, Lambert series, Bell series, and Dirichlet series; definitions and examples are given below. Every sequence in principle has a generating function of each type (except that Lambert and Dirichlet series require indices to start at 1 rather than 0), but the ease with which they can be handled may differ considerably. The particular generating function, if any, that is most useful in a given context will depend upon the nature of the sequence and the details of the problem being addressed.

Generating functions are often expressed in closed form (rather than as a series), by some expression involving operations defined for formal series. These expressions in terms of the indeterminate x may involve arithmetic operations, differentiation with respect to x and composition with (i.e., substitution into) other generating functions; since these operations are also defined for functions, the result looks like a function of x. Indeed, the closed form expression can often be interpreted as a function that can be evaluated at (sufficiently small) concrete values of x, and which has the formal series as its series expansion; this explains the designation "generating functions". However such interpretation is not required to be possible, because formal series are not required to give a convergent series when a nonzero numeric value is substituted for x. Also, not all expressions that are meaningful as functions of x are meaningful as expressions designating formal series; for example, negative and fractional powers of x are examples of functions that do not have a corresponding formal power series.

Generating functions are not functions in the formal sense of a mapping from a domain to a codomain. Generating functions are sometimes called generating series,[2] in that a series of terms can be said to be the generator of its sequence of term coefficients.

mathematics
via:arthegall
to-understand
rather-interesting
to-write-about
nudge-targets
hmmmmmm
There are various types of generating functions, including ordinary generating functions, exponential generating functions, Lambert series, Bell series, and Dirichlet series; definitions and examples are given below. Every sequence in principle has a generating function of each type (except that Lambert and Dirichlet series require indices to start at 1 rather than 0), but the ease with which they can be handled may differ considerably. The particular generating function, if any, that is most useful in a given context will depend upon the nature of the sequence and the details of the problem being addressed.

Generating functions are often expressed in closed form (rather than as a series), by some expression involving operations defined for formal series. These expressions in terms of the indeterminate x may involve arithmetic operations, differentiation with respect to x and composition with (i.e., substitution into) other generating functions; since these operations are also defined for functions, the result looks like a function of x. Indeed, the closed form expression can often be interpreted as a function that can be evaluated at (sufficiently small) concrete values of x, and which has the formal series as its series expansion; this explains the designation "generating functions". However such interpretation is not required to be possible, because formal series are not required to give a convergent series when a nonzero numeric value is substituted for x. Also, not all expressions that are meaningful as functions of x are meaningful as expressions designating formal series; for example, negative and fractional powers of x are examples of functions that do not have a corresponding formal power series.

Generating functions are not functions in the formal sense of a mapping from a domain to a codomain. Generating functions are sometimes called generating series,[2] in that a series of terms can be said to be the generator of its sequence of term coefficients.

4 weeks ago by Vaguery

Scientists Still Can't Decide How to Define a Tree - The Atlantic

4 weeks ago by Vaguery

If one is pressed to describe what makes a tree a tree, long life is right up there with wood and height. While many plants have a predictably limited life span (what scientists call programmed senescence), trees don’t, and many persist for centuries. In fact, that trait—indefinite growth—could be science’s tidiest demarcation of tree-ness, even more than woodiness. Yet it’s only helpful to a point. We think we know what trees are, but they slip through the fingers when we try to define them.

biology
define-your-terms
rather-interesting
taxonomy
philosophy-of-science
4 weeks ago by Vaguery

Sturgeon’s Biases – Quietstars – Medium

5 weeks ago by Vaguery

Some smart social psychologist, anthropologist or sociologist probably wrote about this seventy years ago. So I’m just going to ramble about it here for a bit, and hope that somebody smarter than I am can point me to that paper. So I know what to call it.

communities-of-practice
cultural-assumptions
cultural-norms
essay
social-norms
rather-interesting
5 weeks ago by Vaguery

[1803.01422] DAGs with NO TEARS: Smooth Optimization for Structure Learning

7 weeks ago by Vaguery

Estimating the structure of directed acyclic graphs (DAGs, also known as Bayesian networks) is a challenging problem since the search space of DAGs is combinatorial and scales superexponentially with the number of nodes. Existing approaches rely on various local heuristics for enforcing the acyclicity constraint and are not well-suited to general purpose optimization packages for their solution. In this paper, we introduce a fundamentally different strategy: We formulate the structure learning problem as a smooth, constrained optimization problem over real matrices that avoids this combinatorial constraint entirely. This is achieved by a novel characterization of acyclicity that is not only smooth but also exact. The resulting nonconvex, constrained program involves smooth functions whose gradients are easy to compute and only involve elementary matrix operations. By using existing black-box optimization routines, our method uses global search to find an optimal DAG and can be implemented in about 50 lines of Python and outperforms existing methods without imposing any structural constraints.

graph-theory
combinatorics
algorithms
rather-interesting
computational-complexity
to-understand
to-write-about
nudge-targets
consider:looking-to-see
representation
7 weeks ago by Vaguery

Context Free Art

7 weeks ago by Vaguery

Context Free is a program that generates images from written instructions called a grammar. The program follows the instructions in a few seconds to create images that can contain millions of shapes.

generative-art
rather-interesting
graphics
programming-language
to-understand
7 weeks ago by Vaguery

[1804.00222] Learning Unsupervised Learning Rules

7 weeks ago by Vaguery

A major goal of unsupervised learning is to discover data representations that are useful for subsequent tasks, without access to supervised labels during training. Typically, this goal is approached by minimizing a surrogate objective, such as the negative log likelihood of a generative model, with the hope that representations useful for subsequent tasks will arise as a side effect. In this work, we propose instead to directly target a later desired task by meta-learning an unsupervised learning rule, which leads to representations useful for that task. Here, our desired task (meta-objective) is the performance of the representation on semi-supervised classification, and we meta-learn an algorithm -- an unsupervised weight update rule -- that produces representations that perform well under this meta-objective. Additionally, we constrain our unsupervised update rule to a be a biologically-motivated, neuron-local function, which enables it to generalize to novel neural network architectures. We show that the meta-learned update rule produces useful features and sometimes outperforms existing unsupervised learning techniques. We show that the meta-learned unsupervised update rule generalizes to train networks with different widths, depths, and nonlinearities. It also generalizes to train on data with randomly permuted input dimensions and even generalizes from image datasets to a text task.

machine-learning
unsupervised-learning
rather-interesting
feature-extraction
clustering
algorithms
to-write-about
7 weeks ago by Vaguery

[1803.05316] Seven Sketches in Compositionality: An Invitation to Applied Category Theory

7 weeks ago by Vaguery

This book is an invitation to discover advanced topics in category theory through concrete, real-world examples. It aims to give a tour: a gentle, quick introduction to guide later exploration. The tour takes place over seven sketches, each pairing an evocative application, such as databases, electric circuits, or dynamical systems, with the exploration of a categorical structure, such as adjoint functors, enriched categories, or toposes.

No prior knowledge of category theory is assumed.

category-theory
book
to-read
to-write-about
via:several
rather-interesting
No prior knowledge of category theory is assumed.

7 weeks ago by Vaguery

**related tags**

Copy this bookmark: