Optimal sampling for estimation with constrained resources using a learning automaton-based solution for the nonlinear fractional knapsack problem

While training and estimation for Pattern Recognition (PR) have been extensively studied, the question of achieving these when the resources are both limited and constrained is relatively open. This is the focus of this paper. We consider the problem of allocating limited sampling resources in a “real-time” manner, with the explicit purpose of estimating multiple binomial proportions (the extension of these results to non-binomial proportions is, in our opinion, rather straightforward). More specifically, the user is presented with ‘n’ training sets of data points, S ₁,S ₂,…,S _n , where the set S _i has N _i points drawn from two classes {ω ₁,ω ₂}. A random sample in set S _i belongs to ω ₁ with probability u _i and to ω ₂ with probability 1?u _i , with {u _i }, i=1,2,…n, being the quantities to be learnt. The problem is both interesting and non-trivial because while both n and each N _i are large, the number of samples that can be drawn is bounded by a constant, c. A web-related problem which is based on this model (Snaprud et al., The Accessibility for All Conference, 2003) is intriguing because the sampling resources can only be allocated optimally if the binomial proportions are already known. Further, no non-automaton solution has ever been reported if these proportions are unknown and must be sampled. Using the general LA philosophy as a paradigm to tackle this real-life problem, our scheme improves a current solution in an online manner, through a series of informed guesses which move towards the optimal solution. We solve the problem by first modelling it as a Stochastic Non-linear Fractional Knapsack Problem. We then present a completely new on-line Learning Automata (LA) system, namely, the Hierarchy of Twofold Resource Allocation Automata (H-TRAA), whose primitive component is a Twofold Resource Allocation Automaton (TRAA), both of which are asymptotically optimal. Furthermore, we demonstrate empirically that the H-TRAA provides orders of magnitude faster convergence compared to the Learning Automata Knapsack Game (LAKG) which represents the state-of-the-art. Finally, in contrast to the LAKG, the H-TRAA scales sub-linearly. Based on these results, we believe that the H-TRAA has also tremendous potential to handle demanding real-world applications, particularly those dealing with the world wide web.     

A discrimination algorithm inside λ-β-calculus

A finite set {F₁,…,F_n} of λ-terms is said to be discriminable if, given n arbitrary λ-terms X₁,…,X_n, there exists a λ-term Δ such that: ΔF_i ? X_ifor 1 ? i ? n. In the present paper each finite set of normal combinators which are pairwise non α-η-convertible is proved to be discriminable. Moreover a discrimination algorithm is given.     

On n-Dimensional Sequences. I

Let R be a commutative ring and let n ≥ 1. We study Γ(s), the generating function and Ann(s), the ideal of characteristic polynomials of s, an n-dimensional sequence over R .We express f(X₁,…,X_n) · Γ(s)(X^-1₁,…,X^-1_n) as a partitioned sum. That is, we give (i) a 2ⁿ-fold "border" partition (ii) an explicit expression for the product as a 2ⁿ-fold sum; the support of each summand is contained in precisely one member of the partition. A key summand is βo(f, s), the "border polynomial" of f and s, which is divisible by X₁ … X_n.We say that s is eventually rectilinear if the elimination ideals Ann(s)∩R[X_i] contain an f_i (X_i) for 1 ≤ i ≤ n. In this case, we show that Ann(s) is the ideal quotient ($\text{∑}{}^{\mathrm{n}}{}_{\mathrm{i}}\text{=1(fi) : βo(f, s)/(X}{}_1\text{… X}{}_{\mathrm{n}}\text{)}$).When R and R[[X₁, X₂ ,…, X_n]] are factorial domains (e.g. R a principal ideal domain or F [X₁,…, X_n]), we compute the monic generator γ_i of Ann(s) ∩ R[X_i] from known f_i ϵ Ann(s) ∩ R[X_i] or from a finite number of 1-dimensional linear recurring sequences over R. Over a field F this gives an O($\text{∏}{}_{\mathrm{n}}{}^{\mathrm{i}}\text{=1 δγ}{}^3{}_{\mathrm{i}}$) algorithm to compute an F-basis for Ann(s).     

The Space Complexity of Approximating the Frequency Moments

The frequency moments of a sequence containingm_ielements of typei, 1⩽i⩽n, are the numbersF_k=∑ⁿ_i=1 m^k_i. We consider the space complexity of randomized algorithms that approximate the numbersF_k, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF₀,F₁, andF₂can be approximated in logarithmic space, whereas the approximation ofF_kfork⩾6 requiresn^Ω(1)space. Applications to data bases are mentioned as well.     

An improved version of the Cocke-Younger-Kasami algorithm

The Cocke-Younger-Kasami algorithm (CYK) always requires 0(n³) time and 0(n²) space to recognize a trial sentence ω = w₁w₂…w_n, given an e-free context-free grammar in Chomsky Normal form. The same inductive rule that underlies the CYK algorithm may be used to produce a variant that computes the same information but requires (1) a maximum of 0(n³) time and 0(n²) space, and (2) only 0(s(n)) space and time for an unambiguous grammar, where s(n) is the number of triples (A,i,j) for which a nonterminal symbol A derives w_iw_i+1…w_i+j?1. In this case, time and space consumed are at worst 0(n²).It is shown in addition, for any grammar, that a parse may be obtained from the table left from the recognition algorithm in time 0(s(n)) whether or not the grammar is ambiguous. The same procedure for the CYK algorithm requires time 0(n²).The performance of our variant is quite similar to that of the Earley algorithm except that the Earley algorithm substitutes for s(n), a function which is usually smaller.The model we use of a RAM is strictly identical to the model used in the CYK algorithm. CR categories: 4.20, 5.23, 5.25.     

Reconfiguration of Rings and Meshes in Faulty Hypercubes

In this paper we present schemes for reconfiguration of embedded task graphs in hypercubes. Previous results, which use either fault-tolerant embedding or an automorphism approach, can be expensive in terms of either the required number of spare nodes or reconfiguration time. Using the free dimension concept, we combine the above two approaches in our schemes which can tolerate about n faulty nodes under the worst case while keeping task migration time small. With expansion-2 initial embedding, three distributed reconfiguration schemes are presented in this paper. The first scheme, applied to chains and rings, can tolerate any ƒ ≤ n − 2 faulty nodes in an n-dimensional hypercube. The second and third schemes are applied to meshes or tori. For a mesh or torus of size 2^m₁ 1 ··· 1 2^m_d, the second scheme can tolerate any ƒ ≤ m_i − 1 faulty nodes, where m_i is the largest direction of the mesh and n = m₁ + ··· + m_d + 1. By embedding two copies of meshes or tori in cube, the third scheme can tolerate any ƒ ≤ n − 1 faulty nodes with the dilation of embedding after reconfiguration degraded to 2. The third scheme is quite general and can be applied to any task graph.     

A note on a problem on ω-limit sets of N–dimensional skew-product maps

In 2003, Balibrea et al. stated the problem of finding a skew-product map G on 𝕀³ holding ω _G ={0}×𝕀²=ω _G (x, y, z) for any (x, y, z)∈𝕀³, x≠0. We present a method for constructing skew-product maps F on 𝕀 ⁿ⁺¹ holding ω _F ={0}×𝕀 ⁿ =ω _F (x ₁, x ₂, …, x _n+1), (x ₁, x ₂, …, x _n+1)∈𝕀 ⁿ⁺¹, x ₁≠0.     

Dynamic Matrix Rank with Partial Lookahead

We consider the problem of maintaining information about the rank of a matrix M under changes to its entries. For an n×n matrix M, we show an amortized upper bound of O(n ^ω?1) arithmetic operations per change for this problem, where ω<2.373 is the exponent for matrix multiplication, under the assumption that there is a lookahead of up to Θ(n) locations. That is, we know up to the next Θ(n) locations (i ₁,j ₁),(i ₂,j ₂),…?, whose entries are going to change, in advance; however we do not know the new entries in these locations in advance. We get the new entries in these locations in a dynamic manner. The dynamic matrix rank problem was first studied by Frandsen and Frandsen who showed an upper bound of O(n ^1.575) and a lower bound of Ω(n) for this problem and later Sankowski showed an upper bound of O(n ^1.495) for this problem when allowing randomization and a small probability of error. These algorithms do not assume any lookahead. For the dynamic matrix rank problem with lookahead, Sankowski and Mucha showed a randomized algorithm (with a small probability of error) that is more efficient than these algorithms.     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

Some characterizations of finitely specifiable implicational dependency families

Let r be a relation for the relation scheme R(A₁,A₂,…,A_n); then we define Dom(r) to be Dom_r(A₁)×Dom_r(A₂)×…×Dom_r(A_n), where Dom_r(A_i) for each i is the set of all ith coordinates of tuples of r. A relation s is said to be a substructure of the relation r if and only if Dom(s)∩r = s.The following theorems analogous to Tarski-Fraisse-Vaught's characterizations of universal classes are proved: (i) An implicational dependency family (ID-family) F over the relation scheme R is finitely specifiable if and only if there exists a finite number of relations r₁,r₂,…,r_m for R such that r ∈ F if and only if no r_i is isomorphic to a substructure of r. (ii) F is finitely specifiable if and only if there exists a natural number k such that r ∈ F whenever F contains all substructures of r with at most k elements.We shall use these characterizations to obtain a new proof for Hull's (1984) characterization of finitely specifiable ID-families.     

Characterization of normal forms possessing inverse in the λ-β-η-calculus

The aim of this paper is to generalize a result given by Curry and Feys, who have shown that the only regular combinators possessing inverse in the λ-β-η-calculus are the permutators, whose definition is p=λzλx₁…λx_n(zx_i1…x_in) for n?0 where i₁,…, i_r is a permutation of 1,…, n. Here we extend this characterization to the set of normal forms, showing that the only normal forms possessing inverse in the λ-βη-calculus are the “hereditarily finite permutators” (h.f.p.), whose recursive definition is: if n?0, P_j (1?j?n) are h.f.p. and i₁,…,i_n is a permutation of 1,…, n, then the normal form of P = λzλx₁…λx_n(z(P₁x_i1))… (P_nin) is an h.f.p.     

Succinct 2D Dictionary Matching

The dictionary matching problem seeks all locations in a given text that match any of the patterns in a given dictionary. Efficient algorithms for dictionary matching scan the text once, searching for all patterns simultaneously. Existing algorithms that solve the 2-dimensional dictionary matching problem all require working space proportional to the size of the dictionary. This paper presents the first efficient 2-dimensional dictionary matching algorithm that operates in small space. Given d patterns, D={P ₁,…,P _d }, each of size m×m, and a text T of size n×n, our algorithm finds all occurrences of P _i , 1≤i≤d, in T. The preprocessing of the dictionary forms a compressed self-index of the patterns, after which the original dictionary may be discarded. Our algorithm uses O(dmlogdm) extra bits of space. The time complexity of our algorithm is close to linear, O(dm ²+n ² τlogσ), where τ is the time it takes to access a character in the compressed self-index and σ is the size of the alphabet. Using recent results τ is at most sub-logarithmic.     

A generalization of the Schützenberger product of finite monoids

For each n?1, an n-ary product ? on finite monoids is constructed. This product has the following property: Let Σ be a finite alphabet and Σ¹ the free monoid generated by Σ. For i = 1, …,n, let A_i be a recognizable subset of Σ¹, M(A_i) the syntactic monoid of A_n and M(A₁?A_n) the syntactic monoid of the concatenation product A₁?A_n. Then M(A₁?A_n)< ? (M(A₁),…,M(A_n)). The case n = 2 was studied by Schützenberger. As an application of the generalized product, I prove the theorem of Brzozowski and Knast that the dot-depth hierarchy of star-free sets is infinite.     

A Note on Optimal Time Broadcast in Faulty Hypercubes

This note describes an algorithm for broadcasting a message on the n-dimensional hypercube in optimal time (n time units) and optimal communication (2ⁿ − 1 messages) in the presence of up to n − 2 arbitrary node or edge faults, assuming the set of faults is known to all nodes of the hypercube.     

Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs

Motivated by applications in batch scheduling of jobs in manufacturing systems and distributed computing, we study two related problems. Given is a set of jobs {J ₁,…,J _n }, where J _j has a processing time p _j , and an undirected intersection graph G=({1,…,n},E), with an edge (i,j) whenever the pair of jobs J _i and J _j cannot be processed in the same batch. We are to schedule the jobs in batches, where each batch completes its processing when the last job in the batch completes execution. The goal is to minimize the sum of job completion times. Our two problems differ in the definition of completion time of a job within a given batch. In the first variant, a job completes its execution when its batch is completed, whereas in the second variant, a job completes execution when its own processing is completed. For the first variant, we show that an adaptation of the greedy set cover algorithm gives a 4-approximation for perfect graphs. For the second variant, we give new or improved approximations for a number of different classes of graphs. The algorithms are of widely different genres (LP, greedy, subgraph covering), yet they curiously share a common feature in their use of randomized geometric partitioning.     

Lower Bounds on Performance of Metric Tree Indexing Schemes for Exact Similarity Search in High Dimensions

Within a mathematically rigorous model, we analyse the curse of dimensionality for deterministic exact similarity search in the context of popular indexing schemes: metric trees. The datasets X are sampled randomly from a domain Ω, equipped with a distance, ρ, and an underlying probability distribution, μ. While performing an asymptotic analysis, we send the intrinsic dimension d of Ω to infinity, and assume that the size of a dataset, n, grows superpolynomially yet subexponentially in d. Exact similarity search refers to finding the nearest neighbour in the dataset X to a query point ω∈Ω, where the query points are subject to the same probability distribution μ as datapoints. Let denote a class of all 1-Lipschitz functions on Ω that can be used as decision functions in constructing a hierarchical metric tree indexing scheme. Suppose the VC dimension of the class of all sets {ω:f(ω)≥a}, a∈? is o(n ^1/4/log² n). (In view of a 1995 result of Goldberg and Jerrum, even a stronger complexity assumption d ^O(1) is reasonable.) We deduce the Ω(n ^1/4) lower bound on the expected average case performance of hierarchical metric-tree based indexing schemes for exact similarity search in (Ω,X). In paricular, this bound is superpolynomial in d.     

Time-series decomposition and forecasting

Any stationary time-series can be decomposed by means of an optimization operator, called the ζ-optimator, into several components (the time-series){Y _t ⁱ}, i =1,2,…, p, such that the first component {V _t ⁱ} t = 1,2,…,v is a smooth process having a larger autocorrelation in comparison with the original process {Y _t}, i.e. ρ_vi > ρ_y. Usually only a few such components are sufficient for approximating the time-series with good accuracy. The ζ-optimator involves a shape parameter a, so the decomposition is unique provided that a. is fixed. Since the component {V _t ¹} involves much of the useful information it can be used for computing predictors for control purposes. Thus, given the observations Y_v, Y_v-1, Y_v-2,…, a predictor of Y_v+1 is ρ_vi V _v ¹ (q) where, V_v ¹(q) = qY^v + q(1-q)² Y_v-2, …, the weights q(1-q)^r, r=0,1,2,…, decreasing rapidly as q = q(α) ε (0,1) Further, one may choose q rather than choosing α, since q(α) is a one-one mapping. Once q is fixed, the predictor ρ_v1 V _v ¹(q) is obtained in a straightforward way by using the formula above. It is shown that ρ_v1 V _v ¹(q) converges to the best predictor as α → 0. Some examples are worked out, illustrating both the decomposition and the forecasting procedures.     

Two theorems concerning recognizable N-subsets of σ1

It is proved that the family of recognizable N-subsets is not closed under the operation sup, and that there exists even a DOL length sequence x₀, x₁, … such that, for any k,x_i ? x_i+1 ? … ? x_i+k holds true for some i and the cardinality of the set {n ∈ N|x_n > x_n+1} is infinite.     

On the time-space tradeoff for sorting with linear queries

Extending a result of Borodin et al. [1], we show that any branching program using linear queries “∑_iλ_ix_i:c” to sort n numbers x₁, x₂,…,x_n must satisfy the time-space tradeoff relation $\text{TS = Ω(n}{}^2\text{)}$. The same relation is also shown to be true for branching programs that uses queries “min R = ?” where R is any subset of {x₁, x₂,…,x_n}.