OpenRaiser/Intern-Atlas huggingface dataset:
Exploring Localization in Bayesian Networks for Large Expert Systems
Venue: arXiv cs.AI 2013
Year: 2013

Current Bayesian net representations do not consider structure in the domain and include all variables in a homogeneous network. At any time, a human reasoner in a large domain may direct his attention to only one of a number of natural subdomains, i.e., there is ?localization' of queries and evidence. In such a case, propagating evidence through a homogeneous network is inefficient since the entire network has to be updated each time. This paper presents multiply sectioned Bayesian networks that enable a (localization preserving) representation of natural subdomains by separate Bayesian subnets. The subnets are transformed into a set of permanent junction trees such that evidential reasoning takes place at only one of them at a time. Probabilities obtained are identical to those that would be obtained from the homogeneous network. We discuss attention shift to a different junction tree and propagation of previously acquired evidence. Although the overall system can be large, computational requirements are governed by the size of only one junction tree.
On active information storage in input-driven systems
Venue: arXiv cs.IT 2013
Year: 2013

Information theory and the framework of information dynamics have been used to provide tools to characterise complex systems. In particular, we are interested in quantifying information storage, information modification and information transfer as characteristic elements of computation. Although these quantities are defined for autonomous dynamical systems, information dynamics can also help to get a "wholistic" understanding of input-driven systems such as neural networks. In this case, we do not distinguish between the system itself, and the effects the input has to the system. This may be desired in some cases, but it will change the questions we are able to answer, and is consequently an important consideration, for example, for biological systems which perform non-trivial computations and also retain a short-term memory of past inputs. Many other real world systems like cortical networks are also heavily input-driven, and application of tools designed for autonomous dynamic systems may not necessarily lead to intuitively interpretable results. The aim of our work is to extend the measurements used in the information dynamics framework for input-driven systems. Using the proposed input-corrected information storage we hope to better quantify system behaviour, which will be important for heavily input-driven systems like artificial neural networks to abstract from specific benchmarks, or for brain networks, where intervention is difficult, individual components cannot be tested in isolation or with arbitrary input data.
Markov random walk under constraint for discovering overlapping communities in complex networks
Venue: arXiv cs.SI 2013
Year: 2013

Detection of overlapping communities in complex networks has motivated recent research in the relevant fields. Aiming this problem, we propose a Markov dynamics based algorithm, called UEOC, which means, 'unfold and extract overlapping communities'. In UEOC, when identifying each natural community that overlaps, a Markov random walk method combined with a constraint strategy, which is based on the corresponding annealed network (degree conserving random network), is performed to unfold the community. Then, a cutoff criterion with the aid of a local community function, called conductance, which can be thought of as the ratio between the number of edges inside the community and those leaving it, is presented to extract this emerged community from the entire network. The UEOC algorithm depends on only one parameter whose value can be easily set, and it requires no prior knowledge on the hidden community structures. The proposed UEOC has been evaluated both on synthetic benchmarks and on some real-world networks, and was compared with a set of competing algorithms. Experimental result has shown that UEOC is highly effective and efficient for discovering overlapping communities.
Symbolic Probabilistic Inference with Evidence Potential
Venue: arXiv cs.AI 2013
Year: 2013

Recent research on the Symbolic Probabilistic Inference (SPI) algorithm[2] has focused attention on the importance of 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. In response to this research we have extended the evidence potential algorithm [3] with the same features. We call the extension symbolic evidence potential inference (SEPI). SEPI like SPI can handle generic queries and is incremental with respect to queries and observations. While in SPI, operations are done on a search tree constructed from the nodes of the original network, in SEPI, a clique-tree structure obtained from the evidence potential algorithm [3] is the basic framework for recursive query processing. In this paper, we describe the systematic query and caching procedure of SEPI. SEPI begins with finding a clique tree from a Bayesian network-the standard procedure of the evidence potential algorithm. With the clique tree, various probability distributions are computed and stored in each clique. This is the ?pre-processing? step of SEPI. Once this step is done, the query can then be computed. To process a query, a recursive process similar to the SPI algorithm is used. The queries are directed to the root clique and decomposed into queries for the clique's subtrees until a particular query can be answered at the clique at which it is directed. The algorithm and the computation are simple. The SEPI algorithm will be presented in this paper along with several examples.
A Bayesian Method for Constructing Bayesian Belief Networks from Databases
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a Bayesian method for constructing Bayesian belief networks from a database of cases. Potential applications include computer-assisted hypothesis testing, automated scientific discovery, and automated construction of probabilistic expert systems. Results are presented of a preliminary evaluation of an algorithm for constructing a belief network from a database of cases. We relate the methods in this paper to previous work, and we discuss open problems.
A Reason Maintenace System Dealing with Vague Data
Venue: arXiv cs.AI 2013
Year: 2013

