OpenRaiser/Intern-Atlas huggingface dataset:
Real-Time Scheduling via Reinforcement Learning
Venue: arXiv cs.LG 2012
Year: 2012

Cyber-physical systems, such as mobile robots, must respond adaptively to dynamic operating conditions. Effective operation of these systems requires that sensing and actuation tasks are performed in a timely manner. Additionally, execution of mission specific tasks such as imaging a room must be balanced against the need to perform more general tasks such as obstacle avoidance. This problem has been addressed by maintaining relative utilization of shared resources among tasks near a user-specified target level. Producing optimal scheduling strategies requires complete prior knowledge of task behavior, which is unlikely to be available in practice. Instead, suitable scheduling strategies must be learned online through interaction with the system. We consider the sample complexity of reinforcement learning in this domain, and demonstrate that while the problem state space is countably infinite, we may leverage the problem's structure to guarantee efficient learning.
Causal Conclusions that Flip Repeatedly and Their Justification
Venue: arXiv cs.LG 2012
Year: 2012

Over the past two decades, several consistent procedures have been designed to infer causal conclusions from observational data. We prove that if the true causal network might be an arbitrary, linear Gaussian network or a discrete Bayes network, then every unambiguous causal conclusion produced by a consistent method from non-experimental data is subject to reversal as the sample size increases any finite number of times. That result, called the causal flipping theorem, extends prior results to the effect that causal discovery cannot be reliable on a given sample size. We argue that since repeated flipping of causal conclusions is unavoidable in principle for consistent methods, the best possible discovery methods are consistent methods that retract their earlier conclusions no more than necessary. A series of simulations of various methods across a wide range of sample sizes illustrates concretely both the theorem and the principle of comparing methods in terms of retractions.
Automated Planning in Repeated Adversarial Games
Venue: arXiv cs.GT 2012
Year: 2012

Game theory's prescriptive power typically relies on full rationality and/or self-play interactions. In contrast, this work sets aside these fundamental premises and focuses instead on heterogeneous autonomous interactions between two or more agents. Specifically, we introduce a new and concise representation for repeated adversarial (constant-sum) games that highlight the necessary features that enable an automated planing agent to reason about how to score above the game's Nash equilibrium, when facing heterogeneous adversaries. To this end, we present TeamUP, a model-based RL algorithm designed for learning and planning such an abstraction. In essence, it is somewhat similar to R-max with a cleverly engineered reward shaping that treats exploration as an adversarial optimization problem. In practice, it attempts to find an ally with which to tacitly collude (in more than two-player games) and then collaborates on a joint plan of actions that can consistently score a high utility in adversarial repeated games. We use the inaugural Lemonade Stand Game Tournament to demonstrate the effectiveness of our approach, and find that TeamUP is the best performing agent, demoting the Tournament's actual winning strategy into second place. In our experimental analysis, we show hat our strategy successfully and consistently builds collaborations with many different heterogeneous (and sometimes very sophisticated) adversaries.
Comparative Analysis of Probabilistic Models for Activity Recognition with an Instrumented Walker
Venue: arXiv cs.AI 2012
Year: 2012

Rollating walkers are popular mobility aids used by older adults to improve balance control. There is a need to automatically recognize the activities performed by walker users to better understand activity patterns, mobility issues and the context in which falls are more likely to happen. We design and compare several techniques to recognize walker related activities. A comprehensive evaluation with control subjects and walker users from a retirement community is presented.
Algorithms and Complexity Results for Exact Bayesian Structure Learning
Venue: arXiv cs.LG 2012
Year: 2012

Bayesian structure learning is the NP-hard problem of discovering a Bayesian network that optimally represents a given set of training data. In this paper we study the computational worst-case complexity of exact Bayesian structure learning under graph theoretic restrictions on the super-structure. The super-structure (a concept introduced by Perrier, Imoto, and Miyano, JMLR 2008) is an undirected graph that contains as subgraphs the skeletons of solution networks. Our results apply to several variants of score-based Bayesian structure learning where the score of a network decomposes into local scores of its nodes. Results: We show that exact Bayesian structure learning can be carried out in non-uniform polynomial time if the super-structure has bounded treewidth and in linear time if in addition the super-structure has bounded maximum degree. We complement this with a number of hardness results. We show that both restrictions (treewidth and degree) are essential and cannot be dropped without loosing uniform polynomial time tractability (subject to a complexity-theoretic assumption). Furthermore, we show that the restrictions remain essential if we do not search for a globally optimal network but we aim to improve a given network by means of at most k arc additions, arc deletions, or arc reversals (k-neighborhood local search).
Inference by Minimizing Size, Divergence, or their Sum
Venue: arXiv cs.LG 2012
Year: 2012

We speed up marginal inference by ignoring factors that do not significantly contribute to overall accuracy. In order to pick a suitable subset of factors to ignore, we propose three schemes: minimizing the number of model factors under a bound on the KL divergence between pruned and full models; minimizing the KL divergence under a bound on factor count; and minimizing the weighted sum of KL divergence and factor count. All three problems are solved using an approximation of the KL divergence than can be calculated in terms of marginals computed on a simple seed graph. Applied to synthetic image denoising and to three different types of NLP parsing models, this technique performs marginal inference up to 11 times faster than loopy BP, with graph sizes reduced up to 98%-at comparable error in marginals and parsing accuracy. We also show that minimizing the weighted sum of divergence and size is substantially faster than minimizing either of the other objectives based on the approximation to divergence presented here.
Exact and Approximate Inference in Associative Hierarchical Networks using Graph Cuts
Venue: arXiv cs.AI 2012
Year: 2012

Markov Networks are widely used through out computer vision and machine learning. An important subclass are the Associative Markov Networks which are used in a wide variety of applications. For these networks a good approximate minimum cost solution can be found efficiently using graph cut based move making algorithms such as alpha-expansion. Recently a related model has been proposed, the associative hierarchical network, which provides a natural generalisation of the Associative Markov Network for higher order cliques (i.e. clique size greater than two). This method provides a good model for object class segmentation problem in computer vision. Within this paper we briefly describe the associative hierarchical network and provide a computationally efficient method for approximate inference based on graph cuts. Our method performs well for networks containing hundreds of thousand of variables, and higher order potentials are defined over cliques containing tens of thousands of variables. Due to the size of these problems standard linear programming techniques are inapplicable. We show that our method has a bound of 4 for the solution of general associative hierarchical network with arbitrary clique size noting that few results on bounds exist for the solution of labelling of Markov Networks with higher order cliques.
Modeling Events with Cascades of Poisson Processes
Venue: arXiv cs.LG 2012
Year: 2012

We present a probabilistic model of events in continuous time in which each event triggers a Poisson process of successor events. The ensemble of observed events is thereby modeled as a superposition of Poisson processes. Efficient inference is feasible under this model with an EM algorithm. Moreover, the EM algorithm can be implemented as a distributed algorithm, permitting the model to be applied to very large datasets. We apply these techniques to the modeling of Twitter messages and the revision history of Wikipedia.
Source Separation and Higher-Order Causal Analysis of MEG and EEG
Venue: arXiv cs.LG 2012
Year: 2012

Separation of the sources and analysis of their connectivity have been an important topic in EEG/MEG analysis. To solve this problem in an automatic manner, we propose a two-layer model, in which the sources are conditionally uncorrelated from each other, but not independent; the dependence is caused by the causality in their time-varying variances (envelopes). The model is identified in two steps. We first propose a new source separation technique which takes into account the autocorrelations (which may be time-varying) and time-varying variances of the sources. The causality in the envelopes is then discovered by exploiting a special kind of multivariate GARCH (generalized autoregressive conditional heteroscedasticity) model. The resulting causal diagram gives the effective connectivity between the separated sources; in our experimental results on MEG data, sources with similar functions are grouped together, with negative influences between groups, and the groups are connected via some interesting sources.
The Byzantine Brides Problem
Venue: arXiv cs.DC 2012
Year: 2012

We investigate the hardness of establishing as many stable marriages (that is, marriages that last forever) in a population whose memory is placed in some arbitrary state with respect to the considered problem, and where traitors try to jeopardize the whole process by behaving in a harmful manner. On the negative side, we demonstrate that no solution that is completely insensitive to traitors can exist, and we propose a protocol for the problem that is optimal with respect to the traitor containment radius.
An Accurate Arabic Root-Based Lemmatizer for Information Retrieval Purposes
Venue: arXiv cs.CL 2012
Year: 2012

In spite of its robust syntax, semantic cohesion, and less ambiguity, lemma level analysis and generation does not yet focused in Arabic NLP literatures. In the current research, we propose the first non-statistical accurate Arabic lemmatizer algorithm that is suitable for information retrieval (IR) systems. The proposed lemmatizer makes use of different Arabic language knowledge resources to generate accurate lemma form and its relevant features that support IR purposes. As a POS tagger, the experimental results show that, the proposed algorithm achieves a maximum accuracy of 94.8%. For first seen documents, an accuracy of 89.15% is achieved, compared to 76.7% of up to date Stanford accurate Arabic model, for the same, dataset.
Automated Text Summarization Base on Lexicales Chain and graph Using of WordNet and Wikipedia Knowledge Base
Venue: arXiv cs.IR 2012
Year: 2012

The technology of automatic document summarization is maturing and may provide a solution to the information overload problem. Nowadays, document summarization plays an important role in information retrieval. With a large volume of documents, presenting the user with a summary of each document greatly facilitates the task of finding the desired documents. Document summarization is a process of automatically creating a compressed version of a given document that provides useful information to users, and multi-document summarization is to produce a summary delivering the majority of information content from a set of documents about an explicit or implicit main topic. The lexical cohesion structure of the text can be exploited to determine the importance of a sentence/phrase. Lexical chains are useful tools to analyze the lexical cohesion structure in a text .In this paper we consider the effect of the use of lexical cohesion features in Summarization, And presenting a algorithm base on the knowledge base. Ours algorithm at first find the correct sense of any word, Then constructs the lexical chains, remove Lexical chains that less score than other, detects topics roughly from lexical chains, segments the text with respect to the topics and selects the most important sentences. The experimental results on an open benchmark datasets from DUC01 and DUC02 show that our proposed approach can improve the performance compared to sate-of-the-art summarization approaches.
Building MultiView Analyst Profile From Multidimensional Query Logs: From Consensual to Conflicting Preferences
Venue: arXiv cs.DB 2012
Year: 2012

In order to provide suitable results to the analyst needs, user preferences summarization is widely used in several domains. In this paper, we introduce a new approach for user profile construction from OLAP query logs. The key idea is to learn the user's preferences by drawing the evidence from OLAP logs. In fact, the analyst preferences are clustered into three main pools : (i) consensual or non conflicting preferences referring to same preferences for all analysts; (ii) semi-conflicting preferences corresponding to similar preferences for some analysts; (iii) conflicting preferences related to disjoint preferences for all analysts. To build generic and global model accurately describing the analyst, we enrich the obtained characteristics through including several views, namely the personal view, the professional view and the behavioral view. After that, the multiview profile extracted from multidimensional database can be annotated.
Distributed Position Localization and Tracking (DPLT) of Malicious Nodes in Cluster Based Mobile Ad hoc Networks (MANET)
Venue: arXiv cs.CG 2012
Year: 2012

In this paper, a robust distributed malicious node detection and precise localization and tracking method is proposed for Cluster based Mobile Ad hoc Network (MANET). Certificate Authority (CA) node is selected as the most stable node among trusted nodes, surrounded by Registration Authority nodes (RAs) in each cluster to generate the Dynamic Demilitarized Zone (DDMZ) to defend CA from probable attackers and mitigate the authentication overhead. The RAs also co-operate with member nodes to detect a target node and determine whether it is malicious or not, by providing the public key certificate and trust value. In addition, Internet Protocol (IP) based Triangulation and multi-lateration method are deployed based on using the average time difference of Time of Arrival (ToA) and Time of Departure (ToD) of the management packets. Triangulation uses three reference nodes which are elected within each cluster based on Best Criterion Function (BCF) to localize each member node inside the cluster in 2D. Multi-lateration is employed to localize the malicious target node in 2D using four neighbor nodes. After localization of two consecutive positions, the target node is continuously localized and tracked by a particular node using the modified real time Position Localization and Tracking (PL&T) algorithm by adaptive beam forming and mapping the energy contours of tracking zone into coverage radii distance. The performance of the proposed scheme demonstrates the significant accuracy in the detection of malicious nodes within each cluster.
Literature-based knowledge discovery: the state of the art
Venue: arXiv cs.DL 2012
Year: 2012

Literature-based knowledge discovery method was introduced by Dr. Swanson in 1986. He hypothesized a connection between Raynaud's phenomenon and dietary fish oil, the field of literature-based discovery (LBD) was born from then on. During the subsequent two decades, LBD's research attracts some scientists including information science, computer science, and biomedical science, etc.. It has been a part of knowledge discovery and text mining. This paper summarizes the development of recent years about LBD and presents two parts, methodology research and applied research. Lastly, some problems are pointed as future research directions.
Arabic Interface Analysis Based on Cultural Markers
Venue: arXiv cs.HC 2012
Year: 2012

This study examines the Arabic interface design elements that are largely influenced by the cultural values. Cultural markers are examined in websites from educational, business, and media. Cultural values analysis is based on Geert Hofstede's cultural dimensions. The findings show that there are cultural markers which are largely influenced by the culture and that the Hofstede's score for Arab countries is partially supported by the website design components examined in this study. Moderate support was also found for the long term orientation, for which Hoftsede has no score.
Space-Bounded Kolmogorov Extractors
Venue: arXiv cs.CC 2012
Year: 2012

An extractor is a function that receives some randomness and either "improves" it or produces "new" randomness. There are statistical and algorithmical specifications of this notion. We study an algorithmical one called Kolmogorov extractors and modify it to resource-bounded version of Kolmogorov complexity. Following Zimand we prove the existence of such objects with certain parameters. The utilized technique is "naive" derandomization: we replace random constructions employed by Zimand by pseudo-random ones obtained by Nisan-Wigderson generator.
Static Analysis of Run-Time Errors in Embedded Real-Time Parallel C Programs
Venue: arXiv cs.PL 2012
Year: 2012

We present a static analysis by Abstract Interpretation to check for run-time errors in parallel and multi-threaded C programs. Following our work on Astrée, we focus on embedded critical programs without recursion nor dynamic memory allocation, but extend the analysis to a static set of threads communicating implicitly through a shared memory and explicitly using a finite set of mutual exclusion locks, and scheduled according to a real-time scheduling policy and fixed priorities. Our method is thread-modular. It is based on a slightly modified non-parallel analysis that, when analyzing a thread, applies and enriches an abstract set of thread interferences. An iterator then re-analyzes each thread in turn until interferences stabilize. We prove the soundness of our method with respect to the sequential consistency semantics, but also with respect to a reasonable weakly consistent memory semantics. We also show how to take into account mutual exclusion and thread priorities through a partitioning over an abstraction of the scheduler state. We present preliminary experimental results analyzing an industrial program with our prototype, Thésée, and demonstrate the scalability of our approach.
Linear vertex-kernels for several dense ranking r-CSPs
Venue: arXiv cs.DM 2012
Year: 2012

A Ranking r-Constraint Satisfaction Problem (ranking r-CSP) consists of a ground set of vertices V, an arity r >= 2, a parameter k and a constraint system c, where c is a function which maps rankings of r-sized subsets of V to {0,1}. The objective is to decide if there exists a ranking of the vertices satisfying all but at most k constraints. Famous ranking r-CSP include the Feedback Arc Set in Tournaments and Betweenness in Tournaments problems. We consider these problems from the kernelization viewpoint. We prove that so-called l_r-simply characterized ranking r-CSPs admit linear vertex-kernels whenever they admit constant-factor approximation algorithms. This implies that r-Betweenness in Tournaments and r-Transitive Feedback Arc Set In Tournaments, two natural generalizations of the previously mentioned problems, admit linear vertex-kernels. Moreover, we introduce another generalization of Feedback Arc Set in Tournaments, which does not fit the aforementioned framework. We obtain a 5-approximation and a linear vertex-kernel for this problem.
A Survey on Security Issues in Ad Hoc Routing Protocols and their Mitigation Techniques
Venue: arXiv cs.CR 2012
Year: 2012

Mobile Ad hoc Networks (MANETS) are transient networks of mobile nodes, connected through wireless links, without any fixed infrastructure or central management. Due to the self-configuring nature of these networks, the topology is highly dynamic. This makes the Ad Hoc Routing Protocols in MANETS highly vulnerable to serious security issues. In this paper, we survey the common security threats and attacks and summarize the solutions suggested in the survey to mitigate these security vulnerabilities.
Constrained Role Mining
Venue: arXiv cs.CR 2012
Year: 2012

Role Based Access Control (RBAC) is a very popular access control model, for long time investigated and widely deployed in the security architecture of different enterprises. To implement RBAC, roles have to be firstly identified within the considered organization. Usually the process of (automatically) defining the roles in a bottom up way, starting from the permissions assigned to each user, is called {\it role mining}. In literature, the role mining problem has been formally analyzed and several techniques have been proposed in order to obtain a set of valid roles. Recently, the problem of defining different kind of constraints on the number and the size of the roles included in the resulting role set has been addressed. In this paper we provide a formal definition of the role mining problem under the cardinality constraint, i.e. restricting the maximum number of permissions that can be included in a role. We discuss formally the computational complexity of the problem and propose a novel heuristic. Furthermore we present experimental results obtained after the application of the proposed heuristic on both real and synthetic datasets, and compare the resulting performance to previous proposals
Automatic Theorem-Proving in Combinatorics on Words
Venue: arXiv cs.FL 2012
Year: 2012

We describe a technique for mechanically proving certain kinds of theorems in combinatorics on words, using automata and a package for manipulating them. We illustrate our technique by solving, purely mechanically, an open problem of Currie and Saari on the lengths of unbordered factors in the Thue-Morse sequence.
Data Mining: A Prediction for Performance Improvement of Engineering Students using Classification
Venue: arXiv cs.LG 2012
Year: 2012

Now-a-days the amount of data stored in educational database increasing rapidly. These databases contain hidden information for improvement of students' performance. Educational data mining is used to study the data available in the educational field and bring out the hidden knowledge from it. Classification methods like decision trees, Bayesian network etc can be applied on the educational data for predicting the student's performance in examination. This prediction will help to identify the weak students and help them to score better marks. The C4.5, ID3 and CART decision tree algorithms are applied on engineering student's data to predict their performance in the final exam. The outcome of the decision tree predicted the number of students who are likely to pass, fail or promoted to next year. The results provide steps to improve the performance of the students who were predicted to fail or promoted. After the declaration of the results in the final examination the marks obtained by the students are fed into the system and the results were analyzed for the next session. The comparative analysis of the results states that the prediction has helped the weaker students to improve and brought out betterment in the result.