rather-interesting   2047

« earlier    

[1612.09443] Transversals in Latin arrays with many distinct symbols
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
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
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
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)
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
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
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
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 
19 days ago by Vaguery
[1803.08823] A high-bias, low-variance introduction to Machine Learning for physicists
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
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 
24 days ago by Vaguery
Props in Network Theory | Azimuth
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 
26 days ago by WMTrenfield
Props in Network Theory | Azimuth
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 
27 days ago by Vaguery
Solved: A Decades-Old Ansel Adams Mystery - Atlas Obscura
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 
27 days ago by Vaguery
Generating function - Wikipedia
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 
4 weeks ago by Vaguery
Scientists Still Can't Decide How to Define a Tree - The Atlantic
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
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
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
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
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
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 
7 weeks ago by Vaguery

« earlier    

related tags

abstraction  academia  academic-culture  agent-based  algebra  algorithms  aperiodic-tiles  approximation  architecture  art-history  artificial-life  astronomy  audio  augmented-reality  autocatalysis  biochemistry  bioinformatics  biological-engineering  biology  bond-diagrams  book  boolean-functions  boolean-networks  cad  category-theory  cellular-automata  chess  circles-and-arrows  classification  clustering  codes  collective-intelligence  combinatorics-in-practice  combinatorics  communities-of-practice  competition  computational-complexity  computational-geometry  computer-science  condensed-matter  conferences  consider:embedding-space  consider:feature-discovery  consider:for-code  consider:generalization  consider:generalizations  consider:genetic-programming  consider:integrating-nlp  consider:looking-at-code  consider:looking-to-see  consider:open-questions  consider:parametrization  consider:performance-measures  consider:representation  consider:simulation  consider:stress-testing  constraint-satisfaction  continued-fractions  controversy  cooking  copyright  cryptography  crystals  cultural-assumptions  cultural-norms  data-analysis  data-fusion  decision-making  deep-learning  define-your-terms  demonstrations-of-the-mangle  diffy-qs  digital-humanities  digitization  disintermediation-in-action  distance-measures  distance  distant-reading  diversity  domino-tiling  doom  dynamical-systems  education  electronics  emergent-design  engineering-criticism  engineering-design  enumeration  essay  ethology  evolutionary-biology  evolutionary-dynamics  existence-proof  experiment  experimental-design  explanation  exploitation  exploration  exploratory-data-analysis  feature-construction  feature-extraction  finite-elements-methods  functional-programming  game-theory  gender  generative-art  graph-coloring  graph-theory  graphics  hardware-changes-models  have-done  heuristics  hey-i-know-this-guy  history-of-science  hmmmmmm  hosted-solutions  image-processing  inference  infinities  information-theory  infrastructure  integer-programming  interpolation  interpretability  introduction  inverse-problems  kauffmania  law  leading-questions  learning-by-watching  lecture  linear-programming  literary-criticism  looking-to-see  machine-learning  magic-squares  materials-science  mathematical-programming  mathematical-recreations  mathematics  matrices  maybe-not-but-still  meta-simulation  metrics  microbiology  migration  misleading-trends  modeling  models-and-modes  multiobjective-optimization  multitask-learning  nanotechnology  natural-language-processing  network-theory  neural-networks  neuroscience  nudge-targets  nudge  number-theory  numerical-methods  open-access  open-problems  open-source  operations-research  optimization  origin-of-life  packing  pedagogy  performance-measure  perl  phase-transitions  philosophy-of-science  photography  phylogenetics  physics!  planning  political-economy  population-biology  prediction  probability-theory  problematic-at-best  programming-language  proof  proofs  publishing  puzzles  quantum-computing  quantums  quines  random-processes  rational-numbers  reaction-networks  recurrent-networks  recurrent-neural-networks  replicators  representation  review  rewriting-systems  robotics  robustness  sampling  security  self-organization  semiotics  sensors  several-reasons  sharing  signal-processing  simulation  social-engineering  social-norms  software-engineering  sorting  speech-synthesis  statistics  swarms  systems-biology  taxonomy  testing  text  the-mangle-in-practice  theoretical-biology  theoretical-chemistry  tiling  time-series  to--do  to-emulate  to-read  to-simulate  to-try  to-understand  to-write-about  topology  unsupervised-learning  user-experience  user-interface  utilities  utopianism  visualization  what-gets-measured-gets-fudged  workshop 

Copy this bookmark: