1,720,976 research outputs found
Experimental study of Pac-Man conditions for learn-ability of discrete linear dynamical systems
Get PDFSubmitted to the Department of Mathematics on May 1, 2019, in partial fulfillment of the requirements for the degree of Master of Applied MathematicsIn this work, we are going to reconstruct parameters of a discrete dynamical system
with a hidden layer, given by a quadruple of matrices (,,,), from system’s past behaviour. First, we reproduced experimentally the well-known result of Hardt et al. that the reconstruction can be made under some conditions, called Pac-Man conditions. Then we demonstrated experimentally that the system approaches the global minimum even if an input is a sequence of i.i.d. random variables with a nongaussian distribution. We also formulated hypotheses beyond Pac-Man conditions that Gradient Descent solves the problem if the operator norm (or alternatively, the spectral radius) of transition matrix is bounded by 1 and obtained the negative result, i.e. a counterexample to those conjectures
Computing a partition function of a generalized pattern-based energy over a semiring
Get PDFValued constraint satisfaction problems with ordered variables (VCSPO) are a
special case of Valued CSPs in which variables are totally ordered and soft
constraints are imposed on tuples of variables that do not violate the order.
We study a restriction of VCSPO, in which soft constraints are imposed on a
segment of adjacent variables and a constraint language consists of
-valued characteristic functions of predicates. This kind of
potentials generalizes the so-called pattern-based potentials, which were
applied in many tasks of structured prediction.
For a constraint language we introduce a closure operator, , and give examples of constraint
languages for which is small. If all predicates in
are cartesian products, we show that the minimization of a generalized
pattern-based potential (or, the computation of its partition function) can be
made in
time, where is a set of variables, is a domain set. If, additionally,
only non-positive weights of constraints are allowed, the complexity of the
minimization task drops to where is the
arity of . For a general language and non-positive
weights, the minimization task can be carried out in time.
We argue that in many natural cases is of moderate
size, though in the worst case can blow up and
depend exponentially on
Multi-layer random features and the approximation power of neural networks
Get PDFA neural architecture with randomly initialized weights, in the infinite
width limit, is equivalent to a Gaussian Random Field whose covariance function
is the so-called Neural Network Gaussian Process kernel (NNGP). We prove that a
reproducing kernel Hilbert space (RKHS) defined by the NNGP contains only
functions that can be approximated by the architecture. To achieve a certain
approximation error the required number of neurons in each layer is defined by
the RKHS norm of the target function. Moreover, the approximation can be
constructed from a supervised dataset by a random multi-layer representation of
an input vector, together with training of the last layer's weights.
For a 2-layer NN and a domain equal to an -dimensional sphere in
, we compare the number of neurons required by Barron's theorem
and by the multi-layer features construction. We show that if eigenvalues of
the integral operator of the NNGP decay slower than where
is an order of an eigenvalue, then our theorem guarantees a more succinct
neural network approximation than Barron's theorem. We also make some
computational experiments to verify our theoretical findings. Our experiments
show that realistic neural networks easily learn target functions even when
both theorems do not give any guarantees.Comment: Accepted to Uncertainty in Artificial Intelligence (UAI) 202
Hybrid VCSPs with Crisp and Valued Conservative Templates
Get PDFA constraint satisfaction problem (CSP) is a problem of computing a homomorphism R -> G between two relational structures, e.g. between two directed graphs.
Analyzing its complexity has been a very fruitful research direction, especially for fixed template CSPs (or, non-uniform CSPs), denoted CSP(G),
in which the right side structure G is fixed and the left side structure R is unconstrained.
Recently, the hybrid setting, written CSP_H(G), where both sides are restricted simultaneously, attracted some attention.
It assumes that R is taken from a class of relational structures H (called the structural restriction) that additionally is closed under inverse homomorphisms. The last property allows to exploit an algebraic machinery that has been developed for fixed template CSPs. The key concept that connects hybrid CSPs with fixed-template CSPs is the so called lifted language. Namely, this is a constraint language G_R that can be constructed from an input R. The tractability of the language G_R for any input R from H is a necessary condition for the tractability of the hybrid problem.
In the first part we investigate templates G for which the latter condition is not only necessary, but also is sufficient. We call such templates G widely tractable. For this purpose, we construct from G a new finite relational structure G' and define a maximal structural restriction H_0 as a class of structures homomorphic to G'.
For the so called strongly BJK templates that probably captures all templates, we prove that wide tractability is equivalent to the tractability of CSP_{H_0}(G).
Our proof is based on the key observation that R is homomorphic to G' if and only if the core of G_R is preserved by a Siggers polymorphism.
Analogous result is shown for conservative valued CSPs
Explorations on chaotic behaviors of Recurrent Neural Networks
No full textSubmitted to the Department of Mathematics on Apr 29, 2019, in partial fulfillment of the
requirements for the degree of Master of Science in Applied MathematicsIn this thesis work we analyzed the dynamics of the Recurrent Neural Network architectures.
We explored the chaotic nature of state-of-the-art Recurrent Neural Networks:
Vanilla Recurrent Network, Recurrent Highway Networks and Structurally
Constrained Recurrent Network. Our experiments showed that they exhibit chaotic
behavior in the absence of input data. We also proposed a way of removing chaos
chaos from Recurrent Neural Networks. Our findings show that initialization of the
weight matrices during the training plays an important role, as initialization with
the matrices whose norm is smaller than one will lead to the non-chaotic behavior
of the Recurrent Neural Networks. The advantage of the non-chaotic cells is stable
dynamics. At the end, we tested our chaos-free version of the Recurrent Highway
Networks (RHN) in a real-world application.
In a sequence-to-sequence modeling experiments, particularly in the language
modeling task, chaos-free version of RHN perform on par with the original version by
using the same hyperparameters
The algebraic structure of the densification and the sparsification tasks for CSPs
Get PDFThe tractability of certain CSPs for dense or sparse instances is known from
the 90s. Recently, the densification and the sparsification of CSPs were
formulated as computational tasks and the systematical study of their
computational complexity was initiated.
We approach this problem by introducing the densification operator, i.e. the
closure operator that, given an instance of a CSP, outputs all constraints that
are satisfied by all of its solutions. According to the Galois theory of
closure operators, any such operator is related to a certain implicational
system (or, a functional dependency) . We are specifically interested
in those classes of fixed-template CSPs, parameterized by constraint languages
, for which there is an implicational system whose size is a
polynomial in the number of variables . We show that in the Boolean case,
such implicational systems exist if and only if is of bounded width.
For such languages, can be computed in log-space or in a logarithmic
time with a polynomial number of processors. Given an implicational system
, the densification task is equivalent to the computation of the
closure of input constraints. The sparsification task is equivalent to the
computation of the minimal key
On the induced problem for fixed-template CSPs
Get PDFThe Constraint Satisfaction Problem (CSP) is a problem of computing a
homomorphism between two relational structures,
where is defined over a domain and is
defined over a domain . In a fixed template CSP, denoted
, the right side structure is
fixed and the left side structure is unconstrained. In the last
two decades it was discovered that the reasons that make fixed template CSPs
polynomially solvable are of algebraic nature, namely, templates that are
tractable should be preserved under certain polymorphisms. From this
perspective the following problem looks natural: given a prespecified finite
set of algebras whose domain is , is it possible to present
the solution set of a given instance of as a
subalgebra of where
?
We study this problem and show that it can be reformulated as an instance of
a certain fixed-template CSP over another template .
We study conditions under which can be reduced to
. This issue is connected with the
so-called CSP with an input prototype, formulated in the following way: given a
homomorphism from to find a
homomorphism from to . We prove that if
contains only tractable algebras, then the latter CSP with an
input prototype is tractable. We also prove that
can be reduced to
if the set , treated as a relation
over , can be expressed as a primitive positive formula over
.Comment: 22 page
JMLR
No full textWe consider Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x1...xn is the sum of terms over intervals [i,j] where each term is non-zero only if the substring xi...xj equals a prespecified pattern α. Such CRFs can be naturally applied to many sequence tagging problems.
We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively O(nL), O(nLℓmax) and O(nLmin{|D|,log(ℓmax+1)}) where L is the combined length of input patterns, ℓmax is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of (Ye et al., 2009) whose complexities are respectively O(nL|D|), O(n|Γ|L2ℓ2max) and O(nL|D|), where |Γ| is the number of input patterns.
In addition, we give an efficient algorithm for sampling. Finally, we consider the case of non-positive weights. (Komodakis & Paragios, 2009) gave an O(nL) algorithm for computing the MAP. We present a modification that has the same worst-case complexity but can beat it in the best case
Inference algorithms for pattern-based CRFs on sequence data
No full textWe consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights
Combining pattern-based CRFs and weighted context-free grammars
No full textWe consider two models for the sequence labeling (tagging) problem. The first one is a Pattern-Based Conditional Random Field (PB), in which the energy of a string (chain labeling) x=x1…xn∈Dn is a sum of terms over intervals [i,j] where each term is non-zero only if the substring xi…xj equals a prespecified word w∈Λ. The second model is a Weighted Context-Free Grammar (WCFG) frequently used for natural language processing. PB and WCFG encode local and non-local interactions respectively, and thus can be viewed as complementary. We propose a Grammatical Pattern-Based CRF model (GPB) that combines the two in a natural way. We argue that it has certain advantages over existing approaches such as the Hybrid model of Benedí and Sanchez that combines N-grams and WCFGs. The focus of this paper is to analyze the complexity of inference tasks in a GPB such as computing MAP. We present a polynomial-time algorithm for general GPBs and a faster version for a special case that we call Interaction Grammars
- …
