[1609.00206] Optimal point sets determining few distinct triangles

2 hours ago

We generalize work of Erdos and Fishburn to study the structure of finite point sets that determine few distinct triangles. Specifically, we ask for a given t, what is the maximum number of points that can be placed in the plane to determine exactly t distinct triangles? Denoting this quantity by F(t), we show that F(1)=4, F(2)=5, and F(t)<48(t+1) for all t. We also completely characterize the optimal configurations for t=1,2.

optimization
plane-geometry
nudge-targets
Erdös
to-write-about
benchmarks
2 hours ago

[1610.07836v1] Classification of crescent configurations

2 hours ago

Let n points be in crescent configurations in ℝd if they lie in general position in ℝd and determine n−1 distinct distances, such that for every 1≤i≤n−1 there is a distance that occurs exactly i times. Since Erd\H{o}s' conjecture in 1989 on the existence of N sufficiently large such that no crescent configurations exist on N or more points, he, Pomerance, and Pal\'asti have given constructions for n up to 8 but nothing is yet known for n≥9. Most recently, Burt et. al. had proven that a crescent configuration on n points exists in ℝn−2 for n≥3. In this paper, we study the classification of these configurations on 4 and 5 points through graph isomorphism and rigidity. Our techniques, which can be generalized to higher dimensions, offer a new viewpoint on the problem through the lens of distance geometry and provide a systematic way to construct crescent configurations.

number-theory
to-write-about
nudge-targets
2 hours ago

[1705.02584] On the structure of large sum-free sets of integers

2 hours ago

A set of integers is called sum-free if it contains no triple of elements x,y,z with x+y=z. In this paper we provide a structural characterisation of sum-free subsets of {1,2,…,n} of density at least 2/5−c, where c is an absolute positive constant. As an application we derive a stability version of Hu's theorem [Proc. Amer. Math. Soc. 80 (1980), 711-712] about partitioning sets of integers into two sum-free subsets. We then use this result to show that the number of subsets of {1,2,…,n} which can be partitioned into two sum-free sets is Θ(24n/5), confirming a conjecture of Hancock, Staden and Treglown [arXiv:1701.04754].

number-theory
to-write-about
nudge-targets
consider:classification
2 hours ago

[1201.1317v1] On sets of integers which are both sum-free and product-free

2 hours ago

We consider sets of positive integers containing no sum of two elements in the set and also no product of two elements. We show that the upper density of such a set is strictly smaller than 1/2 and that this is best possible. Further, we also find the maximal order for the density of such sets that are also periodic modulo some positive integer.

number-theory
to-write-about
nudge-targets
2 hours ago

[math/0609373] Lowest Terms Revisited

2 hours ago

In the September 1994 issue of Math Horizons the following problem is given in the Problem Section (p. 33, Problem 5): Lowest Terms - what fraction has the smallest denominator in the interval (19/94, 17/76)? In this paper we develop a general algorithm for solving problems of this type.

mathematical-recreations
to-write-about
number-theory
nudge-targets
2 hours ago

[1303.0605v1] Explicit Constructions of Large Families of Generalized More Sums Than Differences Sets

2 hours ago

A More Sums Than Differences (MSTD) set is a set of integers A contained in {0, ..., n-1} whose sumset A+A is larger than its difference set A-A. While it is known that as n tends to infinity a positive percentage of subsets of {0, ..., n-1} are MSTD sets, the methods to prove this are probabilistic and do not yield nice, explicit constructions. Recently Miller, Orosz and Scheinerman gave explicit constructions of a large family of MSTD sets; though their density is less than a positive percentage, their family's density among subsets of {0, ..., n-1} is at least C/n^4 for some C>0, significantly larger than the previous constructions, which were on the order of 1 / 2^{n/2}. We generalize their method and explicitly construct a large family of sets A with |A+A+A+A| > |(A+A)-(A+A)|. The additional sums and differences allow us greater freedom than in Miller, Orosz and Scheinerman, and we find that for any epsilon>0 the density of such sets is at least C / n^epsilon. In the course of constructing such sets we find that for any integer k there is an A such that |A+A+A+A| - |A+A-A-A| = k, and show that the minimum span of such a set is 30.

number-theory
open-questions
generators
algorithms
to-write-about
2 hours ago

[1512.01727v3] Solving the Subset Sum Problem with Heap-Ordered Subset Trees

2 hours ago

In the field of algorithmic analysis, one of the more well-known exercises is the subset sum problem. That is, given a set of integers, determine whether one or more integers in the set can sum to a target value. Aside from the brute-force approach of verifying all combinations of integers, several solutions have been found, ranging from clever uses of various data structures to computationally-efficient approximation solutions. In this paper, a unique approach is discussed which builds upon the existing min-heap solution for positive integers, introducing a tree-based data structure influenced by the binomial heap. Termed the subset tree, this data structure solves the subset sum problem for all integers in time O(N3klogk), where N is the length of the set and k is the index of the list of subsets that is being searched.

algorithms
number-theory
rather-interesting
to-write-about
hard-problems
nudge-targets
2 hours ago

[math/0608148v2] Sets with more sums than differences

3 hours ago

Let A be a finite subset of the integers or, more generally, of any abelian group, written additively. The set A has "more sums than differences" if |A+A|>|A-A|. A set with this property is called an MSTD set. This paper gives explicit constructions of families of MSTD sets of integers.

number-theory
open-questions
to-write-about
nudge-targets
consider:classification
3 hours ago

[1608.03256v1] When Sets Can and Cannot Have MSTD Subsets

3 hours ago

A finite set of integers A is a More Sums Than Differences (MSTD) set if |A+A|>|A−A|. While almost all subsets of {0,…,n} are not MSTD, interestingly a small positive percentage are. We explore sufficient conditions on infinite sets of positive integers such that there are either no MSTD subsets, at most finitely many MSTD subsets, or infinitely many MSTD subsets. In particular, we prove no subset of the Fibonacci numbers is an MSTD set, establish conditions such that solutions to a recurrence relation have only finitely many MSTD subsets, and show there are infinitely many MSTD subsets of the primes.

number-theory
proof
to-write-about
open-questions
nudge-targets
3 hours ago

[1702.04166v1] A set of 12 numbers is not determined by its set of 4-sums

3 hours ago

We present two sets of 12 integers that have the same sets of 4-sums. The proof of the fact that a set of 12 numbers is uniquely determined by the set of its 4-sums published 50 years ago is wrong, and we demonstrate an incorrect calculation in it.

number-theory
open-questions
to-write-about
puzzles
nudge-targets
3 hours ago

[1201.6339] Epidemics on Interconnected Networks

yesterday

Populations are seldom completely isolated from their environment. Individuals in a particular geographic or social region may be considered a distinct network due to strong local ties, but will also interact with individuals in other networks. We study the susceptible-infected-recovered (SIR) process on interconnected network systems, and find two distinct regimes. In strongly-coupled network systems, epidemics occur simultaneously across the entire system at a critical infection strength βc, below which the disease does not spread. In contrast, in weakly-coupled network systems, a mixed phase exists below βc of the coupled network system, where an epidemic occurs in one network but does not spread to the coupled network. We derive an expression for the network and disease parameters that allow this mixed phase and verify it numerically. Public health implications of communities comprising these two classes of network systems are also mentioned.

epidemiology
network-theory
agent-based
rather-interesting
to-write-about
simulation
yesterday

[1212.0404] Explosive transitions to synchronization in networked phase oscillators

yesterday

We introduce a condition for an ensemble of networked phase oscillators to feature an abrupt, first-order phase transition from an unsynchronized to a synchronized state. This condition is met in a very wide spectrum of situations, and for various oscillators' initial frequency distributions. We show that the occurrence of such transitions is always accompanied by the spontaneous emergence of frequency-degree correlations in random network architectures. We also discuss ways to relax the condition, and to further extend the possibility for the first-order transition to occur, and illustrate how to engineer magnetic-like states of synchronization. Our findings thus indicate how to search for abrupt transitions in real-world applications.

coupled-oscillators
nonlinear-dynamics
to-do
to-write-about
rather-interesting
yesterday

[0711.1778] Modules identification by a Dynamical Clustering algorithm based on chaotic R"ossler oscillators

2 days ago

A new dynamical clustering algorithm for the identification of modules in complex networks has been recently introduced \cite{BILPR}. In this paper we present a modified version of this algorithm based on a system of chaotic Roessler oscillators and we test its sensitivity on real and computer generated networks with a well known modular structure.

community-detection
dynamical-systems
coupled-oscillators
feature-construction
rather-interesting
nonlinear-dynamics
to-write-about
nudge-targets
consider:variant-overlays
2 days ago

[1611.02617] Color-avoiding percolation

2 days ago

Many real world networks have groups of similar nodes which are vulnerable to the same failure or adversary. Nodes can be colored in such a way that colors encode the shared vulnerabilities. Using multiple paths to avoid these vulnerabilities can greatly improve network robustness. Color-avoiding percolation provides a theoretical framework for analyzing this scenario, focusing on the maximal set of nodes which can be connected via multiple color-avoiding paths. In this paper we extend the basic theory of color-avoiding percolation that was published in [Krause et. al., Phys. Rev. X 6 (2016) 041022]. We explicitly account for the fact that the same particular link can be part of different paths avoiding different colors. This fact was previously accounted for with a heuristic approximation. We compare this approximation with a new, more exact theory and show that the new theory is substantially more accurate for many avoided colors. Further, we formulate our new theory with differentiated node functions, as senders/receivers or as transmitters. In both functions, nodes can be explicitly trusted or avoided. With only one avoided color we obtain standard percolation. With one by one avoiding additional colors, we can understand the critical behavior of color avoiding percolation. For heterogeneous color frequencies, we find that the colors with the largest frequencies control the critical threshold and exponent. Colors of small frequencies have only a minor influence on color avoiding connectivity, thus allowing for approximations.

security
graph-theory
network-theory
robustness
algorithms
nudge-targets
consider:higher-order-features
2 days ago

The Omidyar Network and the (Neoliberal) Future of Education

8 days ago

So, while in the US we see neoliberalism pushing to dismantle public institutions and public funding for public institutions, in the Global South, these very forces are there touting the “power of markets” to make sure public institutions can never emerge or thrive in the first place. Investors like the Omidyar Network are poised to extract value from the very people they promise their technologies and businesses are there to help.

Conveniently, the Omidyar Network’s investment portfolio also includes journalistic and research organizations that are too poised to promote and endorse the narratives that aggrandize these very technocratic, market-based solutions.

neoliberalism
education
corporatism
disintermediation-in-action
not-a-good-idea
Conveniently, the Omidyar Network’s investment portfolio also includes journalistic and research organizations that are too poised to promote and endorse the narratives that aggrandize these very technocratic, market-based solutions.

8 days ago

Who Really Makes Money Off of Bail Bonds? - The Atlantic

8 days ago

A new report from the nonprofit Color of Change and the American Civil Liberties Union (ACLU) sheds further light on the country’s bail system. The report finds that around 70 percent of those currently in jail have yet to be convicted of a crime. Not unrelated: Between 1990 and 2009, the share of people arrested who were required to post money bail grew from 37 percent to 61 percent, according to the report.

corporatism
police
politics
racism
legalism
public-policy
the-crises
8 days ago

[1705.03394] That is not dead which can eternal lie: the aestivation hypothesis for resolving Fermi's paradox

8 days ago

If a civilization wants to maximize computation it appears rational to aestivate until the far future in order to exploit the low temperature environment: this can produce a 1030 multiplier of achievable computation. We hence suggest the "aestivation hypothesis": the reason we are not observing manifestations of alien civilizations is that they are currently (mostly) inactive, patiently waiting for future cosmic eras. This paper analyzes the assumptions going into the hypothesis and how physical law and observational evidence constrain the motivations of aliens compatible with the hypothesis.

aliens
Fermi-paradox
rather-interesting
to-write-about
via:absfac
8 days ago

Trumpism: It’s Coming From the Suburbs | The Nation

11 days ago

If you’re looking for Trump’s implacable support, Texas trailer parks and Kentucky cabins are the wrong places to find it. Fascism develops over hands of poker in furnished basements, over the grill by the backyard pool, over beers on the commuter-rail ride back from the ball game—and in police stations and squad cars.

fascism
cultural-norms
11 days ago

[1609.07061] Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations

12 days ago

We introduce a method to train Quantized Neural Networks (QNNs) --- neural networks with extremely low precision (e.g., 1-bit) weights and activations, at run-time. At train-time the quantized weights and activations are used for computing the parameter gradients. During the forward pass, QNNs drastically reduce memory size and accesses, and replace most arithmetic operations with bit-wise operations. As a result, power consumption is expected to be drastically reduced. We trained QNNs over the MNIST, CIFAR-10, SVHN and ImageNet datasets. The resulting QNNs achieve prediction accuracy comparable to their 32-bit counterparts. For example, our quantized version of AlexNet with 1-bit weights and 2-bit activations achieves 51% top-1 accuracy. Moreover, we quantize the parameter gradients to 6-bits as well which enables gradients computation using only bit-wise operation. Quantized recurrent neural networks were tested over the Penn Treebank dataset, and achieved comparable accuracy as their 32-bit counterparts using only 4-bits. Last but not least, we programmed a binary matrix multiplication GPU kernel with which it is possible to run our MNIST QNN 7 times faster than with an unoptimized GPU kernel, without suffering any loss in classification accuracy. The QNN code is available online.

representation
neural-networks
deep-learning
rather-interesting
to-write-about
consider:simple-examples
12 days ago

[1705.00241] Dynamic interdependence and competition in multilayer networks

12 days ago

From critical infrastructure, to physiology and the human brain, complex systems rarely occur in isolation. Instead, the functioning of nodes in one system often promotes or suppresses the functioning of nodes in another. Despite advances in structural interdependence, modeling interdependence and other interactions between dynamic systems has proven elusive. Here we define a broadly applicable dynamic dependency link and develop a general framework for interdependent and competitive interactions between general dynamic systems. We apply our framework to studying interdependent and competitive synchronization in multi-layer oscillator networks and cooperative/competitive contagions in an epidemic model. Using a mean-field theory which we verify numerically, we find explosive transitions and rich behavior which is absent in percolation models including hysteresis, multi-stability and chaos. The framework presented here provides a powerful new way to model and understand many of the interacting complex systems which surround us.

dynamical-systems
coupled-oscillators
network-theory
rather-interesting
to-write-about
simulation
consider:simple-examples
nudge-targets
consider:control-theory
consider:feature-discovery
12 days ago

[1702.08359] Dynamic Word Embeddings via Skip-Gram Filtering

12 days ago

We present a probabilistic language model for time-stamped text data which tracks the semantic evolution of individual words over time. The model represents words and contexts by latent trajectories in an embedding space. At each moment in time, the embedding vectors are inferred from a probabilistic version of word2vec [Mikolov, 2013]. These embedding vectors are connected in time through a latent diffusion process. We describe two scalable variational inference algorithms---skip-gram smoothing and skip-gram filtering---that allow us to train the model jointly over all times; thus learning on all data while simultaneously allowing word and context vectors to drift. Experimental results on three different corpora demonstrate that our dynamic model infers word embedding trajectories that are more interpretable and lead to higher predictive likelihoods than competing methods that are based on static models trained separately on time slices.

natural-language-processing
machine-learning
representation
to-understand
skip-grams
consider:looking-to-see
to-write-about
12 days ago

[1703.01141] Dynamic State Warping

12 days ago

The ubiquity of sequences in many domains enhances significant recent interest in sequence learning, for which a basic problem is how to measure the distance between sequences. Dynamic time warping (DTW) aligns two sequences by nonlinear local warping and returns a distance value. DTW shows superior ability in many applications, e.g. video, image, etc. However, in DTW, two points are paired essentially based on point-to-point Euclidean distance (ED) without considering the autocorrelation of sequences. Thus, points with different semantic meanings, e.g. peaks and valleys, may be matched providing their coordinate values are similar. As a result, DTW is sensitive to noise and poorly interpretable. This paper proposes an efficient and flexible sequence alignment algorithm, dynamic state warping (DSW). DSW converts each time point into a latent state, which endows point-wise autocorrelation information. Alignment is performed by using the state sequences. Thus DSW is able to yield alignment that is semantically more interpretable than that of DTW. Using one nearest neighbor classifier, DSW shows significant improvement on classification accuracy in comparison to ED (70/85 wins) and DTW (74/85 wins). We also empirically demonstrate that DSW is more robust and scales better to long sequences than ED and DTW.

time-series
time-warping
representation
to-understand
algorithms
machine-learning
feature-construction
12 days ago

[1704.00899] Dynamic Rank Maximal Matchings

12 days ago

We consider the problem of matching applicants to posts where applicants have preferences over posts. Thus the input to our problem is a bipartite graph G = (A U P,E), where A denotes a set of applicants, P is a set of posts, and there are ranks on edges which denote the preferences of applicants over posts. A matching M in G is called rank-maximal if it matches the maximum number of applicants to their rank 1 posts, subject to this the maximum number of applicants to their rank 2 posts, and so on.

We consider this problem in a dynamic setting, where vertices and edges can be added and deleted at any point. Let n and m be the number of vertices and edges in an instance G, and r be the maximum rank used by any rank-maximal matching in G. We give a simple O(r(m+n))-time algorithm to update an existing rank-maximal matching under each of these changes. When r = o(n), this is faster than recomputing a rank-maximal matching completely using a known algorithm like that of Irving et al., which takes time O(min((r + n, r*sqrt(n))m).

operations-research
optimization
rostering
scheduling
dynamic-optimization
to-write-about
consider:representation
consider:multiobjective-optimization
We consider this problem in a dynamic setting, where vertices and edges can be added and deleted at any point. Let n and m be the number of vertices and edges in an instance G, and r be the maximum rank used by any rank-maximal matching in G. We give a simple O(r(m+n))-time algorithm to update an existing rank-maximal matching under each of these changes. When r = o(n), this is faster than recomputing a rank-maximal matching completely using a known algorithm like that of Irving et al., which takes time O(min((r + n, r*sqrt(n))m).

12 days ago

[1704.00565] Dynamic Planar Embeddings of Dynamic Graphs

12 days ago

We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the face boundary (we call such a vertex pair linkable), and edges can be deleted. The planar embedding can also be changed locally by flipping components that are connected to the rest of the graph by at most two vertices.

Given vertices u,v, linkable(u,v) decides whether u and v are linkable in the current embedding, and if so, returns a list of suggestions for the placement of (u,v) in the embedding. For non-linkable vertices u,v, we define a new query, one-flip-linkable(u,v) providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log2n) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph.

Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.

graph-layout
dynamical-systems
constraint-satisfaction
multiobjective-optimization
dynamic-optimization
to-write-about
consider:simple-examples
rather-interesting
Given vertices u,v, linkable(u,v) decides whether u and v are linkable in the current embedding, and if so, returns a list of suggestions for the placement of (u,v) in the embedding. For non-linkable vertices u,v, we define a new query, one-flip-linkable(u,v) providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log2n) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph.

Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.