A reason maintenance system which extends an ATMS through Mukaidono's fuzzy logic is described. It supports a problem solver in situations affected by incomplete information and vague data, by allowing nonmonotonic inferences and the revision of previous conclusions when contradictions are detected.
Dynamic Network Updating Techniques For Diagnostic Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

A new probabilistic network construction system, DYNASTY, is proposed for diagnostic reasoning given variables whose probabilities change over time. Diagnostic reasoning is formulated as a sequential stochastic process, and is modeled using influence diagrams. Given a set O of observations, DYNASTY creates an influence diagram in order to devise the best action given O. Sensitivity analyses are conducted to determine if the best network has been created, given the uncertainty in network parameters and topology. DYNASTY uses an equivalence class approach to provide decision thresholds for the sensitivity analysis. This equivalence-class approach to diagnostic reasoning differentiates diagnoses only if the required actions are different. A set of network-topology updating algorithms are proposed for dynamically updating the network when necessary.
High Level Path Planning with Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

For high level path planning, environments are usually modeled as distance graphs, and path planning problems are reduced to computing the shortest path in distance graphs. One major drawback of this modeling is the inability to model uncertainties, which are often encountered in practice. In this paper, a new tool, called U-yraph, is proposed for environment modeling. A U-graph is an extension of distance graphs with the ability to handle a kind of uncertainty. By modeling an uncertain environment as a U-graph, and a navigation problem as a Markovian decision process, we can precisely define a new optimality criterion for navigation plans, and more importantly, we can come up with a general algorithm for computing optimal plans for navigation tasks.
A Monte-Carlo Algorithm for Dempster-Shafer Belief
Venue: arXiv cs.AI 2013
Year: 2013

A very computationally-efficient Monte-Carlo algorithm for the calculation of Dempster-Shafer belief is described. If Bel is the combination using Dempster's Rule of belief functions Bel, ..., Bel,7, then, for subset b of the frame C), Bel(b) can be calculated in time linear in 1(31 and m (given that the weight of conflict is bounded). The algorithm can also be used to improve the complexity of the Shenoy-Shafer algorithms on Markov trees, and be generalised to calculate Dempster-Shafer Belief over other logics.
Why Do We Need Foundations for Modelling Uncertainties?
Venue: arXiv cs.AI 2013
Year: 2013

Surely we want solid foundations. What kind of castle can we build on sand? What is the point of devoting effort to balconies and minarets, if the foundation may be so weak as to allow the structure to collapse of its own weight? We want our foundations set on bedrock, designed to last for generations. Who would want an architect who cannot certify the soundness of the foundations of his buildings?
Line-Constrained Geometric Server Placement
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we present new algorithmic solutions for several constrained geometric server placement problems. We consider the problems of computing the 1-center and obnoxious 1-center of a set of line segments, constrained to lie on a line segment, and the problem of computing the K-median of a set of points, constrained to lie on a line. The presented algorithms have applications in many types of distributed systems, as well as in various fields which make use of distributed systems for running some of their applications (like chemistry, metallurgy, physics, etc.).
Efficient Online Algorithmic Strategies for Several Two-Player Games with Different or Identical Player Roles
Venue: arXiv cs.GT 2013
Year: 2013

In this paper we introduce novel algorithmic strategies for effciently playing two-player games in which the players have different or identical player roles. In the case of identical roles, the players compete for the same objective (that of winning the game). The case with different player roles assumes that one of the players asks questions in order to identify a secret pattern and the other one answers them. The purpose of the first player is to ask as few questions as possible (or that the questions and their number satisfy some previously known constraints) and the purpose of the secret player is to answer the questions in a way that will maximize the number of questions asked by the first player (or in a way which forces the first player to break the constraints of the game). We consider both previously known games (or extensions of theirs) and new types of games, introduced in this paper.
Multilevel communication optimal LU and QR factorizations for hierarchical platforms
Venue: arXiv cs.DC 2013
Year: 2013

This study focuses on the performance of two classical dense linear algebra algorithms, the LU and the QR factorizations, on multilevel hierarchical platforms. We first introduce a new model called Hierarchical Cluster Platform (HCP), encapsulating the characteristics of such platforms. The focus is set on reducing the communication requirements of studied algorithms at each level of the hierarchy. Lower bounds on communications are therefore extended with respect to the HCP model. We then introduce multilevel LU and QR algorithms tailored for those platforms, and provide a detailed performance analysis. We also provide a set of numerical experiments and performance predictions demonstrating the need for such algorithms on large platforms.
BIMS: Biomedical Information Management System
Venue: arXiv cs.SE 2013
Year: 2013

In this paper, we present BIMS (Biomedical Information Management System). BIMS is a software architecture designed to provide a flexible computational framework to manage the information needs of a wide range of biomedical research projects. The main goal is to facilitate the clinicians' job in data entry, and researcher's tasks in data management, in high data quality biomedical research projects. The BIMS architecture has been designed following the two-level modeling paradigm, a promising methodology to model rich and dynamic information environments. In addition, a functional implementation of BIMS architecture has been developed as a web-based application. The result is a highly flexible web application which allows modeling and managing large amounts of heterogeneous biomedical data sets, both textual as well as visual (medical images) information.
A Cooperation Model Towards the Federated Internet of Applications
Venue: arXiv cs.CY 2013
Year: 2013

As Internet is changing from network of data into network of functionalities, a federated Internet of applications, that every application can cooperate with each other smoothly, is a natural trending topic. However, existing integration techniques did not pay enough attention to multiple control domains for participants, i.e. application providers and end-users. In this study, we advocate a global cooperation model for all the participants counts. In particular, we propose a hybrid model to manage the cooperation among applications to achieve more optimized allocation of efforts, which means users perform lighter actions and application providers concerning less uncontrollable information. In addition, we implement the required system and show a case study which demonstrates the effectiveness of this model.
vSkyConf: Cloud-assisted Multi-party Mobile Video Conferencing
Venue: arXiv cs.NI 2013
Year: 2013

As an important application in the busy world today, mobile video conferencing facilitates virtual face-to-face communication with friends, families and colleagues, via their mobile devices on the move. However, how to provision high-quality, multi-party video conferencing experiences over mobile devices is still an open challenge. The fundamental reason behind is the lack of computation and communication capacities on the mobile devices, to scale to large conferencing sessions. In this paper, we present vSkyConf, a cloud-assisted mobile video conferencing system to fundamentally improve the quality and scale of multi-party mobile video conferencing. By novelly employing a surrogate virtual machine in the cloud for each mobile user, we allow fully scalable communication among the conference participants via their surrogates, rather than directly. The surrogates exchange conferencing streams among each other, transcode the streams to the most appropriate bit rates, and buffer the streams for the most efficient delivery to the mobile recipients. A fully decentralized, optimal algorithm is designed to decide the best paths of streams and the most suitable surrogates for video transcoding along the paths, such that the limited bandwidth is fully utilized to deliver streams of the highest possible quality to the mobile recipients. We also carefully tailor a buffering mechanism on each surrogate to cooperate with optimal stream distribution. We have implemented vSkyConf based on Amazon EC2 and verified the excellent performance of our design, as compared to the widely adopted unicast solutions.
Modelling and analysing relations between entities using the multi-agents and social network approaches
Venue: arXiv cs.SI 2013
Year: 2013

In this work, the concept of a system for analysing social relations between entities using the social network analysis and multi-agent system approaches is presented. The following problems especially appear within the domain of our interests: identification of the most influential individuals in a given society, identification of roles played by the given individuals in that society and the recognition of groups of individuals strongly connected with one another. For the analysis of these problems, two application domains are selected: an analysis of data regarding phone calls and analysis of Internet Weblogs.
Particles Prefer Walking Along the Axes: Experimental Insights into the Behavior of a Particle Swarm
Venue: arXiv cs.NE 2013
Year: 2013

Particle swarm optimization (PSO) is a widely used nature-inspired meta-heuristic for solving continuous optimization problems. However, when running the PSO algorithm, one encounters the phenomenon of so-called stagnation, that means in our context, the whole swarm starts to converge to a solution that is not (even a local) optimum. The goal of this work is to point out possible reasons why the swarm stagnates at these non-optimal points. To achieve our results, we use the newly defined potential of a swarm. The total potential has a portion for every dimension of the search space, and it drops when the swarm approaches the point of convergence. As it turns out experimentally, the swarm is very likely to come sometimes into "unbalanced" states, i. e., almost all potential belongs to one axis. Therefore, the swarm becomes blind for improvements still possible in any other direction. Finally, we show how in the light of the potential and these observations, a slightly adapted PSO rebalances the potential and therefore increases the quality of the solution.
Principle "synthesis" for the solution of tasks of class NP
Venue: arXiv cs.OH 2013
Year: 2013

Initial contours of the non-standard approach to reception of the answer of any task on discrete structures are considered: the algorithm independently creates such answer from separate fragments.
Numerical model of elastic laminated glass beams under finite strain
Venue: arXiv cs.CE 2013
Year: 2013

Laminated glass structures are formed by stiff layers of glass connected with a compliant plastic interlayer. Due to their slenderness and heterogeneity, they exhibit a complex mechanical response that is difficult to capture by single-layer models even in the elastic range. The purpose of this paper is to introduce an efficient and reliable finite element approach to the simulation of the immediate response of laminated glass beams. It proceeds from a refined plate theory due to Mau (1973), as we treat each layer independently and enforce the compatibility by the Lagrange multipliers. At the layer level, we adopt the finite-strain shear deformable formulation of Reissner (1972) and the numerical framework by Ibrahimbegović and Frey (1993). The resulting system is solved by the Newton method with consistent linearization. By comparing the model predictions against available experimental data, analytical methods and two-dimensional finite element simulations, we demonstrate that the proposed formulation is reliable and provides accuracy comparable to the detailed two-dimensional finite element analyzes. As such, it offers a convenient basis to incorporate more refined constitutive description of the interlayer.
Video Face Matching using Subset Selection and Clustering of Probabilistic Multi-Region Histograms
Venue: arXiv cs.CV 2013
Year: 2013

Balancing computational efficiency with recognition accuracy is one of the major challenges in real-world video-based face recognition. A significant design decision for any such system is whether to process and use all possible faces detected over the video frames, or whether to select only a few "best" faces. This paper presents a video face recognition system based on probabilistic Multi-Region Histograms to characterise performance trade-offs in: (i) selecting a subset of faces compared to using all faces, and (ii) combining information from all faces via clustering. Three face selection metrics are evaluated for choosing a subset: face detection confidence, random subset, and sequential selection. Experiments on the recently introduced MOBIO dataset indicate that the usage of all faces through clustering always outperformed selecting only a subset of faces. The experiments also show that the face selection metric based on face detection confidence generally provides better recognition performance than random or sequential sampling. Moreover, the optimal number of faces varies drastically across selection metric and subsets of MOBIO. Given the trade-offs between computational effort, recognition accuracy and robustness, it is recommended that face feature clustering would be most advantageous in batch processing (particularly for video-based watchlists), whereas face selection methods should be limited to applications with significant computational restrictions.
Detecting Friendship Within Dynamic Online Interaction Networks
Venue: arXiv cs.SI 2013
Year: 2013

In many complex social systems, the timing and frequency of interactions between individuals are observable but friendship ties are hidden. Recovering these hidden ties, particularly for casual users who are relatively less active, would enable a wide variety of friendship-aware applications in domains where labeled data are often unavailable, including online advertising and national security. Here, we investigate the accuracy of multiple statistical features, based either purely on temporal interaction patterns or on the cooperative nature of the interactions, for automatically extracting latent social ties. Using self-reported friendship and non-friendship labels derived from an anonymous online survey, we learn highly accurate predictors for recovering hidden friendships within a massive online data set encompassing 18 billion interactions among 17 million individuals of the popular online game Halo: Reach. We find that the accuracy of many features improves as more data accumulates, and cooperative features are generally reliable. However, periodicities in interaction time series are sufficient to correctly classify 95% of ties, even for casual users. These results clarify the nature of friendship in online social environments and suggest new opportunities and new privacy concerns for friendship-aware applications that do not require the disclosure of private friendship information.
Phase Transition Analysis of Sparse Support Detection from Noisy Measurements
Venue: arXiv cs.IT 2013
Year: 2013

This paper investigates the problem of sparse support detection (SSD) via a detection-oriented algorithm named Bayesian hypothesis test via belief propagation (BHT-BP). Our main focus is to compare BHT-BP to an estimation-based algorithm, called CS-BP, and show its superiority in the SSD problem. For this investigation, we perform a phase transition (PT) analysis over the plain of the noise level and signal magnitude on the signal support. This PT analysis sharply specifies the required signal magnitude for the detection under a certain noise level. In addition, we provide an experimental validation to assure the PT analysis. Our analytical and experimental results show the fact that BHT-BP detects the signal support against additive noise more robustly than CS-BP does.
New Inapproximability Bounds for TSP
Venue: arXiv cs.CC 2013
Year: 2013

In this paper, we study the approximability of the metric Traveling Salesman Problem (TSP) and prove new explicit inapproximability bounds for that problem. The best up to now known hardness of approximation bounds were 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and Vempala). We construct here two new bounded occurrence CSP reductions which improve these bounds to 123/122 and 75/74, respectively. The latter bound is the first improvement in more than a decade for the case of the asymmetric TSP. One of our main tools, which may be of independent interest, is a new construction of a bounded degree wheel amplifier used in the proof of our results.