The problem of searching for an unknown object occurs in important applications ranging from security, medicine and defense. Sensors with the capability to process information rapidly require adaptive algorithms to co...
详细信息
ISBN:
(纸本)9781479978878
The problem of searching for an unknown object occurs in important applications ranging from security, medicine and defense. Sensors with the capability to process information rapidly require adaptive algorithms to control their search in response to noisy observations. In this paper, we discuss a class of dynamic, adaptive search problems, and formulate the resulting sensor control problems as stochastic control problems with imperfect information. The structure of these problems, with objective functions related to information entropy, allows for a complete characterization of the optimal strategies and the optimal cost. We study problems that involve both individual sensors as well as multiple sensors. We provide a constructive algorithm for determining optimal policies in real time based on convex optimization. We also show that, under symmetry conditions on the observation errors in the sensors, the optimal policies have a simple characterization that lead to a closed-form solution for the convex optimization problem. We illustrate the results with simulations including two sensors searching for a single object.
Suffix tree (and the closely related suffix array) are fundamental structures capturing all substrings of a given text essentially by storing all its suffixes in the lexicographical order. In some applications, such a...
详细信息
ISBN:
(纸本)9781510836358
Suffix tree (and the closely related suffix array) are fundamental structures capturing all substrings of a given text essentially by storing all its suffixes in the lexicographical order. In some applications, such as sparse text indexing, we work with a subset of b interesting suffixes, which are stored in the so-called sparse suffix tree. Because the size of this structure is Θ(b), it is natural to seek a construction algorithm using only O(b) words of space assuming read-only random access to the text. We design a linear-time Monte Carlo algorithm for this problem, hence resolving an open question explicitly stated by Bille et al. [TALG 2016]. The best previously known algorithm by I et al. [STACS 2014] works in O(n log b) time. As opposed to previous solutions, which were based on the divide-and-conquer paradigm, our solution proceeds in n/b rounds. In the r-th round, we consider all suffixes starting at positions congruent to r modulo n/b. By maintaining rolling hashes, we can lexicographically sort all interesting suffixes starting at such positions, and then we can merge them with the already considered suffixes. For efficient merging, we also need to answer LCE queries efficiently (and in small space). By plugging in the structure of Bille et al. [CPM 2015] we obtain O(n + b log b) time complexity. We improve this structure by a recursive application of the so-called difference covers, which then implies a linear-time sparse suffix tree construction algorithm. We complement our Monte Carlo algorithm with a deterministic verification procedure. The verification takes O(n {the square root of}(log b)) time, which improves upon the bound of O(n log b) obtained by I et al. [STACS 2014]. This is obtained by first observing that the pruning done inside the previous solution has a rather clean description using the notion of graph spanners with small multiplicative stretch. Then, we are able to decrease the verification time by applying difference covers twice. Com
The problem of finding finite state models of systems with quantized inputs and outputs has received much deserved attention. In particular, a notion of ρ/μ approximation was proposed and shown to be relevant to the...
详细信息
ISBN:
(纸本)9781467320658
The problem of finding finite state models of systems with quantized inputs and outputs has received much deserved attention. In particular, a notion of ρ/μ approximation was proposed and shown to be relevant to the problem of control synthesis. In this paper, we revisit a recently developed constructive algorithm for generating ρ/μ approximations for a class of systems, and we propose and analyze several algorithms for improving the computational efficiency and memory requirements of the construction. We demonstrate the use of this approach for synthesizing certified-by-design controllers for a simple illustrative example with reachability type specifications.
In this paper, we make analysis and knowledge extraction on the process parameters of affecting stock market using Rough Lattice model. In order to forecast the risk of stock market, we utilize stock quotation data to...
详细信息
ISBN:
(纸本)9781424480333
In this paper, we make analysis and knowledge extraction on the process parameters of affecting stock market using Rough Lattice model. In order to forecast the risk of stock market, we utilize stock quotation data to mine rules according to CM_CARCL (Compressed Matrix Based Construction algorithm of Rough Concept Lattice).The experiment shows that these rules mined from stock quotation can reflect the influence of different factors on stock quotation.
The high school timetabling problem (HSTP) is considered as an NP-Complete problem as the optimal solution for it, is still not discovered by any algorithm. Generally, NP-Complete problem was solved firstly by constru...
详细信息
ISBN:
(数字)9781728150338
ISBN:
(纸本)9781728150345
The high school timetabling problem (HSTP) is considered as an NP-Complete problem as the optimal solution for it, is still not discovered by any algorithm. Generally, NP-Complete problem was solved firstly by constructing the initial solution, in the construction phase. The initial solution will be improvised in the improvisation phase. KHE is an algorithm that generates initial solution of HSTP. The layer sorting procedure in KHE is based on a certain priority. For every two layers, the layers will be ranked based on the highest value of duration. If both layers have equal value of duration, the layer with the highest value of demand will be at a higher rank. If both layers have equal value of demand. The layer will be arranged according to the index value of the layer. These sorting criteria use the layer properties independently which causes non-good results after the time-assignment phase. Therefore, this study proposed a mathematical model based on the Markov Chain Model for the sorting procedure that combines the layer properties in a formula. The proposed model was executed with 40 datasets of XHSTT2014, and it shows better results on 25 datasets of XHSTT2014 compared to the KHE algorithm. The mathematical model based on Markov Chain proposed in this study is able to improvise the original sorting of KHE.
Nonlinear Fisher Discriminant Analysis for binomial problems can be converted into a Linear-In-The-Parameters classifier model by introducing a least-squares cost function. However, the complexity of the classifier sc...
详细信息
ISBN:
(纸本)9781424477456
Nonlinear Fisher Discriminant Analysis for binomial problems can be converted into a Linear-In-The-Parameters classifier model by introducing a least-squares cost function. However, the complexity of the classifier scales with the number of training samples, which makes it difficult to use on large data sets. A popular solution is to adopt a sub-model selection approach, such as Orthogonal Least Squares (OLS) or the Fast Recursive algorithm (FRA), to produce a compact classifier with accurate parameters. The problem is that these methods need additional subjective choice of selection termination criterion, and inappropriate choice of this criterion may lead to an over-fitting classifier. Further, training data with large noise may even deteriorate the performance. This paper proposes a fast automatic forward algorithm for constructing a parsimonious descriptor of the nonlinear discriminant function, thus both the subjective choice of the termination criterion and the over-fitting problem due to noisy data can be avoided. This is achieved by an effective integration of the Bayesian regularisation technique, the Leave-One-Out (LOO) cross-validation criterion and the FRA algorithm. Experimental results are included to confirm the efficacy and superiority of the proposed algorithm on both artificial and real world data sets.
暂无评论