12 days ago

[1610.07631] Dynamic Phases of Active Matter Systems with Quenched Disorder

12 days ago

Depinning and nonequilibrium transitions within sliding states in systems driven over quenched disorder arise across a wide spectrum of size scales ranging from atomic friction at the nanoscale, flux motion in type-II superconductors at the mesoscale, colloidal motion in disordered media at the microscale, and plate tectonics at geological length scales. Here we show that active matter or self-propelled particles interacting with quenched disorder under an external drive represents a new class of system that can also exhibit pinning-depinning phenomena, plastic flow phases, and nonequilibrium sliding transitions that are correlated with distinct morphologies and velocity-force curve signatures. When interactions with the substrate are strong, a homogeneous pinned liquid phase forms that depins plastically into a uniform disordered phase and then dynamically transitions first into a moving stripe coexisting with a pinned liquid and then into a moving phase separated state at higher drives. We numerically map the resulting dynamical phase diagrams as a function of external drive, substrate interaction strength, and self-propulsion correlation length. These phases can be observed for active matter moving through random disorder. Our results indicate that intrinsically nonequilibrium systems can exhibit additional nonequilibrium transitions when subjected to an external drive.

active-matter
simulation
rather-interesting
to-write-about
physics!
emergent-design
phase-transitions
12 days ago

[1610.09787] Edward: A library for probabilistic modeling, inference, and criticism

12 days ago

Probabilistic modeling is a powerful approach for analyzing empirical information. We describe Edward, a library for probabilistic modeling. Edward's design reflects an iterative process pioneered by George Box: build a model of a phenomenon, make inferences about the model given data, and criticize the model's fit to the data. Edward supports a broad class of probabilistic models, efficient algorithms for inference, and many techniques for model criticism. The library builds on top of TensorFlow to support distributed training and hardware such as GPUs. Edward enables the development of complex probabilistic models and their algorithms at a massive scale.

machine-learning
framework
rather-interesting
representation
probabilistic-languages
12 days ago

[1703.08052] Dynamic Bernoulli Embeddings for Language Evolution

12 days ago

Word embeddings are a powerful approach for unsupervised analysis of language. Recently, Rudolph et al. (2016) developed exponential family embeddings, which cast word embeddings in a probabilistic framework. Here, we develop dynamic embeddings, building on exponential family embeddings to capture how the meanings of words change over time. We use dynamic embeddings to analyze three large collections of historical texts: the U.S. Senate speeches from 1858 to 2009, the history of computer science ACM abstracts from 1951 to 2014, and machine learning papers on the Arxiv from 2007 to 2015. We find dynamic embeddings provide better fits than classical embeddings and capture interesting patterns about how language changes.

natural-language-processing
representation
rather-interesting
to-write-about
nudge-targets
consider:representation
12 days ago

[1611.05321] Bootstrap, Review, Decode: Using Out-of-Domain Textual Data to Improve Image Captioning

12 days ago

We propose a novel way of using out-of-domain textual data to enhance the performance of existing image captioning systems. We evaluate this learning approach on a newly designed model that uses - and improves upon - building blocks from state-of-the-art methods. This model starts from detecting visual concepts present in an image which are then fed to a reviewer-decoder architecture with an attention mechanism. Unlike previous approaches that encode visual concepts using word embeddings, we instead suggest using regional image features which capture more intrinsic information. The main benefit of this architecture is that it synthesizes meaningful thought vectors that capture salient image properties and then applies a soft attentive decoder to decode the thought vectors and generate image captions. We evaluate our model on both Microsoft COCO and Flickr30K datasets and demonstrate that this model combined with our bootstrap learning method can largely improve performance and help the model to generate more accurate and diverse captions.

data-fusion
image-processing
deep-learning
rather-interesting
to-write-about
nudge-targets
consider:feature-discovery
12 days ago

[1506.03662] Variance Reduced Stochastic Gradient Descent with Neighbors

12 days ago

Stochastic Gradient Descent (SGD) is a workhorse in machine learning, yet its slow convergence can be a computational bottleneck. Variance reduction techniques such as SAG, SVRG and SAGA have been proposed to overcome this weakness, achieving linear convergence. However, these methods are either based on computations of full gradients at pivot points, or on keeping per data point corrections in memory. Therefore speed-ups relative to SGD may need a minimal number of epochs in order to materialize. This paper investigates algorithms that can exploit neighborhood structure in the training data to share and re-use information about past stochastic gradients across data points, which offers advantages in the transient optimization phase. As a side-product we provide a unified convergence analysis for a family of variance reduction algorithms, which we call memorization algorithms. We provide experimental results supporting our theory.

numerical-methods
optimization
computational-complexity
horse-races
heuristics
to-write-about
compare-to:lexicase
12 days ago

[1605.06561] DynaNewton - Accelerating Newton's Method for Machine Learning

12 days ago

Newton's method is a fundamental technique in optimization with quadratic convergence within a neighborhood around the optimum. However reaching this neighborhood is often slow and dominates the computational costs. We exploit two properties specific to empirical risk minimization problems to accelerate Newton's method, namely, subsampling training data and increasing strong convexity through regularization. We propose a novel continuation method, where we define a family of objectives over increasing sample sizes and with decreasing regularization strength. Solutions on this path are tracked such that the minimizer of the previous objective is guaranteed to be within the quadratic convergence region of the next objective to be optimized. Thereby every Newton iteration is guaranteed to achieve super-linear contractions with regard to the chosen objective, which becomes a moving target. We provide a theoretical analysis that motivates our algorithm, called DynaNewton, and characterizes its speed of convergence. Experiments on a wide range of data sets and problems consistently confirm the predicted computational savings.

numerical-methods
data-fusion
rather-interesting
machine-learning
computational-complexity
to-write-about
sometimes-it-depends
12 days ago

[1610.01983] Driving in the Matrix: Can Virtual Worlds Replace Human-Generated Annotations for Real World Tasks?

12 days ago

Deep learning has rapidly transformed the state of the art algorithms used to address a variety of problems in computer vision and robotics. These breakthroughs have relied upon massive amounts of human annotated training data. This time consuming process has begun impeding the progress of these deep learning efforts. This paper describes a method to incorporate photo-realistic computer images from a simulation engine to rapidly generate annotated data that can be used for the training of machine learning algorithms. We demonstrate that a state of the art architecture, which is trained only using these synthetic annotations, performs better than the identical architecture trained on human annotated real-world data, when tested on the KITTI data set for vehicle detection. By training machine learning algorithms on a rich virtual world, real objects in real scenes can be learned and classified using synthetic data. This approach offers the possibility of accelerating deep learning's application to sensor-based classification problems like those that appear in self-driving cars. The source code and data to train and validate the networks described in this paper are made available for researchers.

simulation
engineering-design
ontology
approximation
training
to-write-about
consider:stress-testing
12 days ago

[1608.08844] Snapping Graph Drawings to the Grid Optimally

12 days ago

In geographic information systems and in the production of digital maps for small devices with restricted computational resources one often wants to round coordinates to a rougher grid. This removes unnecessary detail and reduces space consumption as well as computation time. This process is called snapping to the grid and has been investigated thoroughly from a computational-geometry perspective. In this paper we investigate the same problem for given drawings of planar graphs under the restriction that their combinatorial embedding must be kept and edges are drawn straight-line. We show that the problem is NP-hard for several objectives and provide an integer linear programming formulation. Given a plane graph G and a positive integer w, our ILP can also be used to draw G straight-line on a grid of width w and minimum height (if possible).

graph-layout
computational-geometry
algorithms
rather-interesting
constraint-satisfaction
nudge-targets
consider:looking-to-see
approximation
performance-measure
12 days ago

[1409.0499] Drawing Graphs within Restricted Area

12 days ago

We study the problem of selecting a maximum-weight subgraph of a given graph such that the subgraph can be drawn within a prescribed drawing area subject to given non-uniform vertex sizes. We develop and analyze heuristics both for the general (undirected) case and for the use case of (directed) calculation graphs which are used to analyze the typical mistakes that high school students make when transforming mathematical expressions in the process of calculating, for example, sums of fractions.

graph-layout
constraint-satisfaction
multiobjective-optimization
computational-geometry
parametrization
to-write-about
aesthetics
12 days ago

[1305.0750] Multi-Sided Boundary Labeling

12 days ago

In the Boundary Labeling problem, we are given a set of n points, referred to as sites, inside an axis-parallel rectangle R, and a set of n pairwise disjoint rectangular labels that are attached to R from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called leaders, with at most one bend.

In this paper, we study the Multi-Sided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of R (here a crossing-free solution always exists). The case where labels may lie on adjacent sides is more difficult. We present efficient algorithms for testing the existence of a crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free layout.

