[1605.04679] Typical Performance of Approximation Algorithms for NP-hard Problems
Typical performance of approximation algorithms is studied for randomized minimum vertex cover problems. A wide class of random graph ensembles characterized by an arbitrary degree distribution is discussed with some theoretical frameworks. Here three approximation algorithms are examined; the linear-programming relaxation, the loopy-belief propagation, and the leaf-removal algorithm. The former two algorithms are analyzed using the statistical-mechanical technique while the average-case analysis of the last one is studied by the generating function method. These algorithms have a threshold in the typical performance with increasing the average degree of the random graph, below which they find true optimal solutions with high probability. Our study reveals that there exist only three cases determined by the order of the typical-performance thresholds. We provide some conditions for classifying the graph ensembles and demonstrate explicitly examples for the difference in the threshold.
approximation  computational-complexity  rather-interesting  to-write-about  to-do  nudge-targets  consider:approximation 
2 days ago
[1711.01129] Hamilton-Jacobi Theory and Information Geometry
Recently, a method to dynamically define a divergence function D for a given statistical manifold (,g,T) by means of the Hamilton-Jacobi theory associated with a suitable Lagrangian function 𝔏 on T has been proposed. Here we will review this construction and lay the basis for an inverse problem where we assume the divergence function D to be known and we look for a Lagrangian function 𝔏 for which D is a complete solution of the associated Hamilton-Jacobi theory. To apply these ideas to quantum systems, we have to replace probability distributions with probability amplitudes.
information-geometry  statistics  information-theory  to-understand  modeling 
2 days ago
Directory of Mathematical Headaches
Let’s try to create headaches for the concepts below.
Ask yourself, “If this skill is aspirin, then what is the headache and how do I create it?”
Ask yourself, “How would a mathematician’s life be worse if they didn’t have this skill?”
Let that guide you in your design of an activity for students.
via:robertogreco  pedagogy  mathematics  nudge-targets  machine-learning-targets 
2 days ago
Gauges – Web Analytics Software
Website Analytics you can Actually Understand
Gauges helps you focus on your most important web traffic stats — in real time.
Google-replacements  web-design  analytics  services  subscriptions 
2 days ago
Vulpa™ - Webfont & Desktop font « MyFonts
Vulpa is a charming serif family in regular, italic and bold, informed by the proportions of a personal favorite, Plantin. The quirky foxtail terminals (inspired in part by my script font, Gelato Script) can be seen across all three styles. These little details make the typeface very expressive at display sizes, but practically disappear at text sizes, making for a very versatile face. More…
typeface  want 
10 days ago
Mathematics must be creative, else it ain’t mathematics
When people ask, often cynically, what creativity looks like, it is surely this: the ability to join seemingly disparate ideas to form new expressions of thought and emotion.
By this definition, mathematics must be considered a creative pursuit. The mathematical world is governed by patterns and symmetries, some of them known and most of them awaiting our discovery.
There are no topics in mathematics; only artificial barriers that we have erected to help organise the curriculum. At school, we study topics in discrete chunks and come to understand them as separate islands of knowledge. Yet the most powerful and interesting mathematics arises when we cut through these barriers.
creativity  mathematics  mathematical-recreations  to-write-about  essay  system-of-professions 
10 days ago
[1711.08412] Word Embeddings Quantify 100 Years of Gender and Ethnic Stereotypes
Word embeddings use vectors to represent words such that the geometry between vectors captures semantic relationship between the words. In this paper, we develop a framework to demonstrate how the temporal dynamics of the embedding can be leveraged to quantify changes in stereotypes and attitudes toward women and ethnic minorities in the 20th and 21st centuries in the United States. We integrate word embeddings trained on 100 years of text data with the U.S. Census to show that changes in the embedding track closely with demographic and occupation shifts over time. The embedding captures global social shifts -- e.g., the women's movement in the 1960s and Asian immigration into the U.S -- and also illuminates how specific adjectives and occupations became more closely associated with certain populations over time. Our framework for temporal analysis of word embedding opens up a powerful new intersection between machine learning and quantitative social science.
digital-humanities  text-processing  big-data  rather-interesting  history  to-write-about  sociology 
10 days ago
[1704.00640] Symmetric motifs in random geometric graphs
We study symmetric motifs in random geometric graphs. Symmetric motifs are subsets of nodes which have the same adjacencies. These subgraphs are particularly prevalent in random geometric graphs and appear in the Laplacian and adjacency spectrum as sharp, distinct peaks, a feature often found in real-world networks. We look at the probabilities of their appearance and compare these across parameter space and dimension. We then use the Chen-Stein method to derive the minimum separation distance in random geometric graphs which we apply to study symmetric motifs in both the intensive and thermodynamic limits. In the thermodynamic limit the probability that the closest nodes are symmetric approaches one, whilst in the intensive limit this probability depends upon the dimension.
graph-theory  network-theory  rather-interesting  probability-theory  symmetry  to-write-about  to-simulate 
10 days ago
Information Theory of Complex Networks
Complex networks are characterized by highly heterogeneous distributions of links, often pervading the presence of key properties such as robustness under node removal. Several correlation measures have been defined in order to characterize the structure of these nets. Here we show that mutual information, noise and joint entropies can be properly defined on a static graph. These measures are computed for a number of real networks and analytically estimated for some simple standard models. It is shown that real networks are clustered in a well-defined domain of the entropy- noise space. By using simulated annealing optimization, it is shown that optimally heterogeneous nets actually cluster around the same narrow domain, suggesting that strong constraints actually operate on the possible universe of complex networks. The evolutionary implications are discussed
via:twitter  complexology  network-theory  information-theory  to-read  hey-I-know-this-guy 
10 days ago
[1708.04215] A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.
Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem.
algorithms  via:vielmetti  operations-research  approximation  optimization  computational-complexity  to-write-about  nudge-targets  consider:looking-to-see 
10 days ago
[1711.07387] How morphological development can guide evolution
Organisms result from multiple adaptive processes occurring and interacting at different time scales. One such interaction is that between development and evolution. In modeling studies, it has been shown that development sweeps over a series of traits in a single agent, and sometimes exposes promising static traits. Subsequent evolution can then canalize these rare traits. Thus, development can, under the right conditions, increase evolvability. Here, we report on a previously unknown phenomenon when embodied agents are allowed to develop and evolve: Evolution discovers body plans which are robust to control changes, these body plans become genetically assimilated, yet controllers for these agents are not assimilated. This allows evolution to continue climbing fitness gradients by tinkering with the developmental programs for controllers within these permissive body plans. This exposes a previously unknown detail about the Baldwin effect: instead of all useful traits becoming genetically assimilated, only phenotypic traits that render the agent robust to changes in other traits become assimilated. We refer to this phenomenon as differential canalization. This finding also has important implications for the evolutionary design of artificial and embodied agents such as robots: robots that are robust to internal changes in their controllers may also be robust to external changes in their environment, such as transferal from simulation to reality, or deployment in novel environments.
artificial-life  evolved-devo  developmental-biology  representation  rather-interesting  genetic-programming  hey-I-know-this-guy 
10 days ago
acrolinx/clj-queue-by: A queue which schedules fairly by key
We developed this library with a program in mind that requires a central in-memory queue. The queue must allow the program to serve active users in a timely manner while still ensuring that users with massive traffic get their job done eventually.
queueing-theory  software  library  Clojure  to-learn  to-understand  distributed-processing 
10 days ago
OpenAPI Specification | Swagger
The OpenAPI Specification (OAS) defines a standard, language-agnostic interface to RESTful APIs which allows both humans and computers to discover and understand the capabilities of the service without access to source code, documentation, or through network traffic inspection. When properly defined, a consumer can understand and interact with the remote service with a minimal amount of implementation logic.
OpenAPI  software-development-is-not-programming  standards  API  to-learn  to-use 
10 days ago
Game & Puzzle Design
Game & Puzzle Design is a peer-reviewed print journal publishing high quality work on all aspects of game and puzzle design. The journal aims to bring together designers and researchers from a variety of backgrounds, to foster a deeper understanding of games and facilitate the creation of new high quality games and puzzles. We are particularly interested in the intersection between traditional and digital game design, and the points at which these disciplines converge and diverge.

Submissions may pertain to any type of game or puzzle – abstract, physical, printed, digital, etc. – but should focus on underlying mechanics or gameplay rather than visual design. The emphasis will be on traditional games and puzzles, although submissions on digital games (other than major AAA video games) are also welcome, especially where links are drawn between traditional and digital design approaches.
games  mathematical-recreations  journal  to-read  not-open  to-write-about 
14 days ago
[1710.03248] Synthesizing Bijective Lenses
Bidirectional transformations between different data representations occur frequently in modern software systems. They appear as serializers and deserializers, as database views and view updaters, and more. Manually building bidirectional transformations---by writing two separate functions that are intended to be inverses---is tedious and error prone. A better approach is to use a domain-specific language in which both directions can be written as a single expression. However, these domain-specific languages can be difficult to program in, requiring programmers to manage fiddly details while working in a complex type system.
To solve this, we present Optician, a tool for type-directed synthesis of bijective string transformers. The inputs to Optician are two ordinary regular expressions representing two data formats and a few concrete examples for disambiguation. The output is a well-typed program in Boomerang (a bidirectional language based on the theory of lenses). The main technical challenge involves navigating the vast program search space efficiently enough. Unlike most prior work on type-directed synthesis, our system operates in the context of a language with a rich equivalence relation on types (the theory of regular expressions). We synthesize terms of a equivalent language and convert those generated terms into our lens language. We prove the correctness of our synthesis algorithm. We also demonstrate empirically that our new language changes the synthesis problem from one that admits intractable solutions to one that admits highly efficient solutions. We evaluate Optician on a benchmark suite of 39 examples including both microbenchmarks and realistic examples derived from other data management systems including Flash Fill, a tool for synthesizing string transformations in spreadsheets, and Augeas, a tool for bidirectional processing of Linux system configuration files.
programming-language  to-understand  data-structures  translation  strings  to-write-about  nudge-targets? 
16 days ago
[1710.03370] iVQA: Inverse Visual Question Answering
In recent years, visual question answering (VQA) has become topical as a long-term goal to drive computer vision and multi-disciplinary AI research. The premise of VQA's significance, is that both the image and textual question need to be well understood and mutually grounded in order to infer the correct answer. However, current VQA models perhaps `understand' less than initially hoped, and instead master the easier task of exploiting cues given away in the question and biases in the answer distribution.
In this paper we propose the inverse problem of VQA (iVQA), and explore its suitability as a benchmark for visuo-linguistic understanding. The iVQA task is to generate a question that corresponds to a given image and answer pair. Since the answers are less informative than the questions, and the questions have less learnable bias, an iVQA model needs to better understand the image to be successful. We pose question generation as a multi-modal dynamic inference process and propose an iVQA model that can gradually adjust its focus of attention guided by both a partially generated question and the answer. For evaluation, apart from existing linguistic metrics, we propose a new ranking metric. This metric compares the ground truth question's rank among a list of distractors, which allows the drawbacks of different algorithms and sources of error to be studied. Experimental results show that our model can generate diverse, grammatically correct and content correlated questions that match the given answer.
artificial-intelligence  image-analysis  rather-interesting  jeopardy-questions  inverse-problems  natural-language-processing  to-write-about  nudge-targets  benchmarks 
16 days ago
[1703.07856] Testing for the Equality of two Distributions on High Dimensional Object Spaces
Energy statistics are estimators of the energy distance that depend on the distances between observations. The idea behind energy statistics is to consider a statistical potential energy that would parallel Newton's gravitational potential energy. This statistical potential energy is zero if and only if a certain null hypothesis relating two distributions holds true. In Szekely and Rizzo(2004), a nonparametric test for equality of two multivariate distributions was given, based on the Euclidean distance between observations. This test was shown to be effective for high dimensional multivariate data, and was implemented by an appropriate distribution free permutation test. As an extension of Szekely and Rizzo (2013), here we consider the energy distance between to independent random objects X and Y on the object space M, that admits an embedding into an Euclidean space. In the case of a Kendall shape space, we can use its VW-embedding into an Euclidean space of matrices and define the extrinsic distance between two shapes as their VW associated distance. The corresponding energy distance between two distributions of Kendall shapes of k-ads will be called VW-energy distance We test our methodology on, to compare the distributions of Kendall shape of the contour of the midsagittal section of the Corpus Callossum in normal vs ADHD diagnosed individuals. Here we use the VW distance between the shapes of two children CC midsections. Using the CC data coming originally from this http URL 1000.projects.nitrc.org/indi/adhd200/ it appears that the two Kendall shape distributions are not significantly different.
classification  feature-construction  rather-interesting  computer-vision  representation  algorithms  nudge-targets  consider:rediscovery  consider:looking-to-see 
16 days ago
[1710.04562] Universal Scaling in Complex Substitutive Systems
Diffusion processes are central to human interactions. Despite extensive studies that span multiple disciplines, our knowledge is limited to spreading processes in non-substitutive systems. Yet, a considerable number of ideas, products and behaviors spread by substitution-to adopt a new one, agents must give up an existing one. Here, we find that, ranging from mobile handsets to automobiles to smart phone apps, early growth patterns in substitutive systems follow a power law with non-integer exponents, in sharp contrast to the exponential growth customary in spreading phenomena. Tracing 3.6 million individuals substituting for mobile handsets for over a decade, we uncover three generic ingredients governing substitutive processes, allowing us to develop a minimal substitution model, which not only predict analytically the observed growth patterns, but also collapse growth trajectories of constituents from rather diverse systems into a single universal curve. These results demonstrate that the dynamics of complex substitutive systems are governed by robust self-organizing principles that go beyond the particulars of individual systems, which implies that these results could guide the understanding and prediction of all spreading phenomena driven by substitutions, from electric cars to scientific paradigms, from renewable energy to new healthy habits.
social-dynamics  consumerism  economics  rather-interesting  scaling  power-laws  to-read  to-write-about  consider:simulation 
16 days ago
[1710.03453] The Sparse Multivariate Method of Simulated Quantiles
In this paper the method of simulated quantiles (MSQ) of Dominicy and Veredas (2013) and Dominick et al. (2013) is extended to a general multivariate framework (MMSQ) and to provide a sparse estimator of the scale matrix (sparse-MMSQ). The MSQ, like alternative likelihood-free procedures, is based on the minimisation of the distance between appropriate statistics evaluated on the true and synthetic data simulated from the postulated model. Those statistics are functions of the quantiles providing an effective way to deal with distributions that do not admit moments of any order like the α-Stable or the Tukey lambda distribution. The lack of a natural ordering represents the major challenge for the extension of the method to the multivariate framework. Here, we rely on the notion of projectional quantile recently introduced by Hallin etal. (2010) and Kong Mizera (2012). We establish consistency and asymptotic normality of the proposed estimator. The smoothly clipped absolute deviation (SCAD) ℓ1--penalty of Fan and Li (2001) is then introduced into the MMSQ objective function in order to achieve sparse estimation of the scaling matrix which is the major responsible for the curse of dimensionality problem. We extend the asymptotic theory and we show that the sparse-MMSQ estimator enjoys the oracle properties under mild regularity conditions. The method is illustrated and its effectiveness is tested using several synthetic datasets simulated from the Elliptical Stable distribution (ESD) for which alternative methods are recognised to perform poorly. The method is then applied to build a new network-based systemic risk measurement framework. The proposed methodology to build the network relies on a new systemic risk measure and on a parametric test of statistical dominance.
statistics  reinventing-the-wheel  how-is-this-not-constrained-symbolic-regression?  algorithms  models-and-modes  to-understand  inference 
16 days ago
[1708.08691] Extremal solutions to some art gallery and terminal-pairability problems
The chosen tool of this thesis is an extremal type approach. The lesson drawn by the theorems proved in the thesis is that surprisingly small compromise is necessary on the efficacy of the solutions to make the approach work. The problems studied have several connections to other subjects and practical applications.
The first part of the thesis is concerned with orthogonal art galleries. A sharp extremal bound is proved on partitioning orthogonal polygons into at most 8-vertex polygons using established techniques in the field of art gallery problems. This fills in the gap between already known results for partitioning into at most 6- and 10-vertex orthogonal polygons.
Next, these techniques are further developed to prove a new type of extremal art gallery result. The novelty provided by this approach is that it establishes a connection between mobile and stationary guards. This theorem has strong computational consequences, in fact, it provides the basis for an 83-approximation algorithm for guarding orthogonal polygons with rectangular vision.
In the second part, the graph theoretical concept of terminal-pairability is studied in complete and complete grid graphs. Once again, the extremal approach is conductive to discovering efficient methods to solve the problem.
In the case of a complete base graph, the new demonstrated lower bound on the maximum degree of realizable demand graphs is 4 times higher than previous best results. The techniques developed are then used to solve the classical extremal edge number problem for the terminal-pairability problem in complete base graphs.
The complete grid base graph lies on the other end of the spectrum in terms density amongst path-pairable graphs. It is shown that complete grid graphs are relatively efficient in routing edge-disjoint paths.
computational-geometry  combinatorics  plane-geometry  extreme-values  rather-interesting  to-write-about  nudge-targets  consider:approximation  consider:looking-to-see 
26 days ago
[1710.03395] Efficient Dynamic Dictionary Matching with DAWGs and AC-automata
The dictionary matching is a task to find all occurrences of pattern strings in a set D (called a dictionary) on a text string T. The Aho-Corasick-automaton (AC-automaton) is a data structure which enables us to solve the dictionary matching problem in O(dlogσ) preprocessing time and O(nlogσ+occ) matching time, where d is the total length of the patterns in D, n is the length of the text, σ is the alphabet size, and occ is the total number of occurrences of all the patterns in the text. The dynamic dictionary matching is a variant where patterns may dynamically be inserted into and deleted from D. This problem is called semi-dynamic dictionary matching if only insertions are allowed. In this paper, we propose two efficient algorithms. For a pattern of length m, our first algorithm supports insertions in O(mlogσ+logd/loglogd) time and pattern matching in O(nlogσ+occ) time for the semi-dynamic setting and supports both insertions and deletions in O(σm+logd/loglogd) time and pattern matching in O(n(logd/loglogd+logσ)+occ(logd/loglogd)) time for the dynamic setting by some modifications. This algorithm is based on the directed acyclic word graph. Our second algorithm, which is based on the AC-automaton, supports insertions in O(mlogσ+uf+uo) time for the semi-dynamic setting and supports both insertions and deletions in O(σm+uf+uo) time for the dynamic setting, where uf and uo respectively denote the numbers of states of which the failure function and the output function need to be updated. This algorithm performs pattern matching in O(nlogσ+occ) time for both settings. Our algorithm achieves optimal update time for AC-automaton based methods, since any algorithm which explicitly maintains the AC-automaton requires Ω(uf+uo) update time.
algorithms  strings  rather-interesting  formal-languages  representation  rewriting-systems  to-write-about  consider:rediscovery  nudge-targets 
26 days ago
[1706.01557] The minimum Manhattan distance and minimum jump of permutations
Let π be a permutation of {1,2,…,n}. If we identify a permutation with its graph, namely the set of n dots at positions (i,π(i)), it is natural to consider the minimum L1 (Manhattan) distance, d(π), between any pair of dots. The paper computes the expected value of d(π) when n→∞ and π is chosen uniformly, and settles a conjecture of Bevan, Homberger and Tenner (motivated by permutation patterns), showing that when d is fixed and n→∞, the probability that d(π)≥d+2 tends to e−d2−d.
The minimum jump 𝗆𝗃(π) of π, defined by 𝗆𝗃(π)=min1≤i≤n−1|π(i+1)−π(i)|, is another natural measure in this context. The paper computes the expected value of 𝗆𝗃(π), and the asymptotic probability that 𝗆𝗃(π)≥d+1 for any constant d.
combinatorics  probability-theory  permutations  rather-interesting  to-write-about  to-simulate  nudge-targets  consider:looking-to-see 
26 days ago
[1711.01012] Genetic Policy Optimization
Genetic algorithms have been widely used in many practical optimization problems. Inspired by natural selection, operators, including mutation, crossover and selection, provide effective heuristics for search and black-box optimization. However, they have not been shown useful for deep reinforcement learning, possibly due to the catastrophic consequence of parameter crossovers of neural networks. Here, we present Genetic Policy Optimization (GPO), a new genetic algorithm for sample-efficient deep policy optimization. GPO uses imitation learning for policy crossover in the state space and applies policy gradient methods for mutation. Our experiments on Mujoco tasks show that GPO as a genetic algorithm is able to provide superior performance over the state-of-the-art policy gradient methods and achieves comparable or higher sample efficiency.
machine-learning  genetic-algorithm  representation  reinvented-wheel  to-understand  to-write-about  evolutionary-algorithms 
26 days ago
[1610.08123] Socratic Learning: Augmenting Generative Models to Incorporate Latent Subsets in Training Data
A challenge in training discriminative models like neural networks is obtaining enough labeled training data. Recent approaches use generative models to combine weak supervision sources, like user-defined heuristics or knowledge bases, to label training data. Prior work has explored learning accuracies for these sources even without ground truth labels, but they assume that a single accuracy parameter is sufficient to model the behavior of these sources over the entire training set. In particular, they fail to model latent subsets in the training data in which the supervision sources perform differently than on average. We present Socratic learning, a paradigm that uses feedback from a corresponding discriminative model to automatically identify these subsets and augments the structure of the generative model accordingly. Experimentally, we show that without any ground truth labels, the augmented generative model reduces error by up to 56.06% for a relation extraction task compared to a state-of-the-art weak supervision technique that utilizes generative models.
machine-learning  algorithms  performance-space-analysis  coevolution  to-write-about  system-of-professions  reinvented-wheels 
26 days ago
[1710.06993] Improved Search in Hamming Space using Deep Multi-Index Hashing
Similarity-preserving hashing is a widely-used method for nearest neighbour search in large-scale image retrieval tasks. There has been considerable research on generating efficient image representation via the deep-network-based hashing methods. However, the issue of efficient searching in the deep representation space remains largely unsolved. To this end, we propose a simple yet efficient deep-network-based multi-index hashing method for simultaneously learning the powerful image representation and the efficient searching. To achieve these two goals, we introduce the multi-index hashing (MIH) mechanism into the proposed deep architecture, which divides the binary codes into multiple substrings. Due to the non-uniformly distributed codes will result in inefficiency searching, we add the two balanced constraints at feature-level and instance-level, respectively. Extensive evaluations on several benchmark image retrieval datasets show that the learned balanced binary codes bring dramatic speedups and achieve comparable performance over the existing baselines.
metrics  image-processing  deep-learning  performance-space-analysis  feature-construction  machine-learning  rather-interesting  similarity-measures  to-write-about 
26 days ago
[1610.06934] The K Shortest Paths Problem with Application to Routing
Due to the computational complexity of finding almost shortest simple paths, we propose that identifying a larger collection of (nonbacktracking) paths is more efficient than finding almost shortest simple paths on positively weighted real-world networks. First, we present an easy to implement O(mlogm+kL) solution for finding all (nonbacktracking) paths with bounded length D between two arbitrary nodes on a positively weighted graph, where L is an upperbound for the number of nodes in any of the k outputted paths. Subsequently, we illustrate that for undirected Chung-Lu random graphs, the ratio between the number of nonbacktracking and simple paths asymptotically approaches 1 with high probability for a wide range of parameters. We then consider an application to the almost shortest paths algorithm to measure path diversity for internet routing in a snapshot of the Autonomous System graph subject to an edge deletion process.
planning  data-structures  algorithms  rather-interesting  operations-research  graph-theory  to-write-about  nudge-targets  consider:looking-to-see 
26 days ago
[1711.03172] Curve Reconstruction via the Global Statistics of Natural Curves
Reconstructing the missing parts of a curve has been the subject of much computational research, with applications in image inpainting, object synthesis, etc. Different approaches for solving that problem are typically based on processes that seek visually pleasing or perceptually plausible completions. In this work we focus on reconstructing the underlying physically likely shape by utilizing the global statistics of natural curves. More specifically, we develop a reconstruction model that seeks the mean physical curve for a given inducer configuration. This simple model is both straightforward to compute and it is receptive to diverse additional information, but it requires enough samples for all curve configurations, a practical requirement that limits its effective utilization. To address this practical issue we explore and exploit statistical geometrical properties of natural curves, and in particular, we show that in many cases the mean curve is scale invariant and often times it is extensible. This, in turn, allows to boost the number of examples and thus the robustness of the statistics and its applicability. The reconstruction results are not only more physically plausible but they also lead to important insights on the reconstruction problem, including an elegant explanation why certain inducer configurations are more likely to yield consistent perceptual completions than others.
inference  computer-vision  rather-interesting  algorithms  nudge-targets  consider:looking-to-see  consider:representation  performance-measure  to-write-about 
26 days ago
[1704.07422] Iterative Methods for Photoacoustic Tomography in Attenuating Acoustic Media
The development of efficient and accurate reconstruction methods is an important aspect of tomographic imaging. In this article, we address this issue for photoacoustic tomography. To this aim, we use models for acoustic wave propagation accounting for frequency dependent attenuation according to a wide class of attenuation laws that may include memory. We formulate the inverse problem of photoacoustic tomography in attenuating medium as an ill-posed operator equation in a Hilbert space framework that is tackled by iterative regularization methods. Our approach comes with a clear convergence analysis. For that purpose we derive explicit expressions for the adjoint problem that can efficiently be implemented. In contrast to time reversal, the employed adjoint wave equation is again damping and, thus has a stable solution. This stability property can be clearly seen in our numerical results. Moreover, the presented numerical results clearly demonstrate the Efficiency and accuracy of the derived iterative reconstruction algorithms in various situations including the limited view case.
tomography  numerical-methods  inverse-problems  rather-interesting  signal-processing  algorithms  nudge-targets  consider:benchmarking  consider:looking-to-see 
26 days ago
[1705.01887] Streaming for Aibohphobes: Longest Palindrome with Mismatches
A palindrome is a string that reads the same as its reverse, such as "aibohphobia" (fear of palindromes). Given an integer d>0, a d-near-palindrome is a string of Hamming distance at most d from its reverse. We study the natural problem of identifying a longest d-near-palindrome in data streams. The problem is relevant to the analysis of DNA databases, and to the task of repairing recursive structures in documents such as XML and JSON. We present an algorithm that returns a d-near-palindrome whose length is within a multiplicative (1+ϵ)-factor of the longest d-near-palindrome. Our algorithm also returns the set of mismatched indices of the d-near-palindrome, using (dlog7nϵlog(1+ϵ)) bits of space, and (dlog6nϵlog(1+ϵ)) update time per arriving symbol. We show that Ω(dlogn) space is necessary for estimating the length of longest d-near-palindromes with high probability. We further obtain an additive-error approximation algorithm and a comparable lower bound, as well as an exact two-pass algorithm that solves the longest d-near-palindrome problem using (d2n‾√log6n) bits of space.
strings  computational-complexity  algorithms  probability-theory  inference  online-learning  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:representation 
26 days ago
[1611.07769] The many facets of community detection in complex networks
Community detection, the decomposition of a graph into essential building blocks, has been a core research topic in network science over the past years. Since a precise notion of what constitutes a community has remained evasive, community detection algorithms have often been compared on benchmark graphs with a particular form of assortative community structure and classified based on the mathematical techniques they employ. However, this comparison can be misleading because apparent similarities in their mathematical machinery can disguise different goals and reasons for why we want to employ community detection in the first place. Here we provide a focused review of these different motivations that underpin community detection. This problem-driven classification is useful in applied network science, where it is important to select an appropriate algorithm for the given purpose. Moreover, highlighting the different facets of community detection also delineates the many lines of research and points out open directions and avenues for future research.
community-detection  social-networks  philosophy-of-science  define-your-terms  review  to-write-about 
26 days ago
[1702.01522] Inverse statistical problems: from the inverse Ising problem to data science
Inverse problems in statistical physics are motivated by the challenges of `big data' in different fields, in particular high-throughput experiments in biology. In inverse problems, the usual procedure of statistical physics needs to be reversed: Instead of calculating observables on the basis of model parameters, we seek to infer parameters of a model based on observations. In this review, we focus on the inverse Ising problem and closely related problems, namely how to infer the coupling strengths between spins given observed spin correlations, magnetisations, or other data. We review applications of the inverse Ising problem, including the reconstruction of neural connections, protein structure determination, and the inference of gene regulatory networks. For the inverse Ising problem in equilibrium, a number of controlled and uncontrolled approximate solutions have been developed in the statistical mechanics community. A particularly strong method, pseudolikelihood, stems from statistics. We also review the inverse Ising problem in the non-equilibrium case, where the model parameters must be reconstructed based on non-equilibrium statistics.
data-science  statistics  inverse-problems  complexology  rather-interesting  inference  to-write-about  review  to-simulate  philosophy-of-science 
26 days ago
[1504.08259] Edit Distance for Pushdown Automata
The edit distance between two words w1,w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages 1,2, where the edit distance from 1 to 2 is the minimal number k such that for every word from 1 there exists a word in 2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses. The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for the following problems: (1)~deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k, and (2)~deciding whether the edit distance from a pushdown automaton to a finite automaton is finite.
formal-languages  edit-distance  metrics  define-your-terms  rather-interesting  open-questions  discrete-mathematics 
26 days ago
[1709.07485] The Covering Path Problem on a Grid
This paper introduces the covering path problem on a grid (CPPG) which finds the cost-minimizing path connecting a subset of points in a grid such that each point is within a predetermined distance of a point from the chosen subset. We leverage the geometric properties of the grid graph which captures the road network structure in many transportation problems, including our motivating setting of school bus routing. As defined in this paper, the CPPG is a bi-objective optimization problem comprised of one cost term related to path length and one cost term related to stop count. We develop a trade-off constraint which quantifies the trade-off between path length and stop count and provides a lower bound for the bi-objective optimization problem. We introduce simple construction techniques to provide feasible paths that match the lower bound within a constant factor. Importantly, this solution approach uses transformations of the general CPPG to either a discrete CPPG or continuous CPPG based on the value of the coverage radius. For both the discrete and continuous versions, we provide fast constant-factor approximations, thus solving the general CPPG.
operations-research  planning  multiobjective-optimization  rather-interesting  to-write-about 
26 days ago
In, against and beyond the Co-operative University | Richard Hall's Space
In part my questioning is situated against my own weltschmerz, in particular in the face of ongoing, secular capitalist crisis with its attendant punishing and disciplinary austerity. However, my questioning extends the nature of this socio-economic crisis, which is destroying the lives/futures of millions of people, into the terrain of socio-environmental crisis. I also wonder why we are building a model in this way that is deliberately connected to a hegemonic system of oppression, and which is rooted in contradictions and tensions around the ongoing nature of work and the availability of employment that is increasingly predicted to be marginalised/made redundant by technology in so many sectors. So in building for an unstable world that is increasingly governed by debt as a moment of social discipline, I found myself asking why are we building in this way for a capitalist world that is collapsing? Is building an alternative form of sociability impossible? I found myself questioning how to enact Rosa Luxemburg’s idea (on socialism or barbarism) that ’to push ahead to the victory of socialism we need a strong, activist, educated proletariat, and masses whose power lies in intellectual culture as well as numbers.’
academia  corporatism  activism  cooperation  institutional-design  life-o'-the-mind  to-read 
29 days ago
CEOs Don’t Steer
This is why CEOs are different from other kinds of leaders. Leaders in other societal roles are typically not the stewards of any source of promethean energy. Instead, they are involved with directing and routing second-order effects that drain it. So they can afford to steer and be clever about it. They are zero-sum carve-the-pie leaders (which is important too, just not the point of this post).

But CEOs don’t steer.

What is good for countries, militaries, and art movements is not good for companies (and conversely, when the Trumps, Modis, and Xi Jinpengs bring CEO-like orientation-locking tendencies to inclusive governance jobs that require non-trivial steering, the results are usually not pretty).
business-culture  leadership  corporatism  worklife  a-reasonable-assessment  myths-of-the-managers 
29 days ago
Why is it more difficult to imagine the end of universities than the end of capitalism, or: is the crisis of the university in fact a crisis of imagination? – Jana Bacevic
I’m particularly interested in questions such as:

Qualifications and credentials: can we imagine a society where universities do not hold a monopoly on credentials? What would this look like?
Knowledge work: can we conceive of knowledge production (teaching and research) not only ‘outside of’, but without the university? What would this look like?
Financing: what other modes of funding for knowledge production are conceivable? Is there a form of public funding that does not involve universities (e.g., through an academic workers’ cooperative – Mondragon University in Spain is one example – or guild)? What would be the implications of this, and how it would be regulated?
Built environment/space: can we think of knowledge not confined to specific buildings or an institution? What would this look like – how would it be organised? What would be the consequences for learning, teaching and research?
academic-culture  disintermediation-in-action  sociology  neoliberalism-sidestepped  life-o'-the-mind 
4 weeks ago
plaidml/plaidml: PlaidML is a framework for making deep learning work everywhere.
PlaidML is a multi-language acceleration framework that:

Enables practitioners to deploy high-performance neural nets on any device
Allows hardware developers to quickly integrate with high-level frameworks
Allows framework developers to easily add support for many kinds of hardware
For background and early benchmarks see our blog post announcing the release. PlaidML is under active development and should be thought of as early alpha quality.
machine-learning  library  software-development  to-learn  to-write-about 
4 weeks ago
[1710.05183] Inferring Mesoscale Models of Neural Computation
Recent years have seen dramatic progress in the development of techniques for measuring the activity and connectivity of large populations of neurons in the brain. However, as these techniques grow ever more powerful---allowing us to even contemplate measuring every neuron in entire brain---a new problem arises: how do we make sense of the mountains of data that these techniques produce? Here, we argue that the time is ripe for building an intermediate or "mesoscale" computational theory that can bridge between single-cell (microscale) accounts of neural function and behavioral (macroscale) accounts of animal cognition and environmental complexity. Just as digital accounts of computation in conventional computers abstract away the non-essential dynamics of the analog circuits that implementing gates and registers, so too a computational account of animal cognition can afford to abstract from the non-essential dynamics of neurons. We argue that the geometry of neural circuits is essential in explaining the computational limitations and technological innovations inherent in biological information processing. We propose a blueprint for how to employ tools from modern machine learning to automatically infer a satisfying mesoscale account of neural computation that combines functional and structural data, with an emphasis on learning and exploiting regularity and repeating motifs in neuronal circuits. Rather than suggest a specific theory, we present a new class of scientific instruments that can enable neuroscientists to design, propose, implement and test mesoscale theories of neural computation.
dynamical-systems  machine-learning  deep-learning  representation  temporal-models  rather-interesting  inference  to-write-about 
4 weeks ago
[1512.00507] Beyond Aztec Castles: Toric Cascades in the $dP_3$ Quiver
Given one of an infinite class of supersymmetric quiver gauge theories, string theorists can associate a corresponding toric variety (which is a Calabi-Yau 3-fold) as well as an associated combinatorial model known as a brane tiling. In combinatorial language, a brane tiling is a bipartite graph on a torus and its perfect matchings are of interest to both combinatorialists and physicists alike. A cluster algebra may also be associated to such quivers and in this paper we study the generators of this algebra, known as cluster variables, for the quiver associated to the cone over the del Pezzo surface dP3. In particular, mutation sequences involving mutations exclusively at vertices with two in-coming arrows and two out-going arrows are referred to as toric cascades in the string theory literature. Such toric cascades give rise to interesting discrete integrable systems on the level of cluster variable dynamics. We provide an explicit algebraic formula for all cluster variables which are reachable by toric cascades as well as a combinatorial interpretation involving perfect matchings of subgraphs of the dP3 brane tiling for these formulas in most cases.
tiling  domino-tiling  enumeration  combinatorics  to-write-about  to-simulate  review  rather-interesting 
4 weeks ago
[1504.00303] A Generalization of Aztec Dragons
Aztec dragons are lattice regions first introduced by James Propp, which have the number of tilings given by a power of 2. This family of regions has been investigated further by a number of authors. In this paper, we consider a generalization of the Aztec dragons to two new families of 6-sided regions. By using Kuo's graphical condensation method, we prove that the tilings of the new regions are always enumerated by powers of 2 and 3.
tiling  combinatorics  enumeration  out-of-the-box  to-write-about  to-simulate 
4 weeks ago
[1504.00291] On the numbers of perfect matchings of trimmed Aztec rectangles
We consider several new families of graphs obtained from Aztec rectangle and augmented Aztec rectangle graphs by trimming two opposite corners. We prove that the perfect matchings of these new graphs are enumerated by powers of 2, 3, 5, and 11. The result yields a proof of a conjectured posed by Ciucu. In addition, we reveal a hidden relation between our graphs and the hexagonal dungeons introduced by Blum.
combinatorics  Aztec-diamond  domino-tiling  enumeration  to-write-about  to-simulate 
4 weeks ago
[1411.0146] Double Aztec Rectangles
We investigate the connection between lozenge tilings and domino tilings by introducing a new family of regions obtained by attaching two different Aztec rectangles. We prove a simple product formula for the generating functions of the tilings of the new regions, which involves the statistics as in the Aztec diamond theorem (Elkies, Kuperberg, Larsen, and Propp, J. Algebraic Combin. 1992). Moreover, we consider the connection between the generating function and MacMahon's q-enumeration of plane partitions fitting in a given box
combinatorics  enumeration  tiling  domino-tiling  Aztec-diamond  to-write-about  to-simulate 
4 weeks ago
[1403.4493] Enumeration of tilings of quartered Aztec rectangles
We generalize a theorem of W. Jockusch and J. Propp on quartered Aztec diamonds by enumerating the tilings of quartered Aztec rectangles. We use subgraph replacement method to transform the dual graph of a quartered Aztec rectangle to the dual graph of a quartered lozenge hexagon, and then use Lindstr\"{o}m-Gessel-Viennot methodology to find the number of tilings of a quartered lozenge hexagon.
combinatorics  enumeration  Aztec-diamond  domino-tiling  to-write-about  to-simulate 
4 weeks ago
[1711.02818] Enumeration of lozenge tilings of a hexagon with a shamrock missing on the symmetry axis
In their paper about a dual of MacMahon's classical theorem on plane partitions, Ciucu and Krattenthaler proved a closed form product formula for the tiling number of a hexagon with a "shamrock", a union of four adjacent triangles, removed in the center (Proc. Natl. Acad. Sci. USA 2013). Lai later presented a q-enumeration for lozenge tilings of a hexagon with a shamrock removed from the boundary (European J. Combin. 2017). It appears that the above are the only two positions of the shamrock hole that yield nice tiling enumerations. In this paper, we show that in the case of symmetric hexagons, we always have a simple product formula for the number of tilings when removing a shamrock at any position along the symmetry axis. Our result also generalizes Eisenk\"olbl's related work about lozenge tilings of a hexagon with two unit triangles missing on the symmetry axis (Electron. J. Combin. 1999).
tiling  domino-tiling  rather-interesting  combinatorics  enumeration  the-mangle-in-practice  representation  to-write-about  consider:the-convoluted-approach 
4 weeks ago
notes on academic alienation and mass intellectuality | Richard Hall's Space
SEVEN. What Is To Be Done?

The generation of resistances, across an intersectional set of terrains and which acknowledge issues of privilege and powerlessness, require us to move beyond the triptych of private property, commodity exchange and division of labour, to uncover the realities of alienated labour. This is to work against the reconceptualization of academic labour by advocating solidarity inside and outside universities so that academic labour, including that of students, is recognised as having the same fundamental characteristics as other forms of labour and is therefore subject to the same crises of capitalism that are the focus of other social movements. This does not argue for the militant defence of academic labour, but sees it for what it is: wage labour subject to the alienation of the capitalist valorisation process, and to be abolished. Resistance to the processes of work intensification are all the while necessary, but the discovery of new forms of social solidarity and large scale transformation (rather than reformation) of political economy are the end goals.

Here the terrain of personal narratives grounded in alienation, which have yet to reveal their root in alienated labour, open-up the possibility that we might discuss an overcoming of academic competition and overwork. However, developing a counter-hegemonic solidarity requires that such narratives are connected to both a critique of academic labour, and a focus upon social solidarity and the social strike. This situates the exploitation of academic labour against the wider exploitation of paid and unpaid labour in the social factory. Not only must the academic labourer overcome her own competition with other academics to reduce her exploitation, but she must situate this cognitively and emotionally against the abolition of wage-labour more generally.

Of course, this must be attempted in association, so that an alternative intellectual, physical and humane existence might offer new forms of sociability that are grounded in autonomy over time. This requires praxis at the level of society, rather than within specific institutions like universities or inside specific, commodified curricula. As Marx (1844/2014, 115) argues, ‘The resolution of the theoretical contradictions are possible only through practical means, only through the practical energy of man.’
academic-culture  disintermediation-in-action  life-o'-the-mind  political-economy  cultural-dynamics  workalike  to-write-about 
4 weeks ago
On the alienation of academic labour and the possibilities for mass intellectuality | Richard Hall's Space
Abstract: As one response to the secular crisis of capitalism, higher education is being proletarianised. Its academics and students, encumbered by precarious employment, overwhelming debt, and new levels of performance management, are shorn of any autonomy. Increasingly the labour of those academics and students is subsumed and re-engineered for value production, and is prey to the vicissitudes of the twin processes of financialisation and marketization. At the core of understanding the impact of these processes and their relationships to higher education is the alienated labour of the academic, as it defines the sociability of the University. The article examines the role of alienated labour in academic work, and relates this to feelings of hopelessness, in order to ask what might be done differently. The argument centres on the role of mass intellectuality, or socially-useful knowledge and knowing, as a potential moment for overcoming alienated labour.
academic-culture  political-economy  life-o'-the-mind  to-write-about  disintermediation-in-action  capitalism-as-a-bug 
4 weeks ago
China Thinks Strategically and We Don’t | Ian Welsh
Our states are poor. Their ideology, with a few exceptions (smaller countries, all) is to let the rich get richer and have the rich spend money. So instead of NASA leading a huge space program, we have a variety of private companies like SpaceX building technology which a rich state would have created 20 years ago.

China doesn’t think this way. Chinese citizens may not be as rich as the average westerner (though there are plenty of rich Chinese as every world-class city that allows foreigners to buy its real-estate has found out, much to the sorrow of its ordinary citizens), but the state is rich, and the state and the companies it controls and influences are rich.

Most of our companies are not driven by the bottom line. Rather, they are driven by how much money they can create for those who control them. This is often not the case for Chinese companies.
political-economy  world-politics  history  economics  planning  to-watch 
4 weeks ago
slides and notes on academic alienation and mass intellectuality | Richard Hall's Space
I presented at the DMU Institute for Education Futures seminar yesterday. My paper is based on a forthcoming article in a special issue of TripleC on academic labour, and underpins work that I am doing towards a monograph on the alienated academic, for Palgrave Macmillan.
academic-culture  academia  disintermediation-in-action  to-read  to-write-about 
4 weeks ago
[1703.07244] A Hybrid Feasibility Constraints-Guided Search to the Two-Dimensional Bin Packing Problem with Due Dates
The two-dimensional non-oriented bin packing problem with due dates packs a set of rectangular items, which may be rotated by 90 degrees, into identical rectangular bins. The bins have equal processing times. An item's lateness is the difference between its due date and the completion time of its bin. The problem packs all items without overlap as to minimize maximum lateness Lmax.
The paper proposes a tight lower bound that enhances an existing bound on Lmax for 24.07% of the benchmark instances and matches it in 30.87% cases. In addition, it models the problem using mixed integer programming (MIP), and solves small-sized instances exactly using CPLEX. It approximately solves larger-sized instances using a two-stage heuristic. The first stage constructs an initial solution via a first-fit heuristic that applies an iterative constraint programming (CP)-based neighborhood search. The second stage, which is iterative too, approximately solves a series of assignment low-level MIPs that are guided by feasibility constraints. It then enhances the solution via a high-level random local search. The approximate approach improves existing upper bounds by 27.45% on average, and obtains the optimum for 33.93% of the instances. Overall, the exact and approximate approaches identify the optimum for 39.07% cases.
The proposed approach is applicable to complex problems. It applies CP and MIP sequentially, while exploring their advantages, and hybridizes heuristic search with MIP. It embeds a new lookahead strategy that guards against infeasible search directions and constrains the search to improving directions only; thus, differs from traditional lookahead beam searches.
operations-research  planning  algorithms  hard-problems  bin-packing  computational-complexity  to-write-about  rather-interesting  nudge-targets  consider:multiobjective-approach  consider:performance-measures 
4 weeks ago
The Big Picture: Confederate Revisionist History | Public Books
Thus the Confederate revolt was not about states’ rights, it was about protecting the institution of chattel slavery from a remote future threat. Proof of the centrality of slavery to the Southern cause lies in the Confederate Constitution itself, in which the cryptic references to persons “held to Service or Labour” were replaced with explicit references to slaves and Negroes. Article I, Section 9, Paragraph 3, for example, stated that “no bill of attainder, ex post facto law, or law denying or impairing the right of property in negro slaves shall be passed” (italics my own). Apart from these substitutions, the Confederate Constitution was identical to the original US Constitution in all respects.
history  politics  well-summarized  American-cultural-assumptions 
4 weeks ago
Statistical Thinking: Classification vs. Prediction
A special problem with classifiers illustrates an important issue.  Users of machine classifiers know that a highly imbalanced sample with regard to a binary outcome variable Y results in a strange classifier.  For example, if the sample has 1000 diseased patients and 1,000,000 non-diseased patients, the best classifier may classify everyone as non-diseased; you will be correct 0.999 of the time.  For this reason the odd practice of subsampling the controls is used in an attempt to balance the frequencies and get some variation that will lead to sensible looking classifiers (users of regression models would never exclude good data to get an answer).  Then they have to, in some ill-defined way, construct the classifier to make up for biasing the sample.  It is simply the case that a classifier trained to a 1/1000 prevalence situation will not be applicable to a population with a vastly different prevalence.  The classifier would have to be re-trained on the new sample, and the patterns detected may change greatly.  Logistic regression on the other hand elegantly handles this situation by either (1) having as predictors the variables that made the prevalence so low, or (2) recalibrating the intercept (only) for another dataset with much higher prevalence.  Classifiers' extreme dependence on prevalence may be enough to make some researchers always use probability estimators instead. One could go so far as to say that classifiers should not be used at all when there is little variation in the outcome variable, and that only tendencies should be modeled.
philosophy-of-engineering  classification  statistics  machine-learning  prediction  to-write-about  engineering-criticism 
4 weeks ago
radical book club: the Centralized Left | Status 451
Alinsky is kind of a curious cat. The Lefties who are most influenced by his methods often don’t talk about him much, and in many cases Lefties who do talk about him are critical. Here’s the dynamic you need to appreciate to understand this: Lefties, by and large, do not read older Lefty books the way Righties read older Righty books. A lot of Lefty training is done orally, and it’s not always hugely sourced. One Lefty friend of mine, for example, was shocked to realize years later that his college newspaper had literally been doing Maoist criticism/self-criticism sessions. They’d left any mention of Mao himself behind, of course, but they’d kept the technique.

That’s kind of what happened to Saul Alinsky. His methods are everywhere, but if you read organizing books you’ll be surprised how rarely he’s mentioned. Mainstream Lefties are actually baffled by how popular Righties think Alinsky is.
history-of-ideas  politics  organization  organizational-behavior  rather-interesting  citation  cultural-norms 
4 weeks ago
[1711.02724] Algorithms to Approximate Column-Sparse Packing Problems
Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms, to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k-column sparse packing integer programs (Bansal et al., Theory of Computing, 2012) and stochastic k-set packing (Bansal et al., Algorithmica, 2012), and go "half the remaining distance" to optimal for a major integrality-gap conjecture of Furedi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).
integer-programming  matrices  optimization  operations-research  set-theory  hypergraphs  to-write-about  approximation  algorithms 
4 weeks ago
Reprogramming, oscillations and transdifferentiation in epigenetic landscapes | bioRxiv
Waddington's epigenetic landscape provides a phenomenological understanding of the cell differentiation pathways from the pluripotent to mature lineage-committed cell lines. In light of recent successes in the reverse programming process there has been significant interest in quantifying the underlying landscape picture through the mathematics of gene regulatory networks. We investigate the role of time delays arising from multistep chemical reactions and epigenetic rearrangement on the cell differentiation landscape for a realistic two-gene regulatory network, consisting of self-promoting and mutually inhibiting genes. Our work provides the first theoretical basis of the transdifferentiation process in the presence of delays, where one differentiated cell type can transition to another directly without passing through the undifferentiated state. Additionally, the interplay of time-delayed feedback and a time dependent chemical drive leads to long-lived oscillatory states in appropriate parameter regimes. This work emphasizes the important role played by time-delayed feedback loops in gene regulatory circuits and provides a framework for the characterization of epigenetic landscapes.
epigenetics  gene-regulatory-networks  bioinformatics  theoretical-biology  simulation  biological-engineering  rather-interesting  to-write-about 
4 weeks ago
Understanding LSTM Networks -- colah's blog
Humans don’t start their thinking from scratch every second. As you read this essay, you understand each word based on your understanding of previous words. You don’t throw everything away and start thinking from scratch again. Your thoughts have persistence.

Traditional neural networks can’t do this, and it seems like a major shortcoming. For example, imagine you want to classify what kind of event is happening at every point in a movie. It’s unclear how a traditional neural network could use its reasoning about previous events in the film to inform later ones.
recurrent-neural-nets  machine-learning  architecture  dynamical-systems  explainer 
4 weeks ago
[1202.4503] A Critical Look at Decentralized Personal Data Architectures
While the Internet was conceived as a decentralized network, the most widely used web applications today tend toward centralization. Control increasingly rests with centralized service providers who, as a consequence, have also amassed unprecedented amounts of data about the behaviors and personalities of individuals.
Developers, regulators, and consumer advocates have looked to alternative decentralized architectures as the natural response to threats posed by these centralized services. The result has been a great variety of solutions that include personal data stores (PDS), infomediaries, Vendor Relationship Management (VRM) systems, and federated and distributed social networks. And yet, for all these efforts, decentralized personal data architectures have seen little adoption.
This position paper attempts to account for these failures, challenging the accepted wisdom in the web community on the feasibility and desirability of these approaches. We start with a historical discussion of the development of various categories of decentralized personal data architectures. Then we survey the main ideas to illustrate the common themes among these efforts. We tease apart the design characteristics of these systems from the social values that they (are intended to) promote. We use this understanding to point out numerous drawbacks of the decentralization paradigm, some inherent and others incidental. We end with recommendations for designers of these systems for working towards goals that are achievable, but perhaps more limited in scope and ambition.
social-networks  software  user-experience  social-dynamics  decentralization  good-intentions 
4 weeks ago
[1707.05589] On the State of the Art of Evaluation in Neural Language Models
Ongoing innovations in recurrent neural network architectures have provided a steady influx of apparently state-of-the-art results on language modelling benchmarks. However, these have been evaluated using differing code bases and limited computational resources, which represent uncontrolled sources of experimental variation. We reevaluate several popular architectures and regularisation methods with large-scale automatic black-box hyperparameter tuning and arrive at the somewhat surprising conclusion that standard LSTM architectures, when properly regularised, outperform more recent models. We establish a new state of the art on the Penn Treebank and Wikitext-2 corpora, as well as strong baselines on the Hutter Prize dataset.
natural-language-processing  representation  machine-learning  deep-learning  to-write-about 
4 weeks ago
CTK Insights » Blog Archive A Discovery of Hirotaka Ebisui And Thanos Kalogerakis - CTK Insights
Hirotaka Ebisui has found that in the case of the right triangle,






. On informing me of that result, Thanos added an identity for the next layer




That was exciting enough for me to investigate. I can happily and proudly report that, for the next layer,



plane-geometry  rather-interesting  mathematical-recreations  looking-to-see  to-write-about 
4 weeks ago
[1711.00867] The (Un)reliability of saliency methods
Saliency methods aim to explain the predictions of deep neural networks. These methods lack reliability when the explanation is sensitive to factors that do not contribute to the model prediction. We use a simple and common pre-processing step ---adding a constant shift to the input data--- to show that a transformation with no effect on the model can cause numerous methods to incorrectly attribute. In order to guarantee reliability, we posit that methods should fulfill input invariance, the requirement that a saliency method mirror the sensitivity of the model with respect to transformations of the input. We show, through several examples, that saliency methods that do not satisfy input invariance result in misleading attribution.
via:?  machine-learning  looking-to-see  saliency  define-your-terms  algorithms  criticism  to-write-about 
4 weeks ago
Abandoned Footnotes: Utopia and Revolution
(Mostly a disorganized discussion of Richard Stites’ superb Revolutionary Dreams: Utopian Vision and Experimental Life in the Russian Revolution, by someone who is not a historian. Contains half-baked analogies to current events).
literary-criticism  history  to-read  rather-interesting 
4 weeks ago
Feature Visualization
This article focusses on feature visualization. While feature visualization is a powerful tool, actually getting it to work involves a number of details. In this article, we examine the major issues and explore common approaches to solving them. We find that remarkably simple methods can produce high-quality visualizations. Along the way we introduce a few tricks for exploring variation in what neurons react to, how they interact, and how to improve the optimization process.
neural-networks  inverse-problems  generative-art  to-write-about 
4 weeks ago
The New CSS Layout, An Excerpt · An A List Apart Article
As we have seen, flexbox wasn’t designed for grid layouts—but this is where our newest specification is most at home. CSS Grid Layout does exactly what its name suggests: it enables the creation of grid layouts in CSS. This is two-dimensional layout—laying things out as a row and a column at the same time. We’ll go over many more examples of Grid Layout in the rest of this book, but let’s start by seeing how Grid can solve the problem we had with making flexbox display like a grid.
web-design  css  layout  library  to-understand  to-do 
4 weeks ago
[1711.01032] A Simply Exponential Upper Bound on the Maximum Number of Stable Matchings
Stable matching is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley. In this paper, we provide a new upper bound on f(n), the maximum number of stable matchings that a stable matching instance with n men and n women can have. It has been a long-standing open problem to understand the asymptotic behavior of f(n) as n→∞, first posed by Donald Knuth in the 1970s. Until now the best lower bound was approximately 2.28n, and the best upper bound was 2nlogn−O(n). In this paper, we show that for all n, f(n)≤cn for some universal constant c. This matches the lower bound up to the base of the exponent. Our proof is based on a reduction to counting the number of downsets of a family of posets that we call "mixing". The latter might be of independent interest.
combinatorics  open-questions  out-of-the-box  matchings  to-write-about  consider:simulation  consider:heuristics 
4 weeks ago
[1404.1008] Spectral concentration and greedy k-clustering
A popular graph clustering method is to consider the embedding of an input graph into R^k induced by the first k eigenvectors of its Laplacian, and to partition the graph via geometric manipulations on the resulting metric space. Despite the practical success of this methodology, there is limited understanding of several heuristics that follow this framework. We provide theoretical justification for one such natural and computationally efficient variant.
Our result can be summarized as follows. A partition of a graph is called strong if each cluster has small external conductance, and large internal conductance. We present a simple greedy spectral clustering algorithm which returns a partition that is provably close to a suitably strong partition, provided that such a partition exists. A recent result shows that strong partitions exist for graphs with a sufficiently large spectral gap between the k-th and (k+1)-th eigenvalues. Taking this together with our main theorem gives a spectral algorithm which finds a partition close to a strong one for graphs with large enough spectral gap. We also show how this simple greedy algorithm can be implemented in near-linear time for any fixed k and error guarantee. Finally, we evaluate our algorithm on some real-world and synthetic inputs.
clustering  graph-theory  algorithms  rather-interesting  heuristics  performance-measure  to-write-about 
4 weeks ago
Proofs are not only often beautiful but also necessary | Dan McQuillan
I hope you get the idea. When mathematicians seem obsessed with rigor, it is at least in part due to our history of making mistakes, seemingly every time we tried to jump to a conclusion. But perhaps there’s something more. So for that, we end with a quote from William Thurston:

what we are doing is finding ways for people to understand and think about mathematics… what they really want is usually not some collection of of ‘answers’-what they want is understanding.
mathematics  proof  philosophy  to-write-about  consider:representation 
4 weeks ago
Minus Infinity |
Today we’ll talk about some paradoxical things, like the logarithm of zero, and the maximum element of a set of real numbers that doesn’t contain any real numbers at all. More importantly, we’ll see how mathematicians try to wrap their heads around such enigmas.

All today’s logarithms will be base ten logarithms; so the logarithm of 100 is 2 (because 100 is 102) and the logarithm of 1/1000 is −3 (because 1/1000 is 10−3)). The logarithm of 0 would have to be an x that satisfies the equation 10x = 0. Since there’s no such number, we could just say “log 0 is undefined” and walk away, with our consciences clear and our complacency unruffled.
mathematical-recreations  math  representation  to-read  to-write-about 
4 weeks ago
Swine in a Line |
What I hope you take away from this essay is a sense that there’s an interestingly tangled relationship between games, numbers, and the devices we use for representing and manipulating numbers. The abacus was introduced as a way to represent and manipulate numbers for purposes of counting. On the other hand, we can play games with an abacus (the Swine in a Line games) that don’t immediately seem to be about numbers at all, but if we play with those games for long enough, we come to see that underlying the chaos of one configuration giving rise to another, and then another, there is a pattern, and this pattern is most naturally expressed in the language of number.
number-theory  mathematical-recreations  math  pedagogy  ludics  to-write-about  sandpiles  complexology 
4 weeks ago
Prof. Engel’s Marvelously Improbable Machines |
When the path from a simple question to a simple answer leads you through swamps of computation, you can accept that some amount of tromping through swamps is unavoidable in math and in life, or you can think harder and try to find a different route. This is a story of someone who thought harder.

His name is Arthur Engel. Back in the 1970s this German mathematician was in Illinois, teaching probability theory and other topics to middle-school and high-school students. He taught kids in grades 7 and up how to answer questions like “If you roll a fair die, how long on average should you expect to wait until the die shows a three?” The questions are simple, and the answers also tend to be simple: whole numbers, or fractions with fairly small numerators and denominators. You can solve these problems using fraction arithmetic (in the simpler cases) or small systems of linear equations (for more complicated problems), and those are the methods that Engel taught his students up through the end of 1973.
mathematical-recreations  math  computation  to-write-about  see-also:exploding-dots 
4 weeks ago
[1711.02450] Shape Representation by Zippable Ribbons
Shape fabrication from developable parts is the basis for arts such as papercraft and needlework, as well as modern architecture and CAD in general, and it has inspired much research. We observe that the assembly of complex 3D shapes created by existing methods often requires first fabricating many small flat parts and then carefully following instructions to assemble them together. Despite its significance, this error prone and tedious process is generally neglected in the discussion. We propose an approach for shape representation through a single developable part that attaches to itself and requires no assembly instructions. Our inspiration comes from the so-called zipit bags, which are made of a single, long ribbon with a zipper around its boundary. In order to "assemble" the bag, one simply needs to zip up the ribbon. Our method operates in the same fashion, but it can be used to approximate any shape. Given a 3D model, our algorithm produces plans for a single 2D shape that can be laser cut in few parts from flat fabric or paper. We can then attach a zipper along the boundary for quick assembly and disassembly, or apply more traditional approaches, such as gluing and stitching. We show physical and virtual results that demonstrate the capabilities of our method and the ease with which shapes can be assembled.
via:gigasquid  computational-geometry  construction  manufacturability  representation  algorithms  to-write-about  via:twitter  topology 
4 weeks ago
The Global Roots of Exploding Dots - YouTube
Exploding Dots, an exciting approach to teaching K-12 math that over a million schoolchildren learned as part of Global Math Week 2017, is the brainchild of James Tanton. But he didn't create it in a vacuum. In this video I give the backstory, taking you on a world-wide time-traveling tour of mathematical history from the ancient past to the near future.
mathematics  pedagogy  history  rather-interesting  have-watched  to-write-about 
4 weeks ago
[1710.07179] Increasing Labelings, Generalized Promotion, and Rowmotion
We generalize Bender-Knuth promotion on linear extensions to an analogous action on increasing labelings of any finite poset, in which the restrictions on the values of the labels satisfy a natural consistency condition. We give an equivariant bijection between such increasing labelings under this generalized promotion and order ideals in an associated poset under rowmotion. Additionally, we give a criterion for when certain kinds of toggle group actions on order ideals of a finite poset will be conjugate to rowmotion. These results build upon work of O.\ Pechenik with the first two authors in the case of rectangular increasing tableaux and work of N.\ Williams with the second author relating promotion and rowmotion on ranked posets. We apply these results to posets embedded in the Cartesian product of ranked posets and increasing labelings with labels between 1 and q, in which case we obtain new instances of the resonance phenomenon.
partial-ordering  combinatorics  representation  rather-interesting  to-understand  to-write-about  to-simulate  algorithms  consider:fitness  consider:inverse-problem 
4 weeks ago
[1710.06915] MatchPy: A Pattern Matching Library
Pattern matching is a powerful tool for symbolic computations, based on the well-defined theory of term rewriting systems. Application domains include algebraic expressions, abstract syntax trees, and XML and JSON data. Unfortunately, no lightweight implementation of pattern matching as general and flexible as Mathematica exists for Python Mathics,MacroPy,patterns,PyPatt. Therefore, we created the open source module MatchPy which offers similar pattern matching functionality in Python using a novel algorithm which finds matches for large pattern sets more efficiently by exploiting similarities between patterns.
programming  Python  programming-language  pattern-matching  library  to-understand  to-write-about 
4 weeks ago
[1708.08319] Fast Access to Columnar, Hierarchically Nested Data via Code Transformation
Big Data query systems represent data in a columnar format for fast, selective access, and in some cases (e.g. Apache Drill), perform calculations directly on the columnar data without row materialization, avoiding runtime costs.
However, many analysis procedures cannot be easily or efficiently expressed as SQL. In High Energy Physics, the majority of data processing requires nested loops with complex dependencies. When faced with tasks like these, the conventional approach is to convert the columnar data back into an object form, usually with a performance price.
This paper describes a new technique to transform procedural code so that it operates on hierarchically nested, columnar data natively, without row materialization. It can be viewed as a compiler pass on the typed abstract syntax tree, rewriting references to objects as columnar array lookups.
We will also present performance comparisons between transformed code and conventional object-oriented code in a High Energy Physics context.
databases  data-modeling  rather-interesting  algorithms  representation  to-understand  big-data 
4 weeks ago
[1711.00963] The Computational Complexity of Finding Separators in Temporal Graphs
Vertex separators, that is, vertex sets whose deletion disconnects two distinguished vertices in a graph, play a pivotal role in algorithmic graph theory. For instance, the concept of tree decompositions of graphs is tightly connected to the separator concept. For many realistic models of the real world, however, it is necessary to consider graphs whose edge set changes with time. More specifically, the edges are labeled with time stamps. In the literature, these graphs are referred to as temporal graphs, temporal networks, time-varying networks, edge-scheduled networks, etc. While there is an extensive literature on separators in "static" graphs, much less is known for the temporal setting. Building on previous work (e.g., Kempe et al. [STOC '00]), for the first time we systematically investigate the (parameterized) complexity of finding separators in temporal graphs. Doing so, we discover a rich landscape of computationally (fixed-parameter) tractable and intractable cases. In particular, we shed light on the so far seemingly overlooked fact that two frequently used models of temporal separation may lead to quite significant differences in terms of computational complexity. More specifically, considering paths in temporal graphs one may distinguish between strict paths (the time stamps along a path are strictly increasing) and non-strict paths (the time stamps along a path are monotonically non-decreasing). We observe that the corresponding strict case of temporal separators leads to several computationally much easier to handle cases than the non-strict case does.
graph-theory  combinatorics  dynamical-systems  robustness  nudge-targets  heuristics  algorithms  to-write-about 
4 weeks ago
[1602.03311] Efficient weight vectors from pairwise comparison matrices
Pairwise comparison matrices are frequently applied in multi-criteria decision making. A weight vector is called efficient if no other weight vector is at least as good in approximating the elements of the pairwise comparison matrix, and strictly better in at least one position. A weight vector is weakly efficient if the pairwise ratios cannot be improved in all non-diagonal positions. We show that the principal eigenvector is always weakly efficient, but numerical examples show that it can be inefficient. The linear programs proposed test whether a given weight vector is (weakly) efficient, and in case of (strong) inefficiency, an efficient (strongly) dominating weight vector is calculated. The proposed algorithms are implemented in Pairwise Comparison Matrix Calculator, available at pcmc.online.
optimization  numerical-methods  multiobjective-optimization  heuristics  matrices  inference  rather-interesting  try-not-to-do-this  to-write-about  consider:inverse-problem  consider:robustness 
4 weeks ago
[1609.07531] Popular Matchings with Multiple Partners
Our input is a bipartite graph G=(A∪B,E) where each vertex in A∪B has a preference list strictly ranking its neighbors. The vertices in A and in B are called students and courses, respectively. Each student a seeks to be matched to 𝖼𝖺𝗉(a)≥1 courses while each course b seeks 𝖼𝖺𝗉(b)≥1 many students to be matched to it. The Gale-Shapley algorithm computes a pairwise-stable matching (one with no blocking edge) in G in linear time. We consider the problem of computing a popular matching in G -- a matching M is popular if M cannot lose an election to any matching where vertices cast votes for one matching versus another. Our main contribution is to show that a max-size popular matching in G can be computed by the 2-level Gale-Shapley algorithm in linear time. This is an extension of the classical Gale-Shapley algorithm and we prove its correctness via linear programming.
operations-research  combinatorics  optimization  computational-complexity  algorithms  heuristics  nudge-targets  consider:looking-to-see  to-write-about  consider:comparing-to-random 
4 weeks ago
[1710.00104] Small Satellite Constellation Separation using Linear Programming based Differential Drag Commands
We study the optimal control of an arbitrarily large constellation of small satellites operating in low Earth orbit. Simulating the lack of on-board propulsion, we limit our actuation to the use of differential drag maneuvers to make in-plane changes to the satellite orbits. We propose an efficient method to separate a cluster of satellites into a desired constellation shape while respecting actuation constraints and maximizing the operational lifetime of the constellation. By posing the problem as a linear program, we solve for the optimal drag commands for each of the satellites on a daily basis with a shrinking-horizon model predictive control approach. We then apply this control strategy in a nonlinear orbital dynamics simulation with a simple, varying atmospheric density model. We demonstrate the ability to control a cluster of 100+ satellites starting at the same initial conditions in a circular low Earth orbit to form an equally spaced constellation (with a relative angular separation error tolerance of one-tenth a degree). The constellation separation task can be executed in 71 days, a time frame that is competitive for the state-of-the-practice. This method allows us to trade the time required to converge to the desired constellation with a sacrifice in the overall constellation lifetime, measured as the maximum altitude loss experienced by one of the satellites in the group after the separation maneuvers.
nonlinear-dynamics  control-theory  rather-interesting  simulation  nudge-targets  consider:coordination  consider:looking-to-see  to-write-about 
4 weeks ago
« earlier      
academia academic-culture activism advice agent-based agility algorithms amusing ann-arbor approximation architecture archive art artificial-intelligence artificial-life 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 criticism 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 generative-models 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 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

Copy this bookmark: