OpenRaiser/Intern-Atlas huggingface dataset:
Fuzzy Aggregates in Fuzzy Answer Set Programming
Venue: arXiv cs.AI 2013
Year: 2013

Fuzzy answer set programming is a declarative framework for representing and reasoning about knowledge in fuzzy environments. However, the unavailability of fuzzy aggregates in disjunctive fuzzy logic programs, DFLP, with fuzzy answer set semantics prohibits the natural and concise representation of many interesting problems. In this paper, we extend DFLP to allow arbitrary fuzzy aggregates. We define fuzzy answer set semantics for DFLP with arbitrary fuzzy aggregates including monotone, antimonotone, and nonmonotone fuzzy aggregates. We show that the proposed fuzzy answer set semantics subsumes both the original fuzzy answer set semantics of DFLP and the classical answer set semantics of classical disjunctive logic programs with classical aggregates, and consequently subsumes the classical answer set semantics of classical disjunctive logic programs. We show that the proposed fuzzy answer sets of DFLP with fuzzy aggregates are minimal fuzzy models and hence incomparable, which is an important property for nonmonotonic fuzzy reasoning.
Network Compression: Worst-Case Analysis
Venue: arXiv cs.IT 2013
Year: 2013

We study the problem of communicating a distributed correlated memoryless source over a memoryless network, from source nodes to destination nodes, under quadratic distortion constraints. We establish the following two complementary results: (a) for an arbitrary memoryless network, among all distributed memoryless sources of a given correlation, Gaussian sources are least compressible, that is, they admit the smallest set of achievable distortion tuples, and (b) for any memoryless source to be communicated over a memoryless additive-noise network, among all noise processes of a given correlation, Gaussian noise admits the smallest achievable set of distortion tuples. We establish these results constructively by showing how schemes for the corresponding Gaussian problems can be applied to achieve similar performance for (source or noise) distributions that are not necessarily Gaussian but have the same covariance.
Multiparty Compatibility in Communicating Automata: Characterisation and Synthesis of Global Session Types
Venue: arXiv cs.FL 2013
Year: 2013

Multiparty session types are a type system that can ensure the safety and liveness of distributed peers via the global specification of their interactions. To construct a global specification from a set of distributed uncontrolled behaviours, this paper explores the problem of fully characterising multiparty session types in terms of communicating automata. We equip global and local session types with labelled transition systems (LTSs) that faithfully represent asynchronous communications through unbounded buffered channels. Using the equivalence between the two LTSs, we identify a class of communicating automata that exactly correspond to the projected local types. We exhibit an algorithm to synthesise a global type from a collection of communicating automata. The key property of our findings is the notion of multiparty compatibility which non-trivially extends the duality condition for binary session types.
Towards Efficient Abstractions for Concurrent Consensus
Venue: arXiv cs.PL 2013
Year: 2013

Consensus is an often occurring problem in concurrent and distributed programming. We present a programming language with simple semantics and build-in support for consensus in the form of communicating transactions. We motivate the need for such a construct with a characteristic example of generalized consensus which can be naturally encoded in our language. We then focus on the challenges in achieving an implementation that can efficiently run such programs. We setup an architecture to evaluate different implementation alternatives and use it to experimentally evaluate runtime heuristics. This is the basis for a research project on realistic programming language support for consensus.
Automatic Detection of Search Tactic in Individual Information Seeking: A Hidden Markov Model Approach
Venue: arXiv cs.IR 2013
Year: 2013

Information seeking process is an important topic in information seeking behavior research. Both qualitative and empirical methods have been adopted in analyzing information seeking processes, with major focus on uncovering the latent search tactics behind user behaviors. Most of the existing works require defining search tactics in advance and coding data manually. Among the few works that can recognize search tactics automatically, they missed making sense of those tactics. In this paper, we proposed using an automatic technique, i.e. the Hidden Markov Model (HMM), to explicitly model the search tactics. HMM results show that the identified search tactics of individual information seeking behaviors are consistent with Marchioninis Information seeking process model. With the advantages of showing the connections between search tactics and search actions and the transitions among search tactics, we argue that HMM is a useful tool to investigate information seeking process, or at least it provides a feasible way to analyze large scale dataset.
A new metric for routing in military wireless network
Venue: arXiv cs.NI 2013
Year: 2013

Wireless Ad-hoc network is generally employed in military and emergencies due to its flexibility and easy-to-use. It's suitable for military wireless network that has the characteristics of mobility and works effectively under severe environment and electromagnetic interfering conditions. However, military network cannot benefit from existing routing protocol directly; there exists quite many features which are only typical for military network. This paper presents a new metric for routing, which is employed in A* algorithm. The goal of the metric is to choose a route of less distance and less transmission delay between a source and a destination. Our metric is a function of the distance between the ends and the bandwidth over the link. Moreover, we take frequency selection into account since a node can work on multi-frequencies. This paper proposed the new metric, and experimented it based on A* algorithm. The simulation results show that this metric can find the optimal route which has less transmission delay compared to the shortest path routing.
Auction-based Resource Allocation in MillimeterWave Wireless Access Networks
Venue: arXiv cs.NI 2013
Year: 2013

The resource allocation problem of optimal assignment of the clients to the available access points in 60 GHz millimeterWave wireless access networks is investigated. The problem is posed as a multiassignment optimisation problem. The proposed solution method converts the initial problem to a minimum cost flow problem and allows to design an efficient algorithm by a combination of auction algorithms. The solution algorithm exploits the network optimization structure of the problem, and thus is much more powerful than computationally intensive general-purpose solvers. Theoretical and numerical results evince numerous properties, such as optimality, convergence, and scalability in comparison to existing approaches.
Performance Modelling and Analysis of Connection Admission Control in OFDMA based WiMAX System with MMPP Queuing
Venue: arXiv cs.NI 2013
Year: 2013

This paper presents a problem of queuing theoretic performance modeling and analysis of Orthogonal Frequency Division Multiple Access (OFDMA) under broad-band wireless networks. We consider a single-cell WiMAX environment in which the base station allocates sub channels to the subscriber stations in its coverage area. The sub channels allocated to a subscriber station are shared by multiple connections at that subscriber station. To ensure the Quality of Service (QoS) performances, two Connection Admission Control (CAC) schemes, namely, threshold-based and queue-aware CAC schemes are considered at a subscriber station. A queuing analytical framework for these admission control schemes is presented considering OFDMA-based transmission at the physical layer. Then, based on the queuing model, both the connection-level and the packetlevel performances are studied and compared with their analogues in the case without CAC. The connection arrival is modeled by a Poisson process and the packet arrival for a connection by a Markov Modulated Poisson Process (MMPP). We determine analytically and numerically different performance parameters, such as connection blocking probability, average number of ongoing connections, average queue length, packet dropping probability, queue throughput and average packet delay.
Improved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rank
Venue: arXiv cs.DS 2013
Year: 2013

We prove a structure theorem for the feasible solutions of the Arora-Rao-Vazirani SDP relaxation on low threshold rank graphs and on small-set expanders. We show that if G is a graph of bounded threshold rank or a small-set expander, then an optimal solution of the Arora-Rao-Vazirani relaxation (or of any stronger version of it) can be almost entirely covered by a small number of balls of bounded radius. Then, we show that, if k is the number of balls, a solution of this form can be rounded with an approximation factor of O(sqrt {log k}) in the case of the Arora-Rao-Vazirani relaxation, and with a constant-factor approximation in the case of the k-th round of the Sherali-Adams hierarchy starting at the Arora-Rao-Vazirani relaxation. The structure theorem and the rounding scheme combine to prove the following result, where G=(V,E) is a graph of expansion ϕ(G), λ_k is the k-th smallest eigenvalue of the normalized Laplacian of G, and ϕ_k(G) = \min_{disjoint S_1,...,S_k} \max_{1 <= i <= k} ϕ(S_i) is the largest expansion of any k disjoint subsets of V: if either λ_k >> log^{2.5} k \cdot phi(G) or ϕ_{k} (G) >> log k \cdot sqrt{log n}\cdot loglog n\cdot ϕ(G), then the Arora-Rao-Vazirani relaxation can be rounded in polynomial time with an approximation ratio O(sqrt{log k}). Stronger approximation guarantees are achievable in time exponential in k via relaxations in the Lasserre hierarchy. Guruswami and Sinop [GS13] and Arora, Ge and Sinop [AGS13] prove that 1+eps approximation is achievable in time 2^{O(k)} poly(n) if either λ_k > ϕ(G)/ poly(eps), or if SSE_{n/k} > sqrt{log k log n} \cdot ϕ(G)/ poly(eps), where SSE_s is the minimal expansion of sets of size at most s.
Nearly Maximum Flows in Nearly Linear Time
Venue: arXiv cs.DS 2013
Year: 2013

We introduce a new approach to the maximum flow problem in undirected, capacitated graphs using $α$-\emph{congestion-approximators}: easy-to-compute functions that approximate the congestion required to route single-commodity demands in a graph to within a factor of $α$. Our algorithm maintains an arbitrary flow that may have some residual excess and deficits, while taking steps to minimize a potential function measuring the congestion of the current flow plus an over-estimate of the congestion required to route the residual demand. Since the residual term over-estimates, the descent process gradually moves the contribution to our potential function from the residual term to the congestion term, eventually achieving a flow routing the desired demands with nearly minimal congestion after $\tilde{O}(α\eps^{-2}\log^2 n)$ iterations. Our approach is similar in spirit to that used by Spielman and Teng (STOC 2004) for solving Laplacian systems, and we summarize our approach as trying to do for $\ell_\infty$-flows what they do for $\ell_2$-flows. Together with a nearly linear time construction of a $n^{o(1)}$-congestion-approximator, we obtain $1+\eps$-optimal single-commodity flows undirected graphs in time $m^{1+o(1)}\eps^{-2}$, yielding the fastest known algorithm for that problem. Our requirements of a congestion-approximator are quite low, suggesting even faster and simpler algorithms for certain classes of graphs. For example, an $α$-competitive oblivious routing tree meets our definition, \emph{even without knowing how to route the tree back in the graph}. For graphs of conductance $ϕ$, a trivial $ϕ^{-1}$-congestion-approximator gives an extremely simple algorithm for finding $1+\eps$-optimal-flows in time $\tilde{O}(mϕ^{-1})$.
Sensors and Navigation Algorithms for Flight Control of Tethered Kites
Venue: arXiv cs.SY 2013
Year: 2013

We present the sensor setup and the basic navigation algorithm used for the flight control of the SkySails towing kite system. Starting with brief summaries on system setup and equations of motion of the tethered kite system, we subsequently give an overview of the sensor setup, present the navigation task and discuss challenges which have to be mastered. In the second part we introduce in detail the inertial navigation algorithm which has been used for operational flights for years. The functional capability of this algorithm is illustrated by experimental flight data. Finally we suggest a modification of the algorithms as further development step in order to overcome certain limitations.
Combinatorial Walrasian Equilibrium
Venue: arXiv cs.GT 2013
Year: 2013

We study a combinatorial market design problem, where a collection of indivisible objects is to be priced and sold to potential buyers subject to equilibrium constraints.The classic solution concept for such problems is Walrasian Equilibrium (WE), which provides a simple and transparent pricing structure that achieves optimal social welfare. The main weakness of the WE notion is that it exists only in very restrictive cases. To overcome this limitation, we introduce the notion of a Combinatorial Walrasian equilibium (CWE), a natural relaxation of WE. The difference between a CWE and a (non-combinatorial) WE is that the seller can package the items into indivisible bundles prior to sale, and the market does not necessarily clear. We show that every valuation profile admits a CWE that obtains at least half of the optimal (unconstrained) social welfare. Moreover, we devise a poly-time algorithm that, given an arbitrary allocation X, computes a CWE that achieves at least half of the welfare of X. Thus, the economic problem of finding a CWE with high social welfare reduces to the algorithmic problem of social-welfare approximation. In addition, we show that every valuation profile admits a CWE that extracts a logarithmic fraction of the optimal welfare as revenue. Finally, these results are complemented by strong lower bounds when the seller is restricted to using item prices only, which motivates the use of bundles. The strength of our results derives partly from their generality - our results hold for arbitrary valuations that may exhibit complex combinations of substitutes and complements.
Incremental Computation of Pseudo-Inverse of Laplacian: Theory and Applications
Venue: arXiv cs.DM 2013
Year: 2013

A divide-and-conquer based approach for computing the Moore-Penrose pseudo-inverse of the combinatorial Laplacian matrix $(\bb L^+)$ of a simple, undirected graph is proposed. % The nature of the underlying sub-problems is studied in detail by means of an elegant interplay between $\bb L^+$ and the effective resistance distance $(Ω)$. Closed forms are provided for a novel {\em two-stage} process that helps compute the pseudo-inverse incrementally. Analogous scalar forms are obtained for the converse case, that of structural regress, which entails the breaking up of a graph into disjoint components through successive edge deletions. The scalar forms in both cases, show absolute element-wise independence at all stages, thus suggesting potential parallelizability. Analytical and experimental results are presented for dynamic (time-evolving) graphs as well as large graphs in general (representing real-world networks). An order of magnitude reduction in computational time is achieved for dynamic graphs; while in the general case, our approach performs better in practice than the standard methods, even though the worst case theoretical complexities may remain the same: an important contribution with consequences to the study of online social networks.
Summary of A New Normative Theory of Probabilistic Logic
Venue: arXiv cs.AI 2013
Year: 2013

By probabilistic logic I mean a normative theory of belief that explains how a body of evidence affects one's degree of belief in a possible hypothesis. A new axiomatization of such a theory is presented which avoids a finite additivity axiom, yet which retains many useful inference rules. Many of the examples of this theory--its models do not use numerical probabilities. Put another way, this article gives sharper answers to the two questions: 1.What kinds of sets can used as the range of a probability function? 2.Under what conditions is the range set of a probability function isomorphic to the set of real numbers in the interval 10,1/ with the usual arithmetical operations?
Hierarchical Evidence and Belief Functions
Venue: arXiv cs.AI 2013
Year: 2013

Dempster/Shafer (D/S) theory has been advocated as a way of representing incompleteness of evidence in a system's knowledge base. Methods now exist for propagating beliefs through chains of inference. This paper discusses how rules with attached beliefs, a common representation for knowledge in automated reasoning systems, can be transformed into the joint belief functions required by propagation algorithms. A rule is taken as defining a conditional belief function on the consequent given the antecedents. It is demonstrated by example that different joint belief functions may be consistent with a given set of rules. Moreover, different representations of the same rules may yield different beliefs on the consequent hypotheses.
A Method for Using Belief Networks as Influence Diagrams
Venue: arXiv cs.AI 2013
Year: 2013

This paper demonstrates a method for using belief-network algorithms to solve influence diagram problems. In particular, both exact and approximation belief-network algorithms may be applied to solve influence-diagram problems. More generally, knowing the relationship between belief-network and influence-diagram problems may be useful in the design and development of more efficient influence diagram algorithms.
On the Logic of Causal Models
Venue: arXiv cs.AI 2013
Year: 2013

This paper explores the role of Directed Acyclic Graphs (DAGs) as a representation of conditional independence relationships. We show that DAGs offer polynomially sound and complete inference mechanisms for inferring conditional independence relationships from a given causal set of such relationships. As a consequence, d-separation, a graphical criterion for identifying independencies in a DAG, is shown to uncover more valid independencies then any other criterion. In addition, we employ the Armstrong property of conditional independence to show that the dependence relationships displayed by a DAG are inherently consistent, i.e. for every DAG D there exists some probability distribution P that embodies all the conditional independencies displayed in D and none other.
Epistemological Relevance and Statistical Knowledge
Venue: arXiv cs.AI 2013
Year: 2013

For many years, at least since McCarthy and Hayes (1969), writers have lamented, and attempted to compensate for, the alleged fact that we often do not have adequate statistical knowledge for governing the uncertainty of belief, for making uncertain inferences, and the like. It is hardly ever spelled out what "adequate statistical knowledge" would be, if we had it, and how adequate statistical knowledge could be used to control and regulate epistemic uncertainty.
Evidential Reasoning in a Network Usage Prediction Testbed
Venue: arXiv cs.AI 2013
Year: 2013

This paper reports on empirical work aimed at comparing evidential reasoning techniques. While there is prima facie evidence for some conclusions, this i6 work in progress; the present focus is methodology, with the goal that subsequent results be meaningful. The domain is a network of UNIX* cycle servers, and the task is to predict properties of the state of the network from partial descriptions of the state. Actual data from the network are taken and used for blindfold testing in a betting game that allows abstention. The focal technique has been Kyburg's method for reasoning with data of varying relevance to a particular query, though the aim is to be able eventually to compare various uncertainty calculi. The conclusions are not novel, but are instructive. 1. All of the calculi performed better than human subjects, so unbiased access to sample experience is apparently of value. 2. Performance depends on metric: (a) when trials are repeated, net = gains - losses favors methods that place many bets, if the probability of placing a correct bet is sufficiently high; that is, it favors point-valued formalisms; (b) yield = gains/(gains + lossee) favors methods that bet only when sure to bet correctly; that is, it favors interval-valued formalisms. 3. Among the calculi, there were no clear winners or losers. Methods are identified for eliminating the bias of the net as a performance criterion and for separating the calculi effectively: in both cases by posting odds for the betting game in the appropriate way.
An Axiomatic Framework for Bayesian and Belief-function Propagation
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we describe an abstract framework and axioms under which exact local computation of marginals is possible. The primitive objects of the framework are variables and valuations. The primitive operators of the framework are combination and marginalization. These operate on valuations. We state three axioms for these operators and we derive the possibility of local computation from the axioms. Next, we describe a propagation scheme for computing marginals of a valuation when we have a factorization of the valuation on a hypertree. Finally we show how the problem of computing marginals of joint probability distributions and joint belief functions fits the general framework.
Nonmonotonic Reasoning via Possibility Theory
Venue: arXiv cs.AI 2013
Year: 2013

We introduce the operation of possibility qualification and show how. this modal-like operator can be used to represent "typical" or default knowledge in a theory of nonmonotonic reasoning. We investigate the representational power of this approach by looking at a number of prototypical problems from the nonmonotonic reasoning literature. In particular we look at the so called Yale shooting problem and its relation to priority in default reasoning.
Generalizing the Dempster-Shafer Theory to Fuzzy Sets
Venue: arXiv cs.AI 2013
Year: 2013

With the desire to apply the Dempster-Shafer theory to complex real world problems where the evidential strength is often imprecise and vague, several attempts have been made to generalize the theory. However, the important concept in the D-S theory that the belief and plausibility functions are lower and upper probabilities is no longer preserved in these generalizations. In this paper, we describe a generalized theory of evidence where the degree of belief in a fuzzy set is obtained by minimizing the probability of the fuzzy set under the constraints imposed by a basic probability assignment. To formulate the probabilistic constraint of a fuzzy focal element, we decompose it into a set of consonant non-fuzzy focal elements. By generalizing the compatibility relation to a possibility theory, we are able to justify our generalization to Dempster's rule based on possibility distribution. Our generalization not only extends the application of the D-S theory but also illustrates a way that probability theory and fuzzy set theory can be combined to deal with different kinds of uncertain information in AI systems.