computational-geometry
graph-layout
maps
constraint-satisfaction
multiobjective-optimization
performance-measure
rather-interesting
engineering-philosophy
to-write-about
good-examples-for-MO
In this paper, we study the Multi-Sided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of R (here a crossing-free solution always exists). The case where labels may lie on adjacent sides is more difficult. We present efficient algorithms for testing the existence of a crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free layout.

12 days ago

[1209.0830] Progress on Partial Edge Drawings

12 days ago

Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been investigated. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on a symmetric model (SPED) that requires the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction δ of the edge lengths (δ-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub.

We show that, for a fixed stub--edge length ratio δ, not all graphs have a δ-SHPED. Specifically, we show that K241 does not have a 1/4-SHPED, while bandwidth-k graphs always have a Θ(1/k√)-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem \textsc{MaxSPED} where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem.

graph-layout
computational-geometry
algorithms
constraint-satisfaction
rather-interesting
representation
to-write-about
We show that, for a fixed stub--edge length ratio δ, not all graphs have a δ-SHPED. Specifically, we show that K241 does not have a 1/4-SHPED, while bandwidth-k graphs always have a Θ(1/k√)-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem \textsc{MaxSPED} where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem.

12 days ago

[0806.0253] On collinear sets in straight line drawings

12 days ago

We consider straight line drawings of a planar graph G with possible edge crossings. The \emph{untangling problem} is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let fix(G) denote the maximum number of vertices that can be left fixed in the worst case. In the \emph{allocation problem}, we are given a planar graph G on n vertices together with an n-point set X in the plane and have to draw G without edge crossings so that as many vertices as possible are located in X. Let fit(G) denote the maximum number of points fitting this purpose in the worst case. As fix(G)≤fit(G), we are interested in upper bounds for the latter and lower bounds for the former parameter.

For each ϵ>0, we construct an infinite sequence of graphs with fit(G)=O(nσ+ϵ), where σ<0.99 is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. To the best of our knowledge, this is the first example of graphs with fit(G)=o(n). On the other hand, we prove that fix(G)≥n/30‾‾‾‾√ for all G with tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [Discrete and Computational Geometry 42:542-569 (2009)] for outerplanar graphs.

Our upper bound for fit(G) is based on the fact that the constructed graphs can have only few collinear vertices in any crossing-free drawing. To prove the lower bound for fix(G), we show that graphs of tree-width 2 admit drawings that have large sets of collinear vertices with some additional special properties.

graph-theory
computational-geometry
graph-layout
algorithms
rather-interesting
nudge-targets
consider:mathematical-recreations
consider:classification
For each ϵ>0, we construct an infinite sequence of graphs with fit(G)=O(nσ+ϵ), where σ<0.99 is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. To the best of our knowledge, this is the first example of graphs with fit(G)=o(n). On the other hand, we prove that fix(G)≥n/30‾‾‾‾√ for all G with tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [Discrete and Computational Geometry 42:542-569 (2009)] for outerplanar graphs.

Our upper bound for fit(G) is based on the fact that the constructed graphs can have only few collinear vertices in any crossing-free drawing. To prove the lower bound for fix(G), we show that graphs of tree-width 2 admit drawings that have large sets of collinear vertices with some additional special properties.

12 days ago

[1607.01196] Drawing Graphs on Few Lines and Few Planes

12 days ago

We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows.

We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values.

We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing).

We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.

graph-layout
computational-geometry
optimization
graph-theory
topology
rather-interesting
to-write-about
consider:feature-discovery
nudge-targets
consider:classification
We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values.

We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing).

We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.

12 days ago

[1607.06136] Eliminating Depth Cycles among Triangles in Three Dimensions

13 days ago

Given n non-vertical pairwise disjoint triangles in 3-space, their vertical depth (above/below) relation may contain cycles. We show that, for any ε>0, the triangles can be cut into O(n3/2+ε) pieces, where each piece is a connected semi-algebraic set whose description complexity depends only on the choice of ε, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. We are not aware of any previous study of this problem with a subquadratic bound on the number of pieces.

This work extends the recent study by two of the authors on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth, which leads to a recursive procedure for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear.

Our result essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

computational-geometry
algorithms
hidden-line-removal
rather-interesting
computational-complexity
constraint-satisfaction
nudge-targets
consider:rediscovery
This work extends the recent study by two of the authors on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth, which leads to a recursive procedure for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear.

Our result essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.

13 days ago

[1612.08473] Doodles on surfaces I: An introduction to their basic properties

13 days ago

Doodles were introduced in [R. Fenn and P. Taylor, Introducing doodles, Topology of low-dimensional manifolds, pp. 37--43, Lecture Notes in Math., 722, Springer, Berlin, 1979] but were restricted to embedded circles in the 2-sphere. Khovanov, [M. Khovanov, Doodle groups, Trans. Amer. Math. Soc. 349 (1997), 2297--2315], extended the idea to immersed circles in the 2-sphere. In this paper we further extend the range of doodles to any closed orientable surfaces.

topology
geometry
to-understand
13 days ago

[1605.08107] Dominance Products and Faster Algorithms for High-Dimensional Closest Pair under $L_infty$

13 days ago

We give improved algorithmic time bounds for two fundamental problems, and establish a new complexity connection between them. The first is computing dominance product: given a set of n points p1,…,pn in ℝd, compute a matrix D, such that D[i,j]=∣∣{k∣pi[k]≤pj[k]}∣∣; this is the number of coordinates at which pj dominates pi. Dominance product computation has often been applied in algorithm design over the last decade.

The second problem is the L∞ Closest Pair in high dimensions: given a set S of n points in ℝd, find a pair of distinct points in S at minimum distance under the L∞ metric. When d is constant, there are efficient algorithms that solve this problem, and fast approximate solutions are known for general d. However, obtaining an exact solution in very high dimensions seems to be much less understood. We significantly simplify and improve previous results, showing that the problem can be solved by a deterministic strongly-polynomial algorithm that runs in O(DP(n,d)logn) time, where DP(n,d) is the time bound for computing the dominance product for n points in ℝd. For integer coordinates from some interval [−M,M], and for d=nr for some r>0, we obtain an algorithm that runs in Õ (min{Mnω(1,r,1),DP(n,d)}) time, where ω(1,r,1) is the exponent of multiplying an n×nr matrix by an nr×n matrix.

multiobjective-optimization
matrices
algorithms
rather-interesting
to-understand
consider:lexicase
The second problem is the L∞ Closest Pair in high dimensions: given a set S of n points in ℝd, find a pair of distinct points in S at minimum distance under the L∞ metric. When d is constant, there are efficient algorithms that solve this problem, and fast approximate solutions are known for general d. However, obtaining an exact solution in very high dimensions seems to be much less understood. We significantly simplify and improve previous results, showing that the problem can be solved by a deterministic strongly-polynomial algorithm that runs in O(DP(n,d)logn) time, where DP(n,d) is the time bound for computing the dominance product for n points in ℝd. For integer coordinates from some interval [−M,M], and for d=nr for some r>0, we obtain an algorithm that runs in Õ (min{Mnω(1,r,1),DP(n,d)}) time, where ω(1,r,1) is the exponent of multiplying an n×nr matrix by an nr×n matrix.

13 days ago

[1505.07818] Domain-Adversarial Training of Neural Networks

13 days ago

We introduce a new representation learning approach for domain adaptation, in which data at training and test time come from similar but different distributions. Our approach is directly inspired by the theory on domain adaptation suggesting that, for effective domain transfer to be achieved, predictions must be made based on features that cannot discriminate between the training (source) and test (target) domains. The approach implements this idea in the context of neural network architectures that are trained on labeled data from the source domain and unlabeled data from the target domain (no labeled target-domain data is necessary). As the training progresses, the approach promotes the emergence of features that are (i) discriminative for the main learning task on the source domain and (ii) indiscriminate with respect to the shift between the domains. We show that this adaptation behaviour can be achieved in almost any feed-forward model by augmenting it with few standard layers and a new gradient reversal layer. The resulting augmented architecture can be trained using standard backpropagation and stochastic gradient descent, and can thus be implemented with little effort using any of the deep learning packages. We demonstrate the success of our approach for two distinct classification problems (document sentiment analysis and image classification), where state-of-the-art domain adaptation performance on standard benchmarks is achieved. We also validate the approach for descriptor learning task in the context of person re-identification application.

machine-learning
performance-measure
rather-interesting
to-write-about
nudge-targets
consider:looking-to-see
consider:error-measures
13 days ago

[1606.03686] Does Having More Options Mean Harder to Reach Consensus?

13 days ago

We generalize a binary majority-vote model on adaptive networks to a plurality-vote counterpart. When opinions are uniformly distributed in the population of voters in the initial state, it is found that having more available opinions in the initial state actually accelerate the time to consensus. In particular, we investigate the three-state plurality-vote model. While time to consensus in two state model scales exponentially with population size N, for finite-size system, there is a non-zero probability that either the population reaches the consensus state in a time that is very short and independent of N (in the heterophily regime), or in a time that scales exponentially with N but is still much faster than two-state model.

voting-models
agent-based
evolutionary-economics
diversity
rather-interesting
to-write-about
looking-to-see
13 days ago

[1603.05691] Do Deep Convolutional Nets Really Need to be Deep and Convolutional?

13 days ago

Yes, they do. This paper provides the first empirical demonstration that deep convolutional models really need to be both deep and convolutional, even when trained with methods such as distillation that allow small or shallow models of high accuracy to be trained. Although previous research showed that shallow feed-forward nets sometimes can learn the complex functions previously learned by deep nets while using the same number of parameters as the deep models they mimic, in this paper we demonstrate that the same methods cannot be used to train accurate models on CIFAR-10 unless the student models contain multiple layers of convolution. Although the student models do not have to be as deep as the teacher model they mimic, the students need multiple convolutional layers to learn functions of comparable accuracy as the deep convolutional teacher.

good-question
neural-networks
deep-learning
rather-interesting
approximation
heuristics
nudge-targets
consider:re-approximation
13 days ago

[1604.07309] Division by zero

13 days ago

For any sufficiently strong theory of arithmetic, the set of Diophantine equations provably unsolvable in the theory is algorithmically undecidable, as a consequence of the MRDP theorem. In contrast, we show decidability of Diophantine equations provably unsolvable in Robinson's arithmetic Q. The argument hinges on an analysis of a particular class of equations, hitherto unexplored in Diophantine literature. We also axiomatize the universal fragment of Q in the process.

mathematics
to-understand
/shrug
13 days ago

[1703.10970] Diversity of preferences can increase collective welfare in sequential exploration problems

13 days ago

In search engines, online marketplaces and other human-computer interfaces large collectives of individuals sequentially interact with numerous alternatives of varying quality. In these contexts, trial and error (exploration) is crucial for uncovering novel high-quality items or solutions, but entails a high cost for individual users. Self-interested decision makers, are often better off imitating the choices of individuals who have already incurred the costs of exploration. Although imitation makes sense at the individual level, it deprives the group of additional information that could have been gleaned by individual explorers. In this paper we show that in such problems, preference diversity can function as a welfare enhancing mechanism. It leads to a consistent increase in the quality of the consumed alternatives that outweighs the increased cost of search for the users.

wisdom-of-crowds
diversity
exploration-and-exploitation
collective-intelligence
game-theory
to-write-about
13 days ago

[1011.4245] When the optimal is not the best: parameter estimation in complex biological models

13 days ago

Background: The vast computational resources that became available during the past decade enabled the development and simulation of increasingly complex mathematical models of cancer growth. These models typically involve many free parameters whose determination is a substantial obstacle to model development. Direct measurement of biochemical parameters in vivo is often difficult and sometimes impracticable, while fitting them under data-poor conditions may result in biologically implausible values.

Results: We discuss different methodological approaches to estimate parameters in complex biological models. We make use of the high computational power of the Blue Gene technology to perform an extensive study of the parameter space in a model of avascular tumor growth. We explicitly show that the landscape of the cost function used to optimize the model to the data has a very rugged surface in parameter space. This cost function has many local minima with unrealistic solutions, including the global minimum corresponding to the best fit.

Conclusions: The case studied in this paper shows one example in which model parameters that optimally fit the data are not necessarily the best ones from a biological point of view. To avoid force-fitting a model to a dataset, we propose that the best model parameters should be found by choosing, among suboptimal parameters, those that match criteria other than the ones used to fit the model. We also conclude that the model, data and optimization approach form a new complex system, and point to the need of a theory that addresses this problem more generally.

optimization
biophysics
noise
stochastic-resonance
modeling
rather-interesting
to-write-about
approximation
performance-measure
Results: We discuss different methodological approaches to estimate parameters in complex biological models. We make use of the high computational power of the Blue Gene technology to perform an extensive study of the parameter space in a model of avascular tumor growth. We explicitly show that the landscape of the cost function used to optimize the model to the data has a very rugged surface in parameter space. This cost function has many local minima with unrealistic solutions, including the global minimum corresponding to the best fit.

Conclusions: The case studied in this paper shows one example in which model parameters that optimally fit the data are not necessarily the best ones from a biological point of view. To avoid force-fitting a model to a dataset, we propose that the best model parameters should be found by choosing, among suboptimal parameters, those that match criteria other than the ones used to fit the model. We also conclude that the model, data and optimization approach form a new complex system, and point to the need of a theory that addresses this problem more generally.

13 days ago

[1612.09268] The ontogeny of discourse structure mimics the development of literature

13 days ago

Discourse varies with age, education, psychiatric state and historical epoch, but the ontogenetic and cultural dynamics of discourse structure remain to be quantitatively characterized. To this end we investigated word graphs obtained from verbal reports of 200 subjects ages 2-58, and 676 literary texts spanning ~5,000 years. In healthy subjects, lexical diversity, graph size, and long-range recurrence departed from initial near-random levels through a monotonic asymptotic increase across ages, while short-range recurrence showed a corresponding decrease. These changes were explained by education and suggest a hierarchical development of discourse structure: short-range recurrence and lexical diversity stabilize after elementary school, but graph size and long-range recurrence only stabilize after high school. This gradual maturation was blurred in psychotic subjects, who maintained in adulthood a near-random structure. In literature, monotonic asymptotic changes over time were remarkable: While lexical diversity, long-range recurrence and graph size increased away from near-randomness, short-range recurrence declined, from above to below random levels. Bronze Age texts are structurally similar to childish or psychotic discourses, but subsequent texts converge abruptly to the healthy adult pattern around the onset of the Axial Age (800-200 BC), a period of pivotal cultural change. Thus, individually as well as historically, discourse maturation increases the range of word recurrence away from randomness.

oh-my
psychology
linguistics
cognition
Big-Theories
ontology-recapitulates-Haeckel-again
to-write-about
13 days ago

[1110.0373] An excitable electronic circuit as a sensory neuron model

13 days ago

An electronic circuit device, inspired on the FitzHugh-Nagumo model of neuronal excitability, was constructed and shown to operate with characteristics compatible with those of biological sensory neurons. The nonlinear dynamical model of the electronics quantitatively reproduces the experimental observations on the circuit, including the Hopf bifurcation at the onset of tonic spiking. Moreover, we have implemented an analog noise generator as a source to study the variability of the spike trains. When the circuit is in the excitable regime, coherence resonance is observed. At sufficiently low noise intensity the spike trains have Poisson statistics, as in many biological neurons. The transfer function of the stochastic spike trains has a dynamic range of 6 dB, close to experimental values for real olfactory receptor neurons.

neural-networks
neurology
biophysics
electronics
rather-interesting
simulation
emulation
to-write-about
dynamical-systems
13 days ago

The Problem with Philanthropy | Public Books

13 days ago

The “myth” Kohl-Arenas identifies is the belief that individuals and communities can change their material circumstances in the absence of any change to the systems and policies that govern those circumstances. In the US, our national narrative places the lion’s share of responsibility on individuals: responsibility for poverty on the poor, for mental illness on the mentally ill and their families, for incarceration on the incarcerated. As a wealthy, developed nation, we are a bewildering outlier in our refusal to take more communal responsibility for our brethren. When people do organize to care for one another, and in doing so discover that life struggles are linked to structural problems in need of policy solutions, they are often demoralized to find that funders shy away from any work that would promote policy change.

philanthropy
public-policy
cultural-engineering
cultural-assumptions
corporatism
revolution
13 days ago

[1608.04481] Lecture Notes on Randomized Linear Algebra

13 days ago

These are lecture notes that are based on the lectures from a class I taught on the topic of Randomized Linear Algebra (RLA) at UC Berkeley during the Fall 2013 semester.

matrices
linear-algebra
stochastic-systems
algorithms
optimization
to-understand
to-read
consider:lexicase
13 days ago

[1104.5557] Randomized algorithms for matrices and data

13 days ago

Randomized algorithms for very large matrix problems have received a great deal of attention in recent years. Much of this work was motivated by problems in large-scale data analysis, and this work was performed by individuals from many different research communities. This monograph will provide a detailed overview of recent work on the theory of randomized matrix algorithms as well as the application of those ideas to the solution of practical problems in large-scale data analysis. An emphasis will be placed on a few simple core ideas that underlie not only recent theoretical advances but also the usefulness of these tools in large-scale data applications. Crucial in this context is the connection with the concept of statistical leverage. This concept has long been used in statistical regression diagnostics to identify outliers; and it has recently proved crucial in the development of improved worst-case matrix algorithms that are also amenable to high-quality numerical implementation and that are useful to domain scientists. Randomized methods solve problems such as the linear least-squares problem and the low-rank matrix approximation problem by constructing and operating on a randomized sketch of the input matrix. Depending on the specifics of the situation, when compared with the best previously-existing deterministic algorithms, the resulting randomized algorithms have worst-case running time that is asymptotically faster; their numerical implementations are faster in terms of clock-time; or they can be implemented in parallel computing environments where existing numerical algorithms fail to run at all. Numerous examples illustrating these observations will be described in detail.

via:arthegall
data-analysis
matrices
feature-extraction
learning-from-data
data-mining
rather-interesting
to-read
to-understand
13 days ago

[1409.4178] The frustrated brain: From dynamics on motifs to communities and networks

13 days ago

Cognitive function depends on an adaptive balance between flexible dynamics and integrative processes in distributed cortical networks. Patterns of zero-lag synchrony likely underpin numerous perceptual and cognitive functions. Synchronization fulfils integration by reducing entropy, whilst adaptive function mandates that a broad variety of stable states be readily accessible. Here, we elucidate two complementary influences on patterns of zero-lag synchrony that derive from basic properties of brain networks. First, mutually coupled pairs of neuronal subsystems -- resonance pairs -- promote stable zero-lag synchrony amongst the small motifs in which they are embedded, and whose effects can propagate along connected chains. Second, frustrated closed-loop motifs disrupt synchronous dynamics, enabling metastable configurations of zero-lag synchrony to coexist. We document these two complementary influences in small motifs and illustrate how these effects underpin stable versus metastable phase-synchronization patterns in prototypical modular networks and in large-scale cortical networks of the macaque (CoCoMac). We find that the variability of synchronization patterns depends on the inter-node time delay, increases with the network size, and is maximized for intermediate coupling strengths. We hypothesize that the dialectic influences of resonance versus frustration may form a dynamic substrate for flexible neuronal integration, an essential platform across diverse cognitive processes.

dynamical-systems
network-theory
coupled-oscillators
emergent-design
looking-to-see
systems-biology
nudge-targets
consider:robustness
consider:looking-to-see
13 days ago

[1304.5008] Mechanisms of Zero-Lag Synchronization in Cortical Motifs

13 days ago

Zero-lag synchronization between distant cortical areas has been observed in a diversity of experimental data sets and between many different regions of the brain. Several computational mechanisms have been proposed to account for such isochronous synchronization in the presence of long conduction delays: Of these, the phenomenon of "dynamical relaying" - a mechanism that relies on a specific network motif - has proven to be the most robust with respect to parameter mismatch and system noise. Surprisingly, despite a contrary belief in the community, the common driving motif is an unreliable means of establishing zero-lag synchrony. Although dynamical relaying has been validated in empirical and computational studies, the deeper dynamical mechanisms and comparison to dynamics on other motifs is lacking. By systematically comparing synchronization on a variety of small motifs, we establish that the presence of a single reciprocally connected pair - a "resonance pair" - plays a crucial role in disambiguating those motifs that foster zero-lag synchrony in the presence of conduction delays (such as dynamical relaying) from those that do not (such as the common driving triad). Remarkably, minor structural changes to the common driving motif that incorporate a reciprocal pair recover robust zero-lag synchrony. The findings are observed in computational models of spiking neurons, populations of spiking neurons and neural mass models, and arise whether the oscillatory systems are periodic, chaotic, noise-free or driven by stochastic inputs. The influence of the resonance pair is also robust to parameter mismatch and asymmetrical time delays amongst the elements of the motif. We call this manner of facilitating zero-lag synchrony resonance-induced synchronization, outline the conditions for its occurrence, and propose that it may be a general mechanism to promote zero-lag synchrony in the brain.

systems-biology
dynamical-systems
coupled-oscillators
engineering-design
emergent-design
looking-to-see
nudge-targets
consider:looking-to-see
consider:robustness
consider:reQ-like-systems
13 days ago

[1507.05249] Diversity improves performance in excitable networks

13 days ago

As few real systems comprise indistinguishable units, diversity is a hallmark of nature. Diversity among interacting units shapes properties of collective behavior such as synchronization and information transmission. However, the benefits of diversity on information processing at the edge of a phase transition, ordinarily assumed to emerge from identical elements, remain largely unexplored. Analyzing a general model of excitable systems with heterogeneous excitability, we find that diversity can greatly enhance optimal performance (by two orders of magnitude) when distinguishing incoming inputs. Heterogeneous systems possess a subset of specialized elements whose capability greatly exceeds that of the nonspecialized elements. Nonetheless, the behavior of the whole network can outperform all subgroups. We also find that diversity can yield multiple percolation, with performance optimized at tricriticality. Our results are robust in specific and more realistic neuronal systems comprising a combination of excitatory and inhibitory units, and indicate that diversity-induced amplification can be harnessed by neuronal systems for evaluating stimulus intensities.

network-theory
collective-behavior
physics!
coupled-oscillators
simulation
it's-more-complicated-than-you-think
to-write-about
nudge-targets
consider:engineering-design
13 days ago

[1611.01285] Naive Diversification Preferences and their Representation

13 days ago

A widely applied diversification paradigm is the naive diversification choice heuristic. It stipulates that an economic agent allocates equal decision weights to given choice alternatives independent of their individual characteristics. This article provides mathematically and economically sound choice theoretic foundations for the naive approach to diversification. We axiomatize naive diversification by defining it as a preference for equality over inequality and derive its relationship to the classical diversification paradigm. In particular, we show that (i) the notion of permutation invariance lies at the core of naive diversification and that an economic agent is a naive diversifier if and only if his preferences are convex and permutation invariant; (ii) Schur-concave utility functions capture the idea of being inequality averse on top of being risk averse; and (iii) the transformations, which rebalance unequal decision weights to equality, are characterized in terms of their implied turnover.

portfolio-theory
risk-management
multiobjective-optimization
financial-engineering
to-write-about
nudge-targets
consider:rediscovery
13 days ago

[1501.01573] The Temporal Dimension of Risk

13 days ago

Multi-period measures of risk account for the path that the value of an investment portfolio takes. In the context of probabilistic risk measures, the focus has traditionally been on the magnitude of investment loss and not on the dimension associated with the passage of time. In this paper, the concept of temporal path-dependent risk measure is mathematically formalized to capture the risk associated with the temporal dimension of a stochastic process. We discuss the properties of temporal measures of risk and show that they can never be coherent. We then study the temporal dimension of investment drawdown, its duration, which measures the length of excursions below a running maximum. Its properties in the context of risk measures are analyzed both theoretically and empirically. In particular, we show that duration captures serial correlation in the returns of two major asset classes. We conclude by discussing the challenges of path-dependent temporal risk estimation in practice.

portfolio-theory
risk
risk-management
define-your-terms
financial-engineering
to-write-about
time-series
data-analysis
planning
13 days ago

[1404.7493] Drawdown: From Practice to Theory and Back Again

13 days ago

Maximum drawdown, the largest cumulative loss from peak to trough, is one of the most widely used indicators of risk in the fund management industry, but one of the least developed in the context of measures of risk. We formalize drawdown risk as Conditional Expected Drawdown (CED), which is the tail mean of maximum drawdown distributions. We show that CED is a degree one positive homogenous risk measure, so that it can be linearly attributed to factors; and convex, so that it can be used in quantitative optimization. We empirically explore the differences in risk attributions based on CED, Expected Shortfall (ES) and volatility. An important feature of CED is its sensitivity to serial correlation. In an empirical study that fits AR(1) models to US Equity and US Bonds, we find substantially higher correlation between the autoregressive parameter and CED than with ES or with volatility.

portfolio-theory
performance-measure
financial-engineering
multiobjective-optimization
consider:feature-discovery
to-write-about
algorithms
representation
13 days ago

[1507.02025] Diversification Preferences in the Theory of Choice

13 days ago

Diversification represents the idea of choosing variety over uniformity. Within the theory of choice, desirability of diversification is axiomatized as preference for a convex combination of choices that are equivalently ranked. This corresponds to the notion of risk aversion when one assumes the von-Neumann-Morgenstern expected utility model, but the equivalence fails to hold in other models. This paper studies axiomatizations of the concept of diversification and their relationship to the related notions of risk aversion and convex preferences within different choice theoretic models. Implications of these notions on portfolio choice are discussed. We cover model-independent diversification preferences, preferences within models of choice under risk, including expected utility theory and the more general rank-dependent expected utility theory, as well as models of choice under uncertainty axiomatized via Choquet expected utility theory. Remarks on interpretations of diversification preferences within models of behavioral choice are given in the conclusion.

game-theory
how-much-is-that-in-utiles?
economics
preferences
portfolio-theory
decision-making
to-write-about
nudge-targets
consider:looking-to-see
consider:performance-measures
consider:multiobjective-versions
13 days ago

[1609.08312] Duality between Feature Selection and Data Clustering

13 days ago

The feature-selection problem is formulated from an information-theoretic perspective. We show that the problem can be efficiently solved by an extension of the recently proposed info-clustering paradigm. This reveals the fundamental duality between feature selection and data clustering,which is a consequence of the more general duality between the principal partition and the principal lattice of partitions in combinatorial optimization.

information-theory
modeling
define-your-terms
feature-extraction
to-understand
connections-made
statistics
13 days ago

[1705.02249] Dynamics of Voter Models on Simple and Complex Network

13 days ago

This is a brief tutorial review of the dynamics of the voter model and the invasion process on complex networks.

voting
network-theory
SFI
tutorial
to-write-about
evolutionary-economics
agent-based
13 days ago

[1705.02072] Dynamics of slow and fast systems on complex networks

13 days ago

We study the occurrence of frequency synchronised states with tunable emergent frequencies in a network of connected systems. This is achieved by the interplay between time scales of nonlinear dynamical systems connected to form a network, where out of N systems, m evolve on a slower time scale. In such systems, in addition to frequency synchronised states, we also observe amplitude death, synchronised clusters and multifrequency states. We report an interesting cross over behaviour from fast to slow collective dynamics as the number of slow systems m increases. The transition to amplitude death is analysed in detail for minimal network configurations of 3 and 4 systems which actually form possible motifs of the full network.

nonlinear-dynamics
coupled-oscillators
systems
pattern-discovery
rather-interesting
to-write-about
to-do
consider:looking-to-see
13 days ago

Dragged from the plane in academia…time for a culture hack – Academic Irregularities

14 days ago

In another blog, Jana Bacevic wonders why, when there are so many critiques of the neoliberal, managerial university, is there so little resistance? I think there may not be so much mystery in this. All academics have been made to feel precarious and unworthy and it has led to a focus on meeting the metrics and staying ahead of the escalating demands of the university’s performance expectations. Raising a voice or organising with colleagues to change these absurd conditions seems too much like a risk when there is a mortgage to pay and children to feed. Managers know this, which is why they build structures to feed on academic insecurities – ‘imposter syndrome’- and incorporate employees into an anxiety machine (Hall and Bowles, 2016). So it is as much as academics dare, to reflect and write about their experiences in a rather dispassionate analytic way. Even this leads to a Catch 22 situation whereby academics find themselves required to publish, but publish to satisfy an urge to rebel by tilting at the REF windmill with their (published and peer-reviewed) critique.

academic-culture
precariat
corporatism
cultural-norms
14 days ago

Universities, neoliberalisation, and the (im)possibility of critique – Jana Bacevic

14 days ago

(c) This doesn’t get emphasised enough, but one of the reasons why people vie for positions in the academia is because at least it offers a degree of intellectual satisfaction, in opposition to what Graeber has termed the ever-growing number of ‘bullshit jobs’. So, one of the ways of making working conditions in the academia more decent is by making working conditions outside of academia more decent – and, perhaps, by decentralising a bit the monopoly on knowledge work that the academia holds. Not, however, in the neoliberal outsourcing/’creative hubs’ model, which unfortunately mostly serves to generate value for existing centres while further depleting the peripheries.

academia
academic-culture
monopsony
life-o'-the-mind
worklife
14 days ago

The United States of Work | New Republic

14 days ago

Anderson’s most provocative argument is that large companies, the institutions that employ most workers, amount to a de facto form of government, exerting massive and intrusive power in our daily lives. Unlike the state, these private governments are able to wield power with little oversight, because the executives and boards of directors that rule them are accountable to no one but themselves. Although they exercise their power to varying degrees and through both direct and “soft” means, employers can dictate how we dress and style our hair, when we eat, when (and if) we may use the toilet, with whom we may partner and under what arrangements. Employers may subject our bodies to drug tests; monitor our speech both on and off the job; require us to answer questionnaires about our exercise habits, off-hours alcohol consumption, and childbearing intentions; and rifle through our belongings. If the state held such sweeping powers, Anderson argues, we would probably not consider ourselves free men and women.

corporatism
via:bkerr
labor
politics
political-economy
cultural-assumptions
worklife
not-encouraging
14 days ago

[1705.01088] Visual Attribute Transfer through Deep Image Analogy

15 days ago

We propose a new technique for visual attribute transfer across images that may have very different appearance but have perceptually similar semantic structure. By visual attribute transfer, we mean transfer of visual information (such as color, tone, texture, and style) from one image to another. For example, one image could be that of a painting or a sketch while the other is a photo of a real scene, and both depict the same type of scene.

Our technique finds semantically-meaningful dense correspondences between two input images. To accomplish this, it adapts the notion of "image analogy" with features extracted from a Deep Convolutional Neutral Network for matching; we call our technique Deep Image Analogy. A coarse-to-fine strategy is used to compute the nearest-neighbor field for generating the results. We validate the effectiveness of our proposed method in a variety of cases, including style/texture transfer, color/style swap, sketch/painting to photo, and time lapse.

via:twitter
image-analogies
deep-learning
neural-networks
algorithms
multiobjective-optimization
to-write-about
to-understand
nudge-targets
consider:objective-partitioning
Our technique finds semantically-meaningful dense correspondences between two input images. To accomplish this, it adapts the notion of "image analogy" with features extracted from a Deep Convolutional Neutral Network for matching; we call our technique Deep Image Analogy. A coarse-to-fine strategy is used to compute the nearest-neighbor field for generating the results. We validate the effectiveness of our proposed method in a variety of cases, including style/texture transfer, color/style swap, sketch/painting to photo, and time lapse.

15 days ago

[1510.05464v3] Generation of real algebraic loci via complex detours

15 days ago

We discuss the locus generation algorithm used by the dynamic geometry software Cinderella, and how it uses complex detours to resolve singularities. We show that the algorithm is independent of the orientation of its complex detours. We conjecture that the algorithm terminates if it takes small enough complex detours and small enough steps on every complex detour. Moreover, we introduce a variant of the algorithm that possibly generates entire real connected components of real algebraic loci. Several examples illustrate its use for organic generation of real algebraic loci. Another example shows how we can apply the algorithm to simulate mechanical linkages. Apparently, the use of complex detours produces physically reasonable motion of such linkages.

plane-geometry
algorithms
rather-interesting
nudge-targets
consider:looking-to-see
15 days ago

[1507.07970v2] Dividing the circle

15 days ago

There are known constructions for some regular polygons, usually inscribed in a circle, but not for all polygons - the Gauss-Wantzel Theorem states precisely which ones can be constructed.

The constructions differ greatly from one polygon to the other. There are, however, general processes for determining the side of the n-gon (approximately, but sometimes with great precision), which we describe in this paper. We present a joint mathematical analysis of the so-called Bion and Tempier approximation methods, comparing the errors and trying to explain why these constructions would work at all.

compass-and-straightedge
plane-geometry
construction
approximation
nudge-targets
consider:rediscovery
The constructions differ greatly from one polygon to the other. There are, however, general processes for determining the side of the n-gon (approximately, but sometimes with great precision), which we describe in this paper. We present a joint mathematical analysis of the so-called Bion and Tempier approximation methods, comparing the errors and trying to explain why these constructions would work at all.

15 days ago

[math/0411380] Cosine products, Fourier transforms, and random sums

15 days ago

We investigate several infinite product of cosines and find the closed form using the Fourier transform. The answers provide limiting distributions for some elementary probability experiments.

mathematical-recreations
history
trigonometry
algebra
nudge-targets
consider:looking-to-see
consider:novelty-search
15 days ago

[1208.1329] The multiplication game

15 days ago

The multiplication game is a two-person game in which each player chooses a positive integer without knowledge of the other player's number. The two numbers are then multiplied together and the first digit of the product determines the winner. Rather than analyzing this game directly, we consider a closely related game in which the players choose positive real numbers between 1 and 10, multiply them together, and move the decimal point, if necessary, so that the result is between 1 and 10. The mixed strategies are probability distributions on this interval, and it is shown that for both players it is optimal to choose their numbers from the Benford distribution. Furthermore, this strategy is optimal for any winning set, and the probability of winning is the Benford measure of the player's winning set. Using these results we prove that the original game in which the players choose integers has a well-defined value and that strategies exist that are arbitrarily close to optimal. Finally, we consider generalizations of the game in which players choose elements from a compact topological group and show that choosing them according to Haar measure is an optimal strategy.

mathematical-recreations
game-theory
Benford's-law
number-theory
to-write-about
consider:looking-to-see
nudge-targets
15 days ago

[1212.5161] Smooth neighbors

15 days ago

We give a new algorithm that quickly finds smooth neighbors.

number-theory
algorithms
to-understand
nudge-targets
consider:rediscovery
consider:stress-testing
15 days ago

[1311.6511] Intransitive Dice

15 days ago

We consider n-sided dice whose face values lie between 1 and n and whose faces sum to n(n+1)/2. For two dice A and B, define A≻B if it is more likely for A to show a higher face than B. Suppose k such dice A1,…,Ak are randomly selected. We conjecture that the probability of ties goes to 0 as n grows. We conjecture and provide some supporting evidence that---contrary to intuition---each of the 2(k2) assignments of ≻ or ≺ to each pair is equally likely asymptotically. For a specific example, suppose we randomly select k dice A1,…,Ak and observe that A1≻A2≻…≻Ak. Then our conjecture asserts that the outcomes Ak≻A1 and A1≺Ak both have probability approaching 1/2 as n→∞.

combinatorics
mathematical-recreations
probability-theory
to-write-about
nudge-targets
consider:engineering-design
consider:feature-discovery
15 days ago

[1401.2493] Guessing games

15 days ago

In a guessing game, players guess the value of a random real number selected using some probability density function. The winner may be determined in various ways; for example, a winner can be a player whose guess is closest in magnitude to the target or a winner can be a player coming closest without guessing higher than the target. We study optimal strategies for players in these games and determine some of them for two, three, and four players.

probability-theory
game-theory
games
mathematical-recreations
strategy
nudge-targets
consider:looking-to-see
15 days ago

[1505.07363] An Enumeration of the Equivalence Classes of Self-Dual Matrix Codes

15 days ago

As a result of their applications in network coding, space-time coding, and coding for criss-cross errors, matrix codes have garnered significant attention; in various contexts, these codes have also been termed rank-metric codes, space-time codes over finite fields, and array codes. We focus on characterizing matrix codes that are both efficient (have high rate) and effective at error correction (have high minimum rank-distance). It is well known that the inherent trade-off between dimension and minimum distance for a matrix code is reversed for its dual code; specifically, if a matrix code has high dimension and low minimum distance, then its dual code will have low dimension and high minimum distance. With an aim towards finding codes with a perfectly balanced trade-off, we study self-dual matrix codes. In this work, we develop a framework based on double cosets of the matrix-equivalence maps to provide a complete classification of the equivalence classes of self-dual matrix codes, and we employ this method to enumerate the equivalence classes of these codes for small parameters.

information-theory
matrices
combinatorics
rather-interesting
to-write-about
nudge-targets
consider:feature-discovery
consider:rediscovery
15 days ago

[1409.5531] A mathematical theory of resources

15 days ago

In many different fields of science, it is useful to characterize physical states and processes as resources. Chemistry, thermodynamics, Shannon's theory of communication channels, and the theory of quantum entanglement are prominent examples. Questions addressed by a theory of resources include: Which resources can be converted into which other ones? What is the rate at which arbitrarily many copies of one resource can be converted into arbitrarily many copies of another? Can a catalyst help in making an impossible transformation possible? How does one quantify the resource? Here, we propose a general mathematical definition of what constitutes a resource theory. We prove some general theorems about how resource theories can be constructed from theories of processes wherein there is a special class of processes that are implementable at no cost and which define the means by which the costly states and processes can be interconverted one to another. We outline how various existing resource theories fit into our framework. Our abstract characterization of resource theories is a first step in a larger project of identifying universal features and principles of resource theories. In this vein, we identify a few general results concerning resource convertibility.

systems
formalization
rather-interesting
to-understand
to-write-about
systems-biology
representation
15 days ago

The 20% Statistician: Five reasons blog posts are of higher scientific quality than journal articles

15 days ago

Five reasons blog posts are of higher scientific quality than journal articles

academia
academic-culture
publishing
philosophy-of-science
citation
best-practices
to-write-about
15 days ago

Best Git Client 2017 - Features | GitKraken

15 days ago

GitKraken is the only Git client built on Electron, allowing it to run natively on Windows, Mac and Linux desktop systems. Enjoy the same luxurious experience across all three!

via:many
git
software-development
UI
to-try
15 days ago

[1705.00186] Cyclic Hypergraph Degree Sequences

15 days ago

The problem of efficiently characterizing degree sequences of simple hypergraphs is a fundamental long-standing open problem in Graph Theory. Several results are known for restricted versions of this problem. This paper adds to the list of sufficient conditions for a degree sequence to be {\em hypergraphic}. This paper proves a combinatorial lemma about cyclically permuting the columns of a binary table with length n binary sequences as rows. We prove that for any set of cyclic permutations acting on its columns, the resulting table has all of its 2n rows distinct. Using this property, we first define a subset {\em cyclic hyper degrees} of hypergraphic sequences and show that they admit a polynomial time recognition algorithm. Next, we prove that there are at least 2(n−1)(n−2)2 {\em cyclic hyper degrees}, which also serves as a lower bound on the number of {\em hypergraphic} sequences. The {\em cyclic hyper degrees} also enjoy a structural characterization, they are the integral points contained in the union of some n-dimensional rectangles.

hypergraphs
combinatorics
rather-interesting
classification
feature-discovery
algorithms
computational-complexity
performance-measure
nudge-targets
consider:looking-to-see
15 days ago

[1607.08597] Efficient modularity optimization by self-avoiding walk

15 days ago

Different kinds of random walks have showed to be useful in the study of the structural properties of complex networks. Among them, the restricted dynamics of the self-avoiding random walk (SAW), which reaches only unvisited vertices in the same walk, has been succesfully used in network exploration. SAWs are therefore a promising tool to investigate community structures in networks. Despite its importance, community detection remains an open problem due to the high computational complexity of the associated optimization problem and a lack of a unique formal definition of communities. In this work, we propose a SAW-based modularity optimization algorithm to extract the community distribution of a network that achieves high modularity scores. We combined SAW with principal component analyses to define the dissimilarity measure and use agglomerative hierarchical clustering. To evaluate the performance of this algorithm we compare it with three popular methods for community detection: Girvan-Newman, Fastgreedy and Walktrap, using two types of synthetic networks and six well-known real world cases.

network-theory
feature-construction
random-walks
algorithms
rather-interesting
nudge-targets
consider:approximation
computational-complexity
15 days ago

[1705.00317] Non-polynomial Worst-Case Analysis of Recursive Programs

15 days ago

We study the problem of developing efficient approaches for proving worst-case bounds of non-deterministic recursive programs. Ranking functions are sound and complete for proving termination and worst-case bounds of nonrecursive programs. First, we apply ranking functions to recursion, resulting in measure functions. We show that measure functions provide a sound and complete approach to prove worst-case bounds of non-deterministic recursive programs. Our second contribution is the synthesis of measure functions in nonpolynomial forms. We show that non-polynomial measure functions with logarithm and exponentiation can be synthesized through abstraction of logarithmic or exponentiation terms, Farkas' Lemma, and Handelman's Theorem using linear programming. While previous methods obtain worst-case polynomial bounds, our approach can synthesize bounds of the form (nlogn) as well as (nr) where r is not an integer. We present experimental results to demonstrate that our approach can obtain efficiently worst-case bounds of classical recursive algorithms such as (i) Merge-Sort, the divide-and-conquer algorithm for the Closest-Pair problem, where we obtain (nlogn) worst-case bound, and (ii) Karatsuba's algorithm for polynomial multiplication and Strassen's algorithm for matrix multiplication, where we obtain (nr) bound such that r is not an integer and close to the best-known bounds for the respective algorithms.

computer-science
recursion
algorithms
to-understand
benchmarking
computational-complexity
15 days ago

[1608.00771] Smart Contract Templates: foundations, design landscape and research directions

15 days ago

In this position paper, we consider some foundational topics regarding smart contracts (such as terminology, automation, enforceability, and semantics) and define a smart contract as an automatable and enforceable agreement. We explore a simple semantic framework for smart contracts, covering both operational and non-operational aspects, and describe templates and agreements for legally-enforceable smart contracts, based on legal documents. Building upon the Ricardian Contract, we identify operational parameters in the legal documents and use these to connect legal agreements to standardised code. We also explore the design landscape, including increasing sophistication of parameters, increasing use of common standardised code, and long-term research.

law
contracts
to-write-about
formalization
ontology
software-development-is-not-programming
law-is-not-code-writing
15 days ago

[1703.07915] Perspective: Energy Landscapes for Machine Learning

15 days ago

Machine learning techniques are being increasingly used as flexible non-linear fitting and prediction tools in the physical sciences. Fitting functions that exhibit multiple solutions as local minima can be analysed in terms of the corresponding machine learning landscape. Methods to explore and visualise molecular potential energy landscapes can be applied to these machine learning landscapes to gain new insight into the solution space involved in training and the nature of the corresponding predictions. In particular, we can define quantities analogous to molecular structure, thermodynamics, and kinetics, and relate these emergent properties to the structure of the underlying landscape. This Perspective aims to describe these analogies with examples from recent applications, and suggest avenues for new interdisciplinary research.

machine-learning
introspection
rather-interesting
fitness-landscapes
energy-landscapes
visualization
to-write-about
consider:performance-measures
algorithms
feature-construction
15 days ago

academia
academic-culture
activism
advice
agent-based
agility
algorithms
amusing
ann-arbor
approximation
architecture
archive
art
artificial-intelligence
artificial-life
bankers-should-start-avoiding-lampposts-right-about-now
benchmarking
bioinformatics
biological-engineering
blogging
books
bushism
business
business-culture
business-model
cellular-automata
classification
clustering
collaboration
collective-intelligence
combinatorics
commons
communication
community
complex-systems
complexology
compressed-sensing
computational-complexity
computational-geometry
computer-science
conservatism
consider:feature-discovery
consider:looking-to-see
consider:performance-measures
consider:rediscovery
consider:representation
consider:stress-testing
constraint-satisfaction
copyright
corporatism
crowdsourcing
cultural-assumptions
cultural-dynamics
cultural-norms
data-analysis
data-mining
deep-learning
design
design-patterns
development
digital-humanities
digitization
disintermediation-in-action
distributed-processing
diversity
dynamical-systems
economics
education
emergence
emergent-design
engineering
engineering-design
evolutionary-algorithms
evolutionary-economics
experiment
feature-construction
feature-extraction
finance
financial-crisis
fitness-landscapes
formalization
game-theory
games
generative-art
genetic-programming
geometry
google
government
graph-theory
graphic-design
heuristics
history
horse-races
humor
image-analysis
image-processing
image-segmentation
inference
information-theory
innovation
intellectual-property
interesting
inverse-problems
investment
javascript
kauffmania
language
law
lawyers
learning
learning-by-doing
learning-from-data
library
local
machine-learning
macos
management
marketing
mathematical-recreations
mathematics
matrices
media
metaheuristics
metrics
michigan
modeling
models
models-and-modes
multiobjective-optimization
music
nanohistory
nanotechnology
natural-language-processing
network-theory
networks
neural-networks
nonlinear-dynamics
nudge
nudge-targets
number-theory
numerical-methods
open-access
open-questions
open-source
openness
operations-research
optimization
pedagogy
performance-measure
philosophy
philosophy-of-science
photography
physics
planning
politics
prediction
probability-theory
programming
project-management
proof
public-policy
publishing
rather-interesting
representation
research
review
robotics
robustness
ruby
science
self-organization
signal-processing
simulation
social-dynamics
social-engineering
social-networks
social-norms
sociology
software
software-development
statistics
strings
sustainability
systems-biology
technology
the-mangle-in-practice
theoretical-biology
tiling
time-series
to-read
to-understand
to-write-about
tools
trading
tutorial
typography
user-experience
via:cshalizi
video
visualization
web-design
web2.0
worklife
writing