OpenRaiser/Intern-Atlas huggingface dataset:
Repair for Distributed Storage Systems in Packet Erasure Networks
Venue: arXiv cs.IT 2014
Year: 2014

Reliability is essential for storing files in many applications of distributed storage systems. To maintain reliability, when a storage node fails, a new node should be regenerated by a repair process. Most of the previous results on the repair problem assume perfect (error-free) links in the networks. However, in practice, especially in a wireless network, the transmitted packets (for repair) may be lost due to, e.g., link failure or buffer overflow. We study the repair problem of distributed storage systems in packet erasure networks, where a packet loss is modeled as an erasure. The minimum repair-bandwidth, namely the amount of information sent from the surviving nodes to the new node, is established under the ideal assumption of infinite number of packet transmissions. We also study the bandwidth-storage tradeoffs in erasure networks. Then, the use of repairing storage nodes (nodes with smaller storage space) is proposed to reduce the repair-bandwidth. We study the minimal storage of repairing storage nodes. For the case of a finite number of packet transmissions, the probability of successful repairing is investigated. We show that the repair with a finite number of packet transmissions may use much larger bandwidth than the minimum repair-bandwidth. Finally, we propose a combinatorial optimization problem, which results in the optimal repair-bandwidth for the given packet erasure probability and finite packet transmissions.
Lifted Variable Elimination for Probabilistic Logic Programming
Venue: arXiv cs.AI 2014
Year: 2014

Lifted inference has been proposed for various probabilistic logical frameworks in order to compute the probability of queries in a time that depends on the size of the domains of the random variables rather than the number of instances. Even if various authors have underlined its importance for probabilistic logic programming (PLP), lifted inference has been applied up to now only to relational languages outside of logic programming. In this paper we adapt Generalized Counting First Order Variable Elimination (GC-FOVE) to the problem of computing the probability of queries to probabilistic logic programs under the distribution semantics. In particular, we extend the Prolog Factor Language (PFL) to include two new types of factors that are needed for representing ProbLog programs. These factors take into account the existing causal independence relationships among random variables and are managed by the extension to variable elimination proposed by Zhang and Poole for dealing with convergent variables and heterogeneous factors. Two new operators are added to GC-FOVE for treating heterogeneous factors. The resulting algorithm, called LP$^2$ for Lifted Probabilistic Logic Programming, has been implemented by modifying the PFL implementation of GC-FOVE and tested on three benchmarks for lifted inference. A comparison with PITA and ProbLog2 shows the potential of the approach.
Fast and Fuzzy Private Set Intersection
Venue: arXiv cs.CR 2014
Year: 2014

Private Set Intersection (PSI) is usually implemented as a sequence of encryption rounds between pairs of users, whereas the present work implements PSI in a simpler fashion: each set only needs to be encrypted once, after which each pair of users need only one ordinary set comparison. This is typically orders of magnitude faster than ordinary PSI at the cost of some ``fuzziness" in the matching, which may nonetheless be tolerable or even desirable. This is demonstrated in the case where the sets consist of English words processed with WordNet.
Algorithm Instance Games
Venue: arXiv cs.GT 2014
Year: 2014

This paper introduces algorithm instance games (AIGs) as a conceptual classification applying to games in which outcomes are resolved from joint strategies algorithmically. For such games, a fundamental question asks: How do the details of the algorithm's description influence agents' strategic behavior? We analyze two versions of an AIG based on the set-cover optimization problem. In these games, joint strategies correspond to instances of the set-cover problem, with each subset (of a given universe of elements) representing the strategy of a single agent. Outcomes are covers computed from the joint strategies by a set-cover algorithm. In one variant of this game, outcomes are computed by a deterministic greedy algorithm, and the other variant utilizes a non-deterministic form of the greedy algorithm. We characterize Nash equilibrium strategies for both versions of the game, finding that agents' strategies can vary considerably between the two settings. In particular, we find that the version of the game based on the deterministic algorithm only admits Nash equilibrium in which agents choose strategies (i.e., subsets) containing at most one element, with no two agents picking the same element. On the other hand, in the version of the game based on the non-deterministic algorithm, Nash equilibrium strategies can include agents with zero, one, or every element, and the same element can appear in the strategies of multiple agents.
Grounding Bound Founded Answer Set Programs
Venue: arXiv cs.AI 2014
Year: 2014

To appear in Theory and Practice of Logic Programming (TPLP) Bound Founded Answer Set Programming (BFASP) is an extension of Answer Set Programming (ASP) that extends stable model semantics to numeric variables. While the theory of BFASP is defined on ground rules, in practice BFASP programs are written as complex non-ground expressions. Flattening of BFASP is a technique used to simplify arbitrary expressions of the language to a small and well defined set of primitive expressions. In this paper, we first show how we can flatten arbitrary BFASP rule expressions, to give equivalent BFASP programs. Next, we extend the bottom-up grounding technique and magic set transformation used by ASP to BFASP programs. Our implementation shows that for BFASP problems, these techniques can significantly reduce the ground program size, and improve subsequent solving.
Probabilistic Argumentation with Epistemic Extensions and Incomplete Information
Venue: arXiv cs.AI 2014
Year: 2014

Abstract argumentation offers an appealing way of representing and evaluating arguments and counterarguments. This approach can be enhanced by a probability assignment to each argument. There are various interpretations that can be ascribed to this assignment. In this paper, we regard the assignment as denoting the belief that an agent has that an argument is justifiable, i.e., that both the premises of the argument and the derivation of the claim of the argument from its premises are valid. This leads to the notion of an epistemic extension which is the subset of the arguments in the graph that are believed to some degree (which we defined as the arguments that have a probability assignment greater than 0.5). We consider various constraints on the probability assignment. Some constraints correspond to standard notions of extensions, such as grounded or stable extensions, and some constraints give us new kinds of extensions.
Can Online MBA Programs Allow Professional Working Mothers to Balance Work, Family, and Career Progression? A Case Study in China
Venue: arXiv cs.CY 2014
Year: 2014

Career progression is a general concern of professional working mothers in China. The purpose of this paper is to report a qualitative study of Chinese professional working mothers that explored the perceptions of online Master's of Business Administration (MBA) programmes as a tool for career progression for working mothers balancing work and family in China. The objective was to examine existing work-family and career progression conflicts, the perceived usefulness of online MBA in balancing work-family and career aspirations, and the perceived ease of use of e-learning. Using Davis's (1989) technology acceptance model (TAM), the research drew on in-depth interviews with 10 female part-time MBA students from a university in Wuhan. The data were analysed through coding and transcribing. The findings showed that conflicts arose where demanding work schedules competed with family obligations, studies, and caring for children and the elderly. Online MBA programmes were viewed as a viable tool for balancing work and family and studying, given its flexible time management capabilities. However, consideration must be given to address students' motivation issues, lack of networking, lack of face-to-face interaction, and quality. The research findings emphasise the pragmatic need to re-align higher education policy and practice to position higher education e-learning as a trustable education delivery channel in China. By shedding light on the prevailing work-family conflict experienced by women seeking career advancement, this study suggests developing better gender-supporting policies and innovative e-learning practices to champion online MBA programme for this target niche.
Active Mining of Parallel Video Streams
Venue: arXiv cs.CV 2014
Year: 2014

The practicality of a video surveillance system is adversely limited by the amount of queries that can be placed on human resources and their vigilance in response. To transcend this limitation, a major effort under way is to include software that (fully or at least semi) automatically mines video footage, reducing the burden imposed to the system. Herein, we propose a semi-supervised incremental learning framework for evolving visual streams in order to develop a robust and flexible track classification system. Our proposed method learns from consecutive batches by updating an ensemble in each time. It tries to strike a balance between performance of the system and amount of data which needs to be labelled. As no restriction is considered, the system can address many practical problems in an evolving multi-camera scenario, such as concept drift, class evolution and various length of video streams which have not been addressed before. Experiments were performed on synthetic as well as real-world visual data in non-stationary environments, showing high accuracy with fairly little human collaboration.
A Vernacular for Coherent Logic
Venue: arXiv cs.LO 2014
Year: 2014

We propose a simple, yet expressive proof representation from which proofs for different proof assistants can easily be generated. The representation uses only a few inference rules and is based on a frag- ment of first-order logic called coherent logic. Coherent logic has been recognized by a number of researchers as a suitable logic for many ev- eryday mathematical developments. The proposed proof representation is accompanied by a corresponding XML format and by a suite of XSL transformations for generating formal proofs for Isabelle/Isar and Coq, as well as proofs expressed in a natural language form (formatted in LATEX or in HTML). Also, our automated theorem prover for coherent logic exports proofs in the proposed XML format. All tools are publicly available, along with a set of sample theorems.
Hipster: Integrating Theory Exploration in a Proof Assistant
Venue: arXiv cs.LO 2014
Year: 2014

This paper describes Hipster, a system integrating theory exploration with the proof assistant Isabelle/HOL. Theory exploration is a technique for automatically discovering new interesting lemmas in a given theory development. Hipster can be used in two main modes. The first is exploratory mode, used for automatically generating basic lemmas about a given set of datatypes and functions in a new theory development. The second is proof mode, used in a particular proof attempt, trying to discover the missing lemmas which would allow the current goal to be proved. Hipster's proof mode complements and boosts existing proof automation techniques that rely on automatically selecting existing lemmas, by inventing new lemmas that need induction to be proved. We show example uses of both modes.
Online Channel Assignment in Multi-Radio Wireless Mesh Networks Using Learning Automata
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we look into the problem of channel assignment in multi-channel multi-radio wireless mesh networks. We propose a new learning automata based channel assignment scheme that adaptively improve network overall throughput by expecting channel state. Since the ability of sending packets via upstream links will be evaluation bases for assigning channels to radio interfaces on each node. We use a link capacity function that potentially reflects degree of interferences imposed by selected channels by each node. According to dynamics of system, proposed algorithm assigns channels to radio interface in distributed fashion such that minimize interference in neighborhood of a node. We analyze the stability of the system via appropriate Lyapunov-like trajectory; we show that stability and optimum point of the system is converged.
Satisfaction in societies with opinion leaders and mediators: properties and an axiomatization
Venue: arXiv cs.GT 2014
Year: 2014

In this paper we propose the opinion leader-follower through mediators systems (OLFM systems) a multiple-action collective choice model for societies. In those societies three kind of actors are considered: opinion leaders that can exert certain influence over the decision of other actors, followers that can be convinced to modify their original decisions, and independent actors that neither are influenced nor can influence; mediators are actors that both are influenced and influence other actors. This is a generalization of the opinion leader-follower systems (OLF systems) proposed by van den Brink R, et al. (2011). The satisfaction score is defined on the set of actors. For each actor it measures the number of society initial decisions in which the final collective decision coincides with the one that the actor initially selected. We generalize in OLFM systems some properties that the satisfaction score meets for OLF systems. By using these properties, we provide an axiomatization of the satisfaction score for the case in which followers maintain their own initial decisions unless all their opinion leaders share an opposite inclination. This new axiomatization generalizes the one given by van den Brink R, et al. (2012) for OLF systems under the same restrictions.
An error estimate of Gaussian Recursive Filter in 3Dvar problem
Venue: arXiv cs.NA 2014
Year: 2014

Computational kernel of the three-dimensional variational data assimilation (3D-Var) problem is a linear system, generally solved by means of an iterative method. The most costly part of each iterative step is a matrix-vector product with a very large covariance matrix having Gaussian correlation structure. This operation may be interpreted as a Gaussian convolution, that is a very expensive numerical kernel. Recursive Filters (RFs) are a well known way to approximate the Gaussian convolution and are intensively applied in the meteorology, in the oceanography and in forecast models. In this paper, we deal with an oceanographic 3D-Var data assimilation scheme, named OceanVar, where the linear system is solved by using the Conjugate Gradient (GC) method by replacing, at each step, the Gaussian convolution with RFs. Here we give theoretical issues on the discrete convolution approximation with a first order (1st-RF) and a third order (3rd-RF) recursive filters. Numerical experiments confirm given error bounds and show the benefits, in terms of accuracy and performance, of the 3-rd RF.
Dimension Detection with Local Homology
Venue: arXiv cs.CG 2014
Year: 2014

Detecting the dimension of a hidden manifold from a point sample has become an important problem in the current data-driven era. Indeed, estimating the shape dimension is often the first step in studying the processes or phenomena associated to the data. Among the many dimension detection algorithms proposed in various fields, a few can provide theoretical guarantee on the correctness of the estimated dimension. However, the correctness usually requires certain regularity of the input: the input points are either uniformly randomly sampled in a statistical setting, or they form the so-called $(\varepsilon,δ)$-sample which can be neither too dense nor too sparse. Here, we propose a purely topological technique to detect dimensions. Our algorithm is provably correct and works under a more relaxed sampling condition: we do not require uniformity, and we also allow Hausdorff noise. Our approach detects dimension by determining local homology. The computation of this topological structure is much less sensitive to the local distribution of points, which leads to the relaxation of the sampling conditions. Furthermore, by leveraging various developments in computational topology, we show that this local homology at a point $z$ can be computed \emph{exactly} for manifolds using Vietoris-Rips complexes whose vertices are confined within a local neighborhood of $z$. We implement our algorithm and demonstrate the accuracy and robustness of our method using both synthetic and real data sets.
Anytime Computation of Cautious Consequences in Answer Set Programming
Venue: arXiv cs.AI 2014
Year: 2014

Query answering in Answer Set Programming (ASP) is usually solved by computing (a subset of) the cautious consequences of a logic program. This task is computationally very hard, and there are programs for which computing cautious consequences is not viable in reasonable time. However, current ASP solvers produce the (whole) set of cautious consequences only at the end of their computation. This paper reports on strategies for computing cautious consequences, also introducing anytime algorithms able to produce sound answers during the computation.
Incremental Tabling in Support of Knowledge Representation and Reasoning
Venue: arXiv cs.PL 2014
Year: 2014

Resolution-based Knowledge Representation and Reasoning (KRR) systems, such as Flora-2, Silk or Ergo, can scale to tens or hundreds of millions of facts, while supporting reasoning that includes Hilog, inheritance, defeasibility theories, and equality theories. These systems handle the termination and complexity issues that arise from the use of these features by a heavy use of tabled resolution. In fact, such systems table by default all rules defined by users, unless they are simple facts. Performing dynamic updates within such systems is nearly impossible unless the tables themselves can be made to react to changes. Incremental tabling as first implemented in XSB (Saha 2006) partially addressed this problem, but the implementation was limited in scope and not always easy to use. In this paper, we introduce transparent incremental tabling which at the semantic level supports updates in the 3-valued well-founded semantics, while guaranteeing full consistency of all tabled queries. Transparent incremental tabling also has significant performance improvements over previous implementations, including lazy recomputation, and control over the dependency structures used to determine how tables are updated.
Student Dropout Risk Assessment in Undergraduate Course at Residential University
Venue: arXiv cs.CY 2014
Year: 2014

Student dropout prediction is an indispensable for numerous intelligent systems to measure the education system and success rate of any university as well as throughout the university in the world. Therefore, it becomes essential to develop efficient methods for prediction of the students at risk of dropping out, enabling the adoption of proactive process to minimize the situation. Thus, this research work propose a prototype machine learning tool which can automatically recognize whether the student will continue their study or drop their study using classification technique based on decision tree and extract hidden information from large data about what factors are responsible for dropout student. Further the contribution of factors responsible for dropout risk was studied using discriminant analysis and to extract interesting correlations, frequent patterns, associations or casual structures among significant datasets, Association rule mining was applied. In this study, the descriptive statistics analysis was carried out to measure the quality of data using SPSS 20.0 statistical software and application of decision tree and association rule were carried out by using WEKA data mining tool.
Building a Classification Model for Enrollment In Higher Educational Courses using Data Mining Techniques
Venue: arXiv cs.AI 2014
Year: 2014

Data Mining is the process of extracting useful patterns from the huge amount of database and many data mining techniques are used for mining these patterns. Recently, one of the remarkable facts in higher educational institute is the rapid growth data and this educational data is expanding quickly without any advantage to the educational management. The main aim of the management is to refine the education standard; therefore by applying the various data mining techniques on this data one can get valuable information. This research study proposed the "classification model for the student's enrollment process in higher educational courses using data mining techniques". Additionally, this study contributes to finding some patterns that are meaningful to management.
Minimum Model Semantics for Extensional Higher-order Logic Programming with Negation
Venue: arXiv cs.PL 2014
Year: 2014

Extensional higher-order logic programming has been introduced as a generalization of classical logic programming. An important characteristic of this paradigm is that it preserves all the well-known properties of traditional logic programming. In this paper we consider the semantics of negation in the context of the new paradigm. Using some recent results from non-monotonic fixed-point theory, we demonstrate that every higher-order logic program with negation has a unique minimum infinite-valued model. In this way we obtain the first purely model-theoretic semantics for negation in extensional higher-order logic programming. Using our approach, we resolve an old paradox that was introduced by W. W. Wadge in order to demonstrate the semantic difficulties of higher-order logic programming.
Logic Programming as Scripting Language for Bots in Computer Games -- Research Overview
Venue: arXiv cs.PL 2014
Year: 2014

This publication is to present a summary of research (referred as Klabs - http://www.kappalabs.org) carried out in author's Ph.D studies on topic of application of Logic Programming as scripting language for virtual character behavior control in First Person Shooter (FPS) games. The research goal is to apply reasoning and knowledge representation techniques to create character behavior, which results in increased players' engagement. An extended abstract / full version of a paper accepted to be presented at the Doctoral Consortium of the 30th International Conference on Logic Programming (ICLP 2014), July 19-22, Vienna, Austria
The Higher-Order Voronoi Diagram of Line Segments
Venue: arXiv cs.CG 2014
Year: 2014

Surprisingly, the order-$k$ Voronoi diagram of line segments had received no attention in the computational-geometry literature. It illustrates properties surprisingly different from its counterpart for points; for example, a single order-$k$ Voronoi region may consist of $Ω(n)$ disjoint faces. We analyze the structural properties of this diagram and show that its combinatorial complexity for $n$ non-crossing line segments is $O(k(n-k))$, despite the disconnected regions. The same bound holds for $n$ intersecting line segments, when $k\geq n/2$. We also consider the order-$k$ Voronoi diagram of line segments that form a planar straight-line graph, and augment the definition of an order-$k$ Voronoi diagram to cover non-disjoint sites, addressing the issue of non-uniqueness for $k$-nearest sites. Furthermore, we enhance the iterative approach to construct this diagram. All bounds are valid in the general $L_p$ metric, $1\leq p\leq \infty$. For non-crossing segments in the $L_\infty$ and $L_1$ metrics, we show a tighter $O((n-k)^2)$ bound for $k>n/2$.