representation   3597
[1701.06790] Parallel Graph Rewriting with Overlapping Rules
We tackle the problem of simultaneous transformations of networks represented as graphs. Roughly speaking, one may distinguish two kinds of simultaneous or parallel rewrite relations over complex structures such as graphs: (i) those which transform disjoint subgraphs in parallel and hence can be simulated by successive mere sequential and local transformations and (ii) those which transform overlapping subgraphs simultaneously. In the latter situations, parallel transformations cannot be simulated in general by means of successive local rewrite steps. We investigate this last problem in the framework of overlapping graph transformation systems. As parallel transformation of a graph does not produce a graph in general, we propose first some sufficient conditions that ensure the closure of graphs by parallel rewrite relations. Then we mainly introduce and discuss two parallel rewrite relations over graphs. One relation is functional and thus deterministic, the other one is not functional for which we propose sufficient conditions which ensure its confluence.
rewriting-systems  graph-theory  generative-models  representation  dynamical-systems  to-write-about  nudge-targets  consider:looking-to-see  consider:representation  algorithms
3 days ago by Vaguery
[1012.1332] Time-Symmetric Cellular Automata
Together with the concept of reversibility, another relevant physical notion is time-symmetry, which expresses that there is no way of distinguishing between backward and forward time directions. This notion, found in physical theories, has been neglected in the area of discrete dynamical systems. Here we formalize it in the context of cellular automata and establish some basic facts and relations. We also state some open problems that may encourage further research on the topic.
cellular-automata  artificial-life  complexology  computational-complexity  information-theory  representation
3 days ago by Vaguery
[1610.03430] Elliptic Curves in Recreational Number Theory
Several problems which could be thought of as belonging to recreational mathematics are described. They are all such that solutions to the problem depend on finding rational points on elliptic curves. Many of the problems considered lead to the search for points of very large height on the curves, which (as yet) have not been found.
mathematical-recreations  elliptic-curves  review  open-questions  representation  nudge-targets  consider:looking-to-see  to-write-about
3 days ago by Vaguery
[1312.6534] Nonlocal and global dynamics of cellular automata: A theoretical computer arithmetic for real continuous maps
A digit function is presented which provides the ith-digit in base p of any real number x. By means of this function, formulated within -calculus, the local, nonlocal and global dynamical behaviors of cellular automata (CAs) are systematically explored and universal maps are derived for the three levels of description. None of the maps contain any freely adjustable parameter and they are valid for any number of symbols in the alphabet p and neighborhood range ρ. A discrete general method to approximate any real continuous map in the unit interval by a CA on the rational numbers ℚ (Diophantine approximation) is presented. This result leads to establish a correspondence between the qualitative behavior found in bifurcation diagrams of real nonlinear maps and the Wolfram classes of CAs. The method is applied to the logistic map, for which a logistic CA is derived. The period doubling cascade into chaos is interpreted as a sequence of global cellular automata of Wolfram's class 2 leading to Class 3 aperiodic behavior. Class 4 behavior is also found close to the period-3 orbits.
cellular-automata  representation  feature-construction  to-write-about  consider:looking-to-see  consider:generalization
3 days ago by Vaguery
[1505.02547] The $plambda n$ fractal decomposition: Nontrivial partitions of conserved physical quantities
A mathematical method for constructing fractal curves and surfaces, termed the pλn fractal decomposition, is presented. It allows any function to be split into a finite set of fractal discontinuous functions whose sum is equal everywhere to the original function. Thus, the method is specially suited for constructing families of fractal objects arising from a conserved physical quantity, the decomposition yielding an exact partition of the quantity in question. Most prominent classes of examples are provided by Hamiltonians and partition functions of statistical ensembles: By using this method, any such function can be decomposed in the ordinary sum of a specified number of terms (generally fractal functions), the decomposition being both exact and valid everywhere on the domain of the function.
representation  composition  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery
3 days ago by Vaguery
[1107.4120] Generalized packing designs
Generalized t-designs, which form a common generalization of objects such as t-designs, resolvable designs and orthogonal arrays, were defined by Cameron [P.J. Cameron, A generalisation of t-designs, \emph{Discrete Math.}\ {\bf 309} (2009), 4835--4842]. In this paper, we define a related class of combinatorial designs which simultaneously generalize packing designs and packing arrays. We describe the sometimes surprising connections which these generalized designs have with various known classes of combinatorial designs, including Howell designs, partial Latin squares and several classes of triple systems, and also concepts such as resolvability and block colouring of ordinary designs and packings, and orthogonal resolutions and colourings. Moreover, we derive bounds on the size of a generalized packing design and construct optimal generalized packings in certain cases. In particular, we provide methods for constructing maximum generalized packings with t=2 and block size k=3 or 4.
combinatorics  constraint-satisfaction  algorithms  representation  experimental-design  rather-interesting  to-write  nudge-targets  consider:representation
3 days ago by Vaguery
The problem with problematic
but I think it is poisonous to insist, as a general cultural standard, that books pass a fucking purity test in order to be deemed worthy of reading. Because, again--a book that "fails" one test may be the only book that passes another one that you are not even aware of.
books  writing  race  representation  meta
[math/0611293] Descending Dungeons and Iterated Base-Changing
For real numbers a, b> 1, let as a_b denote the result of interpreting a in base b instead of base 10. We define dungeons'' (as opposed to towers'') to be numbers of the form a_b_c_d_..._e, parenthesized either from the bottom upwards (preferred) or from the top downwards. Among other things, we show that the sequences of dungeons with n-th terms 10_11_12_..._(n-1)_n or n_(n-1)_..._12_11_10 grow roughly like 10^{10^{n log log n}}, where the logarithms are to the base 10. We also investigate the behavior as n increases of the sequence a_a_a_..._a, with n a's, parenthesized from the bottom upwards. This converges either to a single number (e.g. to the golden ratio if a = 1.1), to a two-term limit cycle (e.g. if a = 1.05) or else diverges (e.g. if a = frac{100{99).
number-theory  mathematical-recreations  representation  rather-interesting  to-write-about  nudge-targets  consider:representation  consider:feature-discovery  sequences
4 days ago by Vaguery
[1108.5574] Substitutive Arnoux-Rauzy sequences have pure discrete spectrum
We prove that the symbolic dynamical system generated by a purely substitutive Arnoux-Rauzy sequence is measurably conjugate to a toral translation. The proof is based on an explicit construction of a fundamental domain with fractal boundary (a Rauzy fractal) for this toral translation.
dynamical-systems  discrete-mathematics  rewriting-systems  to-understand  strings  representation  to-write-about
6 days ago by Vaguery
[1703.04213] MetaPAD: Meta Pattern Discovery from Massive Text Corpora
Mining textual patterns in news, tweets, papers, and many other kinds of text corpora has been an active theme in text mining and NLP research. Previous studies adopt a dependency parsing-based pattern discovery approach. However, the parsing results lose rich context around entities in the patterns, and the process is costly for a corpus of large scale. In this study, we propose a novel typed textual pattern structure, called meta pattern, which is extended to a frequent, informative, and precise subsequence pattern in certain context. We propose an efficient framework, called MetaPAD, which discovers meta patterns from massive corpora with three techniques: (1) it develops a context-aware segmentation method to carefully determine the boundaries of patterns with a learnt pattern quality assessment function, which avoids costly dependency parsing and generates high-quality patterns; (2) it identifies and groups synonymous meta patterns from multiple facets---their types, contexts, and extractions; and (3) it examines type distributions of entities in the instances extracted by each group of patterns, and looks for appropriate type levels to make discovered patterns precise. Experiments demonstrate that our proposed framework discovers high-quality typed textual patterns efficiently from different genres of massive corpora and facilitates information extraction.
text-mining  natural-language-processing  pattern-discovery  semantics  rather-interesting  algorithms  representation
8 days ago by Vaguery
[1511.02667] An Efficient Multilinear Optimization Framework for Hypergraph Matching
Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows to integrate higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to the assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. This leads to a tensor block coordinate ascent scheme which has the guarantee of providing monotonic ascent in the original matching score function and leads to state-of-the-art performance both in terms of achieved matching score and accuracy. In this paper we show that the lifting step to a fourth-order problem can be avoided yielding a third-order scheme with the same guarantees and performance but being two times faster. Moreover, we introduce a homotopy type method which further improves the performance.
algorithms  numerical-methods  graph-theory  hypergraphs  feature-construction  representation  computer-vision  nudge-targets  consider:looking-to-see  consider:representation  to-write-about
8 days ago by Vaguery
[1601.01944] Nonparametric semi-supervised learning of class proportions
The problem of developing binary classifiers from positive and unlabeled data is often encountered in machine learning. A common requirement in this setting is to approximate posterior probabilities of positive and negative classes for a previously unseen data point. This problem can be decomposed into two steps: (i) the development of accurate predictors that discriminate between positive and unlabeled data, and (ii) the accurate estimation of the prior probabilities of positive and negative examples. In this work we primarily focus on the latter subproblem. We study nonparametric class prior estimation and formulate this problem as an estimation of mixing proportions in two-component mixture models, given a sample from one of the components and another sample from the mixture itself. We show that estimation of mixing proportions is generally ill-defined and propose a canonical form to obtain identifiability while maintaining the flexibility to model any distribution. We use insights from this theory to elucidate the optimization surface of the class priors and propose an algorithm for estimating them. To address the problems of high-dimensional density estimation, we provide practical transformations to low-dimensional spaces that preserve class priors. Finally, we demonstrate the efficacy of our method on univariate and multivariate data.
machine-learning  classification  statistics  representation  algorithms  estimation  probability-theory
8 days ago by Vaguery

Copy this bookmark:

description:

tags: