OpenRaiser/Intern-Atlas huggingface dataset:
An Introductory Study on Time Series Modeling and Forecasting
Venue: arXiv cs.LG 2013
Year: 2013

Time series modeling and forecasting has fundamental importance to various practical domains. Thus a lot of active research works is going on in this subject during several years. Many important models have been proposed in literature for improving the accuracy and effectiveness of time series forecasting. The aim of this dissertation work is to present a concise description of some popular time series forecasting models used in practice, with their salient features. In this thesis, we have described three important classes of time series models, viz. the stochastic, neural networks and SVM based models, together with their inherent forecasting strengths and weaknesses. We have also discussed about the basic issues related to time series modeling, such as stationarity, parsimony, overfitting, etc. Our discussion about different time series models is supported by giving the experimental forecast results, performed on six real time series datasets. While fitting a model to a dataset, special care is taken to select the most parsimonious one. To evaluate forecast accuracy as well as to compare among different models fitted to a time series, we have used the five performance measures, viz. MSE, MAD, RMSE, MAPE and Theil's U-statistics. For each of the six datasets, we have shown the obtained forecast diagram which graphically depicts the closeness between the original and forecasted observations. To have authenticity as well as clarity in our discussion about time series modeling and forecasting, we have taken the help of various published research works from reputed journals and some standard books.
PSO based Neural Networks vs. Traditional Statistical Models for Seasonal Time Series Forecasting
Venue: arXiv cs.NE 2013
Year: 2013

Seasonality is a distinctive characteristic which is often observed in many practical time series. Artificial Neural Networks (ANNs) are a class of promising models for efficiently recognizing and forecasting seasonal patterns. In this paper, the Particle Swarm Optimization (PSO) approach is used to enhance the forecasting strengths of feedforward ANN (FANN) as well as Elman ANN (EANN) models for seasonal data. Three widely popular versions of the basic PSO algorithm, viz. Trelea-I, Trelea-II and Clerc-Type1 are considered here. The empirical analysis is conducted on three real-world seasonal time series. Results clearly show that each version of the PSO algorithm achieves notably better forecasting accuracies than the standard Backpropagation (BP) training method for both FANN and EANN models. The neural network forecasting results are also compared with those from the three traditional statistical models, viz. Seasonal Autoregressive Integrated Moving Average (SARIMA), Holt-Winters (HW) and Support Vector Machine (SVM). The comparison demonstrates that both PSO and BP based neural networks outperform SARIMA, HW and SVM models for all three time series datasets. The forecasting performances of ANNs are further improved through combining the outputs from the three PSO based models.
The Unified Segment Tree and its Application to the Rectangle Intersection Problem
Venue: arXiv cs.CG 2013
Year: 2013

In this paper we introduce a variation on the multidimensional segment tree, formed by unifying different interpretations of the dimensionalities of the data structure. We give some new definitions to previously well-defined concepts that arise naturally in this variation, and we show some properties concerning the relationships between the nodes, and the regions those nodes represent. We think these properties will enable the data to be utilized in new situations, beyond those previously studied. As an example, we show that the data structure can be used to solve the Rectangle Intersection Problem in a more straightforward and natural way than had be done in the past.
Decentralized set-valued state estimation and prediction for hybrid systems: A symbolic approach
Venue: arXiv cs.SY 2013
Year: 2013

A symbolic approach to decentralized set-valued state estimation and prediction for systems that admit a hybrid state machine representations is proposed. The decentralized computational scheme represents a conj unction of a finite number of distributed state machines, which are specified by an appropriate decomposition of the external signal space. It aims at a distribution of computational tasks into smaller ones, allocated to individual distributed state machines, leading to a potentially significant reduction in the overall space/time computational complexity. We show that, in general, such a scheme outerapproximates the state set estimates and predictions of the original monolithic state machine. By utilizing structural properties of the transition relation of the latter, in a next step, we propose constructive decomposition algorithms for a recovery of the exact state set outcomes.
Laplace's Method Approximations for Probabilistic Inference in Belief Networks with Continuous Variables
Venue: arXiv cs.AI 2013
Year: 2013

Laplace's method, a family of asymptotic methods used to approximate integrals, is presented as a potential candidate for the tool box of techniques used for knowledge acquisition and probabilistic inference in belief networks with continuous variables. This technique approximates posterior moments and marginal posterior distributions with reasonable accuracy [errors are O(n^-2) for posterior means] in many interesting cases. The method also seems promising for computing approximations for Bayes factors for use in the context of model selection, model uncertainty and mixtures of pdfs. The limitations, regularity conditions and computational difficulties for the implementation of Laplace's method are comparable to those associated with the methods of maximum likelihood and posterior mode analysis.
Generating New Beliefs From Old
Venue: arXiv cs.AI 2013
Year: 2013

In previous work [BGHK92, BGHK93], we have studied the random-worlds approach -- a particular (and quite powerful) method for generating degrees of belief (i.e., subjective probabilities) from a knowledge base consisting of objective (first-order, statistical, and default) information. But allowing a knowledge base to contain only objective information is sometimes limiting. We occasionally wish to include information about degrees of belief in the knowledge base as well, because there are contexts in which old beliefs represent important information that should influence new beliefs. In this paper, we describe three quite general techniques for extending a method that generates degrees of belief from objective information to one that can make use of degrees of belief as well. All of our techniques are bloused on well-known approaches, such as cross-entropy. We discuss general connections between the techniques and in particular show that, although conceptually and technically quite different, all of the techniques give the same answer when applied to the random-worlds method.
A Stratified Simulation Scheme for Inference in Bayesian Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

Simulation schemes for probabilistic inference in Bayesian belief networks offer many advantages over exact algorithms; for example, these schemes have a linear and thus predictable runtime while exact algorithms have exponential runtime. Experiments have shown that likelihood weighting is one of the most promising simulation schemes. In this paper, we present a new simulation scheme that generates samples more evenly spread in the sample space than the likelihood weighting scheme. We show both theoretically and experimentally that the stratified scheme outperforms likelihood weighting in average runtime and error in estimates of beliefs.
An Alternative Proof Method for Possibilistic Logic and its Application to Terminological Logics
Venue: arXiv cs.AI 2013
Year: 2013

Possibilistic logic, an extension of first-order logic, deals with uncertainty that can be estimated in terms of possibility and necessity measures. Syntactically, this means that a first-order formula is equipped with a possibility degree or a necessity degree that expresses to what extent the formula is possibly or necessarily true. Possibilistic resolution yields a calculus for possibilistic logic which respects the semantics developed for possibilistic logic. A drawback, which possibilistic resolution inherits from classical resolution, is that it may not terminate if applied to formulas belonging to decidable fragments of first-order logic. Therefore we propose an alternative proof method for possibilistic logic. The main feature of this method is that it completely abstracts from a concrete calculus but uses as basic operation a test for classical entailment. We then instantiate possibilistic logic with a terminological logic, which is a decidable subclass o f first-order logic but nevertheless much more expressive than propositional logic. This yields an extension of terminological logics towards the representation of uncertain knowledge which is satisfactory from a semantic as well as algorithmic point of view.
The Automated Mapping of Plans for Plan Recognition
Venue: arXiv cs.AI 2013
Year: 2013

To coordinate with other agents in its environment, an agent needs models of what the other agents are trying to do. When communication is impossible or expensive, this information must be acquired indirectly via plan recognition. Typical approaches to plan recognition start with a specification of the possible plans the other agents may be following, and develop special techniques for discriminating among the possibilities. Perhaps more desirable would be a uniform procedure for mapping plans to general structures supporting inference based on uncertain and incomplete observations. In this paper, we describe a set of methods for converting plans represented in a flexible procedural language to observation models represented as probabilistic belief networks.
Optimal Junction Trees
Venue: arXiv cs.AI 2013
Year: 2013

The paper deals with optimality issues in connection with updating beliefs in networks. We address two processes: triangulation and construction of junction trees. In the first part, we give a simple algorithm for constructing an optimal junction tree from a triangulated network. In the second part, we argue that any exact method based on local calculations must either be less efficient than the junction tree method, or it has an optimality problem equivalent to that of triangulation.
Syntax-based Default Reasoning as Probabilistic Model-based Diagnosis
Venue: arXiv cs.AI 2013
Year: 2013

We view the syntax-based approaches to default reasoning as a model-based diagnosis problem, where each source giving a piece of information is considered as a component. It is formalized in the ATMS framework (each source corresponds to an assumption). We assume then that all sources are independent and "fail" with a very small probability. This leads to a probability assignment on the set of candidates, or equivalently on the set of consistent environments. This probability assignment induces a Dempster-Shafer belief function which measures the probability that a proposition can be deduced from the evidence. This belief function can be used in several different ways to define a non-monotonic consequence relation. We study and compare these consequence relations. The -case of prioritized knowledge bases is briefly considered.
Robust Planning in Uncertain Environments
Venue: arXiv cs.AI 2013
Year: 2013

This paper describes a novel approach to planning which takes advantage of decision theory to greatly improve robustness in an uncertain environment. We present an algorithm which computes conditional plans of maximum expected utility. This algorithm relies on a representation of the search space as an AND/OR tree and employs a depth-limit to control computation costs. A numeric robustness factor, which parameterizes the utility function, allows the user to modulate the degree of risk-aversion employed by the planner. Via a look-ahead search, the planning algorithm seeks to find an optimal plan using expected utility as its optimization criterion. We present experimental results obtained by applying our algorithm to a non-deterministic extension of the blocks world domain. Our results demonstrate that the robustness factor governs the degree of risk embodied in the conditional plans computed by our algorithm.
Belief Updating by Enumerating High-Probability Independence-Based Assignments
Venue: arXiv cs.AI 2013
Year: 2013

Independence-based (IB) assignments to Bayesian belief networks were originally proposed as abductive explanations. IB assignments assign fewer variables in abductive explanations than do schemes assigning values to all evidentially supported variables. We use IB assignments to approximate marginal probabilities in Bayesian belief networks. Recent work in belief updating for Bayes networks attempts to approximate posterior probabilities by finding a small number of the highest probability complete (or perhaps evidentially supported) assignments. Under certain assumptions, the probability mass in the union of these assignments is sufficient to obtain a good approximation. Such methods are especially useful for highly-connected networks, where the maximum clique size or the cutset size make the standard algorithms intractable. Since IB assignments contain fewer assigned variables, the probability mass in each assignment is greater than in the respective complete assignment. Thus, fewer IB assignments are sufficient, and a good approximation can be obtained more efficiently. IB assignments can be used for efficiently approximating posterior node probabilities even in cases which do not obey the rather strict skewness assumptions used in previous research. Two algorithms for finding the high probability IB assignments are suggested: one by doing a best-first heuristic search, and another by special-purpose integer linear programming. Experimental results show that this approach is feasible for highly connected belief networks.
Generating Graphoids from Generalised Conditional Probability
Venue: arXiv cs.AI 2013
Year: 2013

We take a general approach to uncertainty on product spaces, and give sufficient conditions for the independence structures of uncertainty measures to satisfy graphoid properties. Since these conditions are arguably more intuitive than some of the graphoid properties, they can be viewed as explanations why probability and certain other formalisms generate graphoids. The conditions include a sufficient condition for the Intersection property which can still apply even if there is a strong logical relations hip between the variables. We indicate how these results can be used to produce theories of qualitative conditional probability which are semi-graphoids and graphoids.
Decidable Classes of Tree Automata Mixing Local and Global Constraints Modulo Flat Theories
Venue: arXiv cs.LO 2013
Year: 2013

We define a class of ranked tree automata TABG generalizing both the tree automata with local tests between brothers of Bogaert and Tison (1992) and with global equality and disequality constraints (TAGED) of Filiot et al. (2007). TABG can test for equality and disequality modulo a given flat equational theory between brother subterms and between subterms whose positions are defined by the states reached during a computation. In particular, TABG can check that all the subterms reaching a given state are distinct. This constraint is related to monadic key constraints for XML documents, meaning that every two distinct positions of a given type have different values. We prove decidability of the emptiness problem for TABG. This solves, in particular, the open question of the decidability of emptiness for TAGED. We further extend our result by allowing global arithmetic constraints for counting the number of occurrences of some state or the number of different equivalence classes of subterms (modulo a given flat equational theory) reaching some state during a computation. We also adapt the model to unranked ordered terms. As a consequence of our results for TABG, we prove the decidability of a fragment of the monadic second order logic on trees extended with predicates for equality and disequality between subtrees, and cardinality.
Integration of nanoscale memristor synapses in neuromorphic computing architectures
Venue: arXiv cs.ET 2013
Year: 2013

Conventional neuro-computing architectures and artificial neural networks have often been developed with no or loose connections to neuroscience. As a consequence, they have largely ignored key features of biological neural processing systems, such as their extremely low-power consumption features or their ability to carry out robust and efficient computation using massively parallel arrays of limited precision, highly variable, and unreliable components. Recent developments in nano-technologies are making available extremely compact and low-power, but also variable and unreliable solid-state devices that can potentially extend the offerings of availing CMOS technologies. In particular, memristors are regarded as a promising solution for modeling key features of biological synapses due to their nanoscale dimensions, their capacity to store multiple bits of information per element and the low energy required to write distinct states. In this paper, we first review the neuro- and neuromorphic-computing approaches that can best exploit the properties of memristor and-scale devices, and then propose a novel hybrid memristor-CMOS neuromorphic circuit which represents a radical departure from conventional neuro-computing approaches, as it uses memristors to directly emulate the biophysics and temporal dynamics of real synapses. We point out the differences between the use of memristors in conventional neuro-computing architectures and the hybrid memristor-CMOS circuit proposed, and argue how this circuit represents an ideal building block for implementing brain-inspired probabilistic computing paradigms that are robust to variability and fault-tolerant by design.
Presence Factor-Oriented Blog Summarization
Venue: arXiv cs.IR 2013
Year: 2013

The research that has been carried out on blogs focused on blog posts only, ignoring the title of the blog page. Also, in summarization only a set of representative sentences are extracted. Some analysis has been done and it has been found that the blog post contains the content that is likely to be related to the topic of the blog post. Thus, proposed system of summarization makes use of title contained in a blog page. The approach makes use of the Presence factor that indicates the presence of each term of the title in each sentence of the blog post. This is a key feature because it considers those sentences as more relevant for summarization that contain each of the term present in the title. The system has been implemented and evaluated experimentally. The system has shown promising results.
Fast Matching by 2 Lines of Code for Large Scale Face Recognition Systems
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, we propose a method to apply the popular cascade classifier into face recognition to improve the computational efficiency while keeping high recognition rate. In large scale face recognition systems, because the probability of feature templates coming from different subjects is very high, most of the matching pairs will be rejected by the early stages of the cascade. Therefore, the cascade can improve the matching speed significantly. On the other hand, using the nested structure of the cascade, we could drop some stages at the end of feature to reduce the memory and bandwidth usage in some resources intensive system while not sacrificing the performance too much. The cascade is learned by two steps. Firstly, some kind of prepared features are grouped into several nested stages. And then, the threshold of each stage is learned to achieve user defined verification rate (VR). In the paper, we take a landmark based Gabor+LDA face recognition system as baseline to illustrate the process and advantages of the proposed method. However, the use of this method is very generic and not limited in face recognition, which can be easily generalized to other biometrics as a post-processing module. Experiments on the FERET database show the good performance of our baseline and an experiment on a self-collected large scale database illustrates that the cascade can improve the matching speed significantly.
Torque Saturation in Bipedal Robotic Walking through Control Lyapunov Function Based Quadratic Programs
Venue: arXiv cs.SY 2013
Year: 2013

This paper presents a novel method for directly incorporating user-defined control input saturations into the calculation of a control Lyapunov function (CLF)-based walking controller for a biped robot. Previous work by the authors has demonstrated the effectiveness of CLF controllers for stabilizing periodic gaits for biped walkers, and the current work expands on those results by providing a more effective means for handling control saturations. The new approach, based on a convex optimization routine running at a 1 kHz control update rate, is useful not only for handling torque saturations but also for incorporating a whole family of user-defined constraints into the online computation of a CLF controller. The paper concludes with an experimental implementation of the main results on the bipedal robot MABEL.
QCSP on partially reflexive cycles - the wavy line of tractability
Venue: arXiv cs.CC 2013
Year: 2013

We study the (non-uniform) quantified constraint satisfaction problem QCSP(H) as H ranges over partially reflexive cycles. We obtain a complexity-theoretic dichotomy: QCSP(H) is either in NL or is NP-hard. The separating conditions are somewhat esoteric hence the epithet "wavy line of tractability".
Entropy Distance
Venue: arXiv cs.IT 2013
Year: 2013

Motivated by the approach of random linear codes, a new distance in the vector space over a finite field is defined as the logarithm of the "surface area" of a Hamming ball with radius being the corresponding Hamming distance. It is named entropy distance because of its close relation with entropy function. It is shown that entropy distance is a metric for a non-binary field and a pseudometric for the binary field. The entropy distance of a linear code is defined to be the smallest entropy distance between distinct codewords of the code. Analogues of the Gilbert bound, the Hamming bound, and the Singleton bound are derived for the largest size of a linear code given the length and entropy distance of the code. Furthermore, as an important property related to lossless joint source-channel coding, the entropy distance of a linear encoder is defined. Very tight upper and lower bounds are obtained for the largest entropy distance of a linear encoder with given dimensions of input and output vector spaces.
Estimating Thematic Similarity of Scholarly Papers with Their Resistance Distance in an Electric Network Model
Venue: arXiv cs.DL 2013
Year: 2013

We calculate resistance distances between papers in a nearly bipartite citation network of 492 papers and the sources cited by them. We validate that this is a realistic measure of thematic distance if each citation link has an electric resistance equal to the geometric mean of the number of the paper's references and the citation number of the cited source.