Inner Product Space and Concept Classes Induced by Bayesian Networks

Bayesian networks have become one of the major models used for statistical inference. In this paper we discuss the properties of the inner product spaces and concept class induced by some special Bayesian networks and the problem whether there exists a Bayesian network such that lower bound on dimensional inner product space just is some positive integer. We focus on two-label classification tasks over the Boolean domain. As main results we show that lower bound on the dimension of the inner product space induced by a class of Bayesian networks without v-structures is where m _i denotes the number of parents for ith variable. As the variable’s number of Bayesian network is n≤5, we also show that for each integer m∈[n+1,2 ⁿ −1] there is a Bayesian network such that VC dimension of concept class and lower bound on dimensional inner product space induced by all are m. This work was supported by National Natural Science Foundation of China (60574075).     

Constructions of p-ary Quadratic Bent Functions

Bent functions have many applications in the fields of coding theory, communications and cryptography. This paper studies the constructions of bent functions having the form for odd n and for even n, over the finite field of odd characteristic p, where . Based on the irreducibility of some polynomials on , we focus on characterizing the bent functions for n=p ^v q ^r and n=2p ^v q ^r , where is an odd prime and p a primitive root modulo q ². Moreover, the enumerations of those functions are also considered. Partially supported by the NSF of China under Grants No. 60603012 and No. 60573053.     

Diophantine exponents for mildly restricted approximation

We are studying the Diophantine exponent μ _n,l defined for integers 1≤l<n and a vector α∈ℝ ⁿ by letting

On Some Properties of Randomly Indexed Sequences of Random Elements

Let be a probability space with a nonatomic measure P and let (S,ρ) be a separable complete metric space. Let {N _n ,n≥1} be an arbitrary sequence of positive-integer valued random variables. Let {F _k ,k≥1} be a family of probability laws and let X be some random element defined on and taking values in (S,ρ). In this paper we present necessary and sufficient conditions under which one can construct an array of random elements {X _n,k ,n,k≥1} defined on the same probability space and taking values in (S,ρ), and such that , and moreover as  n→∞. Furthermore, we consider the speed of convergence to X as n→∞.      

Greedy Bases for Besov Spaces

We prove that the Banach space (?_n=1^￥l_pⁿ)_lq(\bigoplus_{n=1}^{\infty}\ell_{p}^{n})_{\ell_{q}}, which is isomorphic to certain Besov spaces, has a greedy basis whenever 1≤p≤∞ and 1<q<∞. Furthermore, the Banach spaces (?_n=1^￥l_pⁿ)_l1(\bigoplus_{n=1}^{\infty}\ell _{p}^{n})_{\ell_{1}}, with 1<p≤∞, and (?_n=1^￥l_pⁿ)_c0(\bigoplus_{n=1}^{\infty}\ell_{p}^{n})_{c_{0}}, with 1≤p<∞, do not have a greedy basis. We prove as well that the space (?_n=1^￥l_pⁿ)_lq(\bigoplus_{n=1}^{\infty}\ell _{p}^{n})_{\ell_{q}} has a 1-greedy basis if and only if 1≤p=q≤∞.     

Graph von Neumann Algebras

In this paper, we will define a graph von Neumann algebra over a fixed von Neumann algebra M, where G is a countable directed graph, by a crossed product algebra = M × _α , where is the graph groupoid of G and α is the graph-representation. After defining a certain conditional expectation from onto its M-diagonal subalgebra we can see that this crossed product algebra is *-isomorphic to an amalgamated free product where = vN(M × _α where is the subset of consisting of all reduced words in {e, e ^–1} and M × _α is a W ^*-subalgebra of as a new graph von Neumann algebra induced by a graph G _e . Also, we will show that, as a Banach space, a graph von Neumann algebra is isomorphic to a Banach space ⊕ where is a certain subset of the set E(G)* of all words in the edge set E(G) of G. The author really appreciates to Prof F. Radulescu and Prof P. Jorgensen for the valuable discussion and kind advice. Also, he appreciates all supports from St. Ambrose Univ.. In particular, he thanks to Prof T. Anderson and Prof V. Vega for the useful conversations and suggestions.     

Freeknot splines approximation of Sobolev-type classes of <Emphasis Type="Italic">s</Emphasis>-monotone functions

Let I be a finite interval, s ∈ ℕ₀, and r,ν,n ∈ ℕ. Given a set M, of functions defined on I, denote by M the subset of all functions y ∈ M such that the s-difference is nonnegative on I, ∀τ > 0. Further, denote by the Sobolev class of functions x on I with the seminorm . Also denote by Σ _ν,n , the manifold of all piecewise polynomials of order ν and with n – 1 knots in I. If ν ≥ max {r,s}, 1 ≤ p,q ≤ ∞, and (r,p,q) ≠ (1,1,∞), then we give exact orders of the best unconstrained approximation and of the best s-monotonicity preserving approximation . Part of this work was done while the first author visited Tel Aviv University in May 2003 and in March 2004.     

On some homotopical and homological properties of monoid presentations

If a monoid S is given by some finite complete presentation ℘, we construct inductively a chain of CW-complexes

Comparison of exact constants in Kolmogorov-type inequalities for periodic and nonperiodic functions of many variables

We investigate the correlation between the constants K(ℝⁿ) and , where

Score sets in oriented 3-partite graphs

Let D(U, V, W) be an oriented 3-partite graph with |U|=p, |V|=q and |W|= r. For any vertex x in D(U, V, W), let d x and d-x be the outdegree and indegree of x respectively. Define aui (or simply ai) = q r d ui - d-ui, bvj(or simply bj) = p r d vj - d-vj and Cwk (or simply ck) = p q d wk - d-wk as the scores of ui in U, vj in V and wk in Wrespectively. The set A of distinct scores of the vertices of D(U, V, W) is called its score set. In this paper, we prove that if a1 is a non-negative integer, ai(2≤i≤n - 1) are even positive integers and an is any positive integer, then for n≥3, there exists an oriented 3-partite graph with the score set A = {a1,2∑i=1 ai,…,n∑i=1 ai}, except when A = {0,2,3}. Some more results for score sets in oriented 3-partite graphs are obtained.     

Optimisation of Measures on a Hyperfinite Adapted Probability Space

The minimisation problem for a functional is considered, where is an ℝ ⁿ -valued stochastic process, defined on some filtered probability space , and P is an admissible probability measure in the sense that it obeys (1) some uniform equivalence condition with respect to the given measure ℙ on Γ, and (2) a finite number (possibly zero) of arbitrarily given other conditions that require the expectation (with respect to P) of some continuous bounded function φ of , for t ₁,…,t _k ∈[0,1], to lie within some closed set. We assume that u can be formulated through finite compositions of conditional expectations and bounded continuous functions. Under the assumption of |φ| being uniformly bounded from below and some condition on the dimension of , the existence of a solution on hyperfinite adapted probability spaces, as well as its minimality among admissible measures on any other adapted probability space, is proven. Also, a coarseness result for the Loeb operation is established. The main result of this paper, however, is a “standard result”: It does not include any reference to nonstandard analysis and can be perfectly understood without any familiarity with nonstandard analysis.      

Canonical Representations on Lobachevsky Spaces: An Interaction with an Overalgebra

We define canonical representations R _λ , , for the Lobachevsky space ℒ=G/K of dimension n−1 where G=SO₀(n−1,1), K=SO(n−1), as the restriction to G of maximal degenerate series representations of the overgroup . We determine explicitly the interaction of Lie operators of with operators intertwining canonical representations and representations of G associated with a cone. Supported by the Russian Foundation for Basic Research: grants No. 05-01-00074a and No. 05-01-00001a, the Netherlands Organization for Scientific Research (NWO): grant 047-017-015, the Scientific Program “Devel. Sci. Potent. High. School”: project RNP.2.1.1.351 and Templan No. 1.2.02.     

Almost sure convergence of sample range

Let X ₁, X ₂, ... be i.i.d. random variables. The sample range is R _n = max {X _i , 1 ≤ i ≤ n} − min {X _i , 1 ≤ i ≤ n}. If for a non-degenerate distribution G and some sequences (α _k ), (β _k ) then we have

A class of problems for which cyclic relaxation converges linearly

The method of cyclic relaxation for the minimization of a function depending on several variables cyclically updates the value of each of the variables to its optimum subject to the condition that the remaining variables are fixed. We present a simple and transparent proof for the fact that cyclic relaxation converges linearly to an optimum solution when applied to the minimization of functions of the form for a _i,j ,b _i ,c _i ∈ℝ_≥0 with max {min {b ₁,b ₂,…,b _n },min {c ₁,c ₂,…,c _n }}>0 over the n-dimensional interval [l ₁,u ₁]×[l ₂,u ₂]×⋅⋅⋅×[l _n ,u _n ] with 0<l _i <u _i for 1≤i≤n. Our result generalizes several convergence results that have been observed for algorithms applied to gate- and wire-sizing problems that arise in chip design.     

On vector space partitions and uniformly resolvable designs

Let V _n (q) denote a vector space of dimension n over the field with q elements. A set of subspaces of V _n (q) is a partition of V _n (q) if every nonzero vector in V _n (q) is contained in exactly one subspace in . A uniformly resolvable design is a pairwise balanced design whose blocks can be resolved in such a way that all blocks in a given parallel class have the same size. A partition of V _n (q) containing a _i subspaces of dimension n _i for 1 ≤ i ≤ k induces a uniformly resolvable design on q ⁿ points with a _i parallel classes with block size , 1 ≤ i ≤ k, and also corresponds to a factorization of the complete graph into -factors, 1 ≤ i ≤ k. We present some sufficient and some necessary conditions for the existence of certain vector space partitions. For the partitions that are shown to exist, we give the corresponding uniformly resolvable designs. We also show that there exist uniformly resolvable designs on q ⁿ points where corresponding partitions of V _n (q) do not exist. A. D. Blinco—Part of this research was done while the author was visiting Illinois State University.     

Constant-Sign Solutions for Systems of Fredholm and Volterra Integral Equations: The Singular Case

We consider the system of Fredholm integral equations

Iterated Logarithm Law for Anticipating Stochastic Differential Equations

We prove a functional law of iterated logarithm for the following kind of anticipating stochastic differential equations

Non-commutative Clarkson Inequalities for n-Tuples of Operators

Let A ₀, ... , A _n−1 be operators on a separable complex Hilbert space , and let α₀,..., α _n−1 be positive real numbers such that 1. We prove that for every unitarily invariant norm,

Shape preserving widths of Sobolev-type classes ofs-monotone functions on a finite interval

LetI be a finite interval andr ∈ ℕ. Denote by △ ₊ ^s L _q the subset of all functionsy ∈L _q such that thes-difference △ _T ^s y(·) is nonnegative onI, ∀τ>0. Further, denote by △ ₊ ^s W _p ^r the class of functionsx onI with the seminorm ‖x ^(r) ‖L _p ≤1, such that △ _T ^s x≥0, τ > 0, τ>0. Fors=3,…,r+1, we obtain two-sided estimates of the shape preserving widths , whereM ⁿ is the set of all linear manifoldsM ⁿ inL _q , dimM ⁿ ≤n, such thatM ⁿ ⋂△ ₊ ^s L _q ≠ 0. Part of this work was done while the first author visited Tel Aviv University in 2001 and part of it while the second author was a member of the Industrial Mathematics Institute (IMI), University of South Carolina.