OpenRaiser/Intern-Atlas huggingface dataset:
Generalizing Jeffrey Conditionalization
Venue: arXiv cs.AI 2013
Year: 2013

Jeffrey's rule has been generalized by Wagner to the case in which new evidence bounds the possible revisions of a prior probability below by a Dempsterian lower probability. Classical probability kinematics arises within this generalization as the special case in which the evidentiary focal elements of the bounding lower probability are pairwise disjoint. We discuss a twofold extension of this generalization, first allowing the lower bound to be any two-monotone capacity and then allowing the prior to be a lower envelope.
A Decision Calculus for Belief Functions in Valuation-Based Systems
Venue: arXiv cs.AI 2013
Year: 2013

Valuation-based system (VBS) provides a general framework for representing knowledge and drawing inferences under uncertainty. Recent studies have shown that the semantics of VBS can represent and solve Bayesian decision problems (Shenoy, 1991a). The purpose of this paper is to propose a decision calculus for Dempster-Shafer (D-S) theory in the framework of VBS. The proposed calculus uses a weighting factor whose role is similar to the probabilistic interpretation of an assumption that disambiguates decision problems represented with belief functions (Strat 1990). It will be shown that with the presented calculus, if the decision problems are represented in the valuation network properly, we can solve the problems by using fusion algorithm (Shenoy 1991a). It will also be shown the presented decision calculus can be reduced to the calculus for Bayesian probability theory when probabilities, instead of belief functions, are given.
Adverse Conditions and ASR Techniques for Robust Speech User Interface
Venue: arXiv cs.CL 2013
Year: 2013

The main motivation for Automatic Speech Recognition (ASR) is efficient interfaces to computers, and for the interfaces to be natural and truly useful, it should provide coverage for a large group of users. The purpose of these tasks is to further improve man-machine communication. ASR systems exhibit unacceptable degradations in performance when the acoustical environments used for training and testing the system are not the same. The goal of this research is to increase the robustness of the speech recognition systems with respect to changes in the environment. A system can be labeled as environment-independent if the recognition accuracy for a new environment is the same or higher than that obtained when the system is retrained for that environment. Attaining such performance is the dream of the researchers. This paper elaborates some of the difficulties with Automatic Speech Recognition (ASR). These difficulties are classified into Speakers characteristics and environmental conditions, and tried to suggest some techniques to compensate variations in speech signal. This paper focuses on the robustness with respect to speakers variations and changes in the acoustical environment. We discussed several different external factors that change the environment and physiological differences that affect the performance of a speech recognition system followed by techniques that are helpful to design a robust ASR system.
Lowering the Barrier to Reuse through Test-Driven Search
Venue: arXiv cs.SE 2013
Year: 2013

Dedicated software search engines that index open source software repositories or in-house software assets significantly enhance the chance of finding software components suitable for reuse. However, they still leave the work of evaluating and testing components to the developer. To significantly change the risk-cost-benefit tradeoff involved in software reuse, search engines need to be supported by user friendly environments that deliver code search functionality non-intrusively right to developers' fingertips.
Viterbi training in PRISM
Venue: arXiv cs.AI 2013
Year: 2013

VT (Viterbi training), or hard EM, is an efficient way of parameter learning for probabilistic models with hidden variables. Given an observation $y$, it searches for a state of hidden variables $x$ that maximizes $p(x,y \mid θ)$ by coordinate ascent on parameters $θ$ and $x$. In this paper we introduce VT to PRISM, a logic-based probabilistic modeling system for generative models. VT improves PRISM in three ways. First VT in PRISM converges faster than EM in PRISM due to the VT's termination condition. Second, parameters learned by VT often show good prediction performance compared to those learned by EM. We conducted two parsing experiments with probabilistic grammars while learning parameters by a variety of inference methods, i.e.\ VT, EM, MAP and VB. The result is that VT achieved the best parsing accuracy among them in both experiments. Also we conducted a similar experiment for classification tasks where a hidden variable is not a prediction target unlike probabilistic grammars. We found that in such a case VT does not necessarily yield superior performance. Third since VT always deals with a single probability of a single explanation, Viterbi explanation, the exclusiveness condition that is imposed on PRISM programs is no more required if we learn parameters by VT. Last but not least we can say that as VT in PRISM is general and applicable to any PRISM program, it largely reduces the need for the user to develop a specific VT algorithm for a specific model. Furthermore since VT in PRISM can be used just by setting a PRISM flag appropriately, it makes VT easily accessible to (probabilistic) logic programmers. To appear in Theory and Practice of Logic Programming (TPLP).
Symbolic Probabilistic Inference with Continuous Variables
Venue: arXiv cs.AI 2013
Year: 2013

Research on Symbolic Probabilistic Inference (SPI) [2, 3] has provided an algorithm for resolving general queries in Bayesian networks. SPI applies the concept of dependency directed backward search to probabilistic inference, and is incremental with respect to both queries and observations. Unlike traditional Bayesian network inferencing algorithms, SPI algorithm is goal directed, performing only those calculations that are required to respond to queries. Research to date on SPI applies to Bayesian networks with discrete-valued variables and does not address variables with continuous values. In this papers, we extend the SPI algorithm to handle Bayesian networks made up of continuous variables where the relationships between the variables are restricted to be ?linear gaussian?. We call this variation of the SPI algorithm, SPI Continuous (SPIC). SPIC modifies the three basic SPI operations: multiplication, summation, and substitution. However, SPIC retains the framework of the SPI algorithm, namely building the search tree and recursive query mechanism and therefore retains the goal-directed and incrementality features of SPI.
Belief and Surprise - A Belief-Function Formulation
Venue: arXiv cs.AI 2013
Year: 2013

We motivate and describe a theory of belief in this paper. This theory is developed with the following view of human belief in mind. Consider the belief that an event E will occur (or has occurred or is occurring). An agent either entertains this belief or does not entertain this belief (i.e., there is no "grade" in entertaining the belief). If the agent chooses to exercise "the will to believe" and entertain this belief, he/she/it is entitled to a degree of confidence c (1 > c > 0) in doing so. Adopting this view of human belief, we conjecture that whenever an agent entertains the belief that E will occur with c degree of confidence, the agent will be surprised (to the extent c) upon realizing that E did not occur.
Representation Requirements for Supporting Decision Model Formulation
Venue: arXiv cs.AI 2013
Year: 2013

This paper outlines a methodology for analyzing the representational support for knowledge-based decision-modeling in a broad domain. A relevant set of inference patterns and knowledge types are identified. By comparing the analysis results to existing representations, some insights are gained into a design approach for integrating categorical and uncertain knowledge in a context sensitive manner.
Non-monotonic Negation in Probabilistic Deductive Databases
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we study the uses and the semantics of non-monotonic negation in probabilistic deductive data bases. Based on the stable semantics for classical logic programming, we introduce the notion of stable formula, functions. We show that stable formula, functions are minimal fixpoints of operators associated with probabilistic deductive databases with negation. Furthermore, since a. probabilistic deductive database may not necessarily have a stable formula function, we provide a stable class semantics for such databases. Finally, we demonstrate that the proposed semantics can handle default reasoning naturally in the context of probabilistic deduction.
Integrating Probabilistic Rules into Neural Networks: A Stochastic EM Learning Algorithm
Venue: arXiv cs.AI 2013
Year: 2013

The EM-algorithm is a general procedure to get maximum likelihood estimates if part of the observations on the variables of a network are missing. In this paper a stochastic version of the algorithm is adapted to probabilistic neural networks describing the associative dependency of variables. These networks have a probability distribution, which is a special case of the distribution generated by probabilistic inference networks. Hence both types of networks can be combined allowing to integrate probabilistic rules as well as unspecified associations in a sound way. The resulting network may have a number of interesting features including cycles of probabilistic rules, hidden 'unobservable' variables, and uncertain and contradictory evidence.
Algorithms for Irrelevance-Based Partial MAPs
Venue: arXiv cs.AI 2013
Year: 2013

Irrelevance-based partial MAPs are useful constructs for domain-independent explanation using belief networks. We look at two definitions for such partial MAPs, and prove important properties that are useful in designing algorithms for computing them effectively. We make use of these properties in modifying our standard MAP best-first algorithm, so as to handle irrelevance-based partial MAPs.
About Updating
Venue: arXiv cs.AI 2013
Year: 2013

Survey of several forms of updating, with a practical illustrative example. We study several updating (conditioning) schemes that emerge naturally from a common scenarion to provide some insights into their meaning. Updating is a subtle operation and there is no single method, no single 'good' rule. The choice of the appropriate rule must always be given due consideration. Planchet (1989) presents a mathematical survey of many rules. We focus on the practical meaning of these rules. After summarizing the several rules for conditioning, we present an illustrative example in which the various forms of conditioning can be explained.
An Efficient Implementation of Belief Function Propagation
Venue: arXiv cs.AI 2013
Year: 2013

The local computation technique (Shafer et al. 1987, Shafer and Shenoy 1988, Shenoy and Shafer 1986) is used for propagating belief functions in so called a Markov Tree. In this paper, we describe an efficient implementation of belief function propagation on the basis of the local computation technique. The presented method avoids all the redundant computations in the propagation process, and so makes the computational complexity decrease with respect to other existing implementations (Hsia and Shenoy 1989, Zarley et al. 1988). We also give a combined algorithm for both propagation and re-propagation which makes the re-propagation process more efficient when one or more of the prior belief functions is changed.
Object-oriented approach to Rapid Custom Instruction design
Venue: arXiv cs.AR 2013
Year: 2013

Due to continuous evolution of Systems-on-Chip (SoC), the complexity of their design and development has augmented exponentially. To deal with the ever-growing complexity of such embedded systems, we introduce, in this paper, an object-oriented approach to rapid SoC design using auto-generation of hardware custom instructions to simplify and accelerate the SoC design process. In our approach, a Data Flow Graph (DFG) is adopted as a representation of the arithmetic operation to convert it to a custom instruction. Then VHDL code will be automatically generated. The input C code is automatically updated for calling the new hardware components. To prove the effectiveness of the proposed approach, a Java source code framework named Automatic Custom Architecture generator (ACAgen) is developed. Experimental results on 3D sample application validate our approach and demonstrate how the proposed framework facilitates and accelerates the SoC design process at low costs.
Live music programming in Haskell
Venue: arXiv cs.PL 2013
Year: 2013

We aim for composing algorithmic music in an interactive way with multiple participants. To this end we have developed an interpreter for a sub-language of the non-strict functional programming language Haskell that allows the modification of a program during its execution. Our system can be used both for musical live-coding and for demonstration and education of functional programming.
Clustering Based Lifetime Maximizing Aggregation Tree for Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Energy efficiency is the most important issue in all facets of wireless sensor networks (WSNs) operations because of the limited and non-replenish able energy supply. Data aggregation mechanism is one of the possible solutions to prolong the life time of sensor nodes and on the other hand it also helps in eliminating the data redundancy and improving the accuracy of information gathering, is essential for WSNs. In this paper we propose a Clustering based lifetime maximizing aggregation tree (CLMAT) in which we create aggregation tree which aim to reduce energy consumption, minimizing the distance traversed and minimizing the cost in terms of energy consumption. In CLMAT the node having maximum available energy is used as parent node/ aggregator node. We concluded with the best possible aggregation tree minimizing energy utilization, minimizing cost and hence maximizing network lifetime.
Improved Approximation Algorithm for the Number of Queries Necessary to Identify a Permutation
Venue: arXiv cs.DS 2013
Year: 2013

In the past three decades, deductive games have become interesting from the algorithmic point of view. Deductive games are two players zero sum games of imperfect information. The first player, called "codemaker", chooses a secret code and the second player, called "codebreaker", tries to break the secret code by making as few guesses as possible, exploiting information that is given by the codemaker after each guess. A well known deductive game is the famous Mastermind game. In this paper, we consider the so called Black-Peg variant of Mastermind, where the only information concerning a guess is the number of positions in which the guess coincides with the secret code. More precisely, we deal with a special version of the Black-Peg game with n holes and k >= n colors where no repetition of colors is allowed. We present a strategy that identifies the secret code in O(n log n) queries. Our algorithm improves the previous result of Ker-I Ko and Shia-Chung Teng (1985) by almost a factor of 2 for the case k = n. To our knowledge there is no previous work dealing with the case k > n. Keywords: Mastermind; combinatorial problems; permutations; algorithms
Simulating Resilience in Transaction-Oriented Networks
Venue: arXiv cs.DC 2013
Year: 2013

The power of networks manifests itself in a highly non-linear amplification of a number of effects, and their weakness - in propagation of cascading failures. The potential systemic risk effects can be either exacerbated or mitigated, depending on the resilience characteristics of the network. The goals of this paper are to study some characteristics of network amplification and resilience. We simulate random Erdos-Renyi networks and measure amplification by varying node capacity, transaction volume, and expected failure rates. We discover that network throughput scales almost quadratically with respect to the node capacity and that the effects of excessive network load and random and irreparable node faults are equivalent and almost perfectly anticorrelated. This knowledge can be used by capacity planners to determine optimal reliability requirements that maximize the optimal operational regions.
Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks
Venue: arXiv cs.SI 2013
Year: 2013

In order to further improve the performance of current genetic algorithms aiming at discovering communities, a local search based genetic algorithm GALS is here proposed. The core of GALS is a local search based mutation technique. In order to overcome the drawbacks of traditional mutation methods, the paper develops the concept of marginal gene and then the local monotonicity of modularity function Q is deduced from each nodes local view. Based on these two elements, a new mutation method combined with a local search strategy is presented. GALS has been evaluated on both synthetic benchmarks and several real networks, and compared with some presently competing algorithms. Experimental results show that GALS is highly effective and efficient for discovering community structure.
STC: Semantic Taxonomical Clustering for Service Category Learning
Venue: arXiv cs.SE 2013
Year: 2013

Service discovery is one of the key problems that has been widely researched in the area of Service Oriented Architecture (SOA) based systems. Service category learning is a technique for efficiently facilitating service discovery. Most approaches for service category learning are based on suitable similarity distance measures using thresholds. Threshold selection is essentially difficult and often leads to unsatisfactory accuracy. In this paper, we have proposed a self-organizing based clustering algorithm called Semantic Taxonomical Clustering (STC) for taxonomically organizing services with self-organizing information and knowledge. We have tested the STC algorithm on both randomly generated data and the standard OWL-S TC dataset. We have observed promising results both in terms of classification accuracy and runtime performance compared to existing approaches.
The Two Paradigms of Software Design
Venue: arXiv cs.SE 2013
Year: 2013

The dominant view of design in information systems and software engineering, the Rational Design Paradigm, views software development as a methodical, plan-centered, approximately rational process of optimizing a design candidate for known constraints and objectives. This paper synthesizes an Alternative Design Paradigm, which views software development as an amethodical, improvisational, emotional process of simultaneously framing the problem and building artifacts to address it. These conflicting paradigms are manifestations of a deeper philosophical conflict between rationalism and empiricism. The paper clarifies the nature, components and assumptions of each paradigm and explores the implications of the paradigmatic conflict for research, practice and education.
Automorphisms of Cayley graphs generated by transposition sets
Venue: arXiv cs.DM 2013
Year: 2013

Let $S$ be a set of transpositions such that the girth of the transposition graph of $S$ is at least 5. It is shown that the automorphism group of the Cayley graph of the permutation group $H$ generated by $S$ is the semidirect product $R(H) \rtimes \Aut(H,S)$, where $R(H)$ is the right regular representation of $H$ and $\Aut(H,S)$ is the set of automorphisms of $H$ that fixes $S$ setwise. Furthermore, if the connected components of the transposition graph of $S$ are isomorphic to each other, then $\Aut(H,S)$ is isomorphic to the automorphism group of the line graph of the transposition graph of $S$. This result is a common generalization of previous results by Feng, Ganesan, Harary, Mirafzal, and Zhang and Huang. As another special case, we obtain the automorphism group of the extended cube graph that was proposed as a topology for interconnection networks.
Generalizing k-means for an arbitrary distance matrix
Venue: arXiv cs.LG 2013
Year: 2013

The original k-means clustering method works only if the exact vectors representing the data points are known. Therefore calculating the distances from the centroids needs vector operations, since the average of abstract data points is undefined. Existing algorithms can be extended for those cases when the sole input is the distance matrix, and the exact representing vectors are unknown. This extension may be named relational k-means after a notation for a similar algorithm invented for fuzzy clustering. A method is then proposed for generalizing k-means for scenarios when the data points have absolutely no connection with a Euclidean space.
Dynamics of Trust Reciprocation in Heterogenous MMOG Networks
Venue: arXiv cs.SI 2013
Year: 2013

Understanding the dynamics of reciprocation is of great interest in sociology and computational social science. The recent growth of Massively Multi-player Online Games (MMOGs) has provided unprecedented access to large-scale data which enables us to study such complex human behavior in a more systematic manner. In this paper, we consider three different networks in the EverQuest2 game: chat, trade, and trust. The chat network has the highest level of reciprocation (33%) because there are essentially no barriers to it. The trade network has a lower rate of reciprocation (27%) because it has the obvious barrier of requiring more goods or money for exchange; morever, there is no clear benefit to returning a trade link except in terms of social connections. The trust network has the lowest reciprocation (14%) because this equates to sharing certain within-game assets such as weapons, and so there is a high barrier for such connections because they require faith in the players that are granted such high access. In general, we observe that reciprocation rate is inversely related to the barrier level in these networks. We also note that reciprocation has connections across the heterogeneous networks. Our experiments indicate that players make use of the medium-barrier reciprocations to strengthen a relationship. We hypothesize that lower-barrier interactions are an important component to predicting higher-barrier ones. We verify our hypothesis using predictive models for trust reciprocations using features from trade interactions. Using the number of trades (both before and after the initial trust link) boosts our ability to predict if the trust will be reciprocated up to 11% with respect to the AUC.
Random Discrete Morse Theory and a New Library of Triangulations
Venue: arXiv cs.CG 2013
Year: 2013

1) We introduce random discrete Morse theory as a computational scheme to measure the complicatedness of a triangulation. The idea is to try to quantify the frequence of discrete Morse matchings with a certain number of critical cells. Our measure will depend on the topology of the space, but also on how nicely the space is triangulated. (2) The scheme we propose looks for optimal discrete Morse functions with an elementary random heuristic. Despite its naïveté, this approach turns out to be very successful even in the case of huge inputs. (3) In our view the existing libraries of examples in computational topology are `too easy' for testing algorithms based on discrete Morse theory. We propose a new library containing more complicated (and thus more meaningful) test examples.