OpenRaiser/Intern-Atlas huggingface dataset:
GALGO: A Genetic ALGOrithm Decision Support Tool for Complex Uncertain Systems Modeled with Bayesian Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

Bayesian belief networks can be used to represent and to reason about complex systems with uncertain, incomplete and conflicting information. Belief networks are graphs encoding and quantifying probabilistic dependence and conditional independence among variables. One type of reasoning of interest in diagnosis is called abductive inference (determination of the global most probable system description given the values of any partial subset of variables). In some cases, abductive inference can be performed with exact algorithms using distributed network computations but it is an NP-hard problem and complexity increases drastically with the presence of undirected cycles, number of discrete states per variable, and number of variables in the network. This paper describes an approximate method based on genetic algorithms to perform abductive inference in large, multiply connected networks for which complexity is a concern when using most exact methods and for which systematic search methods are not feasible. The theoretical adequacy of the method is discussed and preliminary experimental results are presented.
Deciding Morality of Graphs is NP-complete
Venue: arXiv cs.AI 2013
Year: 2013

In order to find a causal explanation for data presented in the form of covariance and concentration matrices it is necessary to decide if the graph formed by such associations is a projection of a directed acyclic graph (dag). We show that the general problem of deciding whether such a dag exists is NP-complete.
Probabilistic Assumption-Based Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

The classical propositional assumption-based model is extended to incorporate probabilities for the assumptions. Then it is placed into the framework of evidence theory. Several authors like Laskey, Lehner (1989) and Provan (1990) already proposed a similar point of view, but the first paper is not as much concerned with mathematical foundations, and Provan's paper develops into a different direction. Here we thoroughly develop and present the mathematical foundations of this theory, together with computational methods adapted from Reiter, De Kleer (1987) and Inoue (1992). Finally, recently proposed techniques for computing degrees of support are presented.
Partially Specified Belief Functions
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a procedure to determine a complete belief function from the known values of belief for some of the subsets of the frame of discerment. The method is based on the principle of minimum commitment and a new principle called the focusing principle. This additional principle is based on the idea that belief is specified for the most relevant sets: the focal elements. The resulting procedure is compared with existing methods of building complete belief functions: the minimum specificity principle and the least commitment principle.
A Belief-Function Based Decision Support System
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we present a decision support system based on belief functions and the pignistic transformation. The system is an integration of an evidential system for belief function propagation and a valuation-based system for Bayesian decision analysis. The two subsystems are connected through the pignistic transformation. The system takes as inputs the user's "gut feelings" about a situation and suggests what, if any, are to be tested and in what order, and it does so with a user friendly interface.
Queuing Theoretic Analysis of Power-performance Tradeoff in Power-efficient Computing
Venue: arXiv cs.PF 2013
Year: 2013

In this paper we study the power-performance relationship of power-efficient computing from a queuing theoretic perspective. We investigate the interplay of several system operations including processing speed, system on/off decisions, and server farm size. We identify that there are oftentimes "sweet spots" in power-efficient operations: there exist optimal combinations of processing speed and system settings that maximize power efficiency. For the single server case, a widely deployed threshold mechanism is studied. We show that there exist optimal processing speed and threshold value pairs that minimize the power consumption. This holds for the threshold mechanism with job batching. For the multi-server case, it is shown that there exist best processing speed and server farm size combinations.
Reduced-rank Adaptive Constrained Constant Modulus Beamforming Algorithms based on Joint Iterative Optimization of Filters
Venue: arXiv cs.IT 2013
Year: 2013

This paper proposes a reduced-rank scheme for adaptive beamforming based on the constrained joint iterative optimization of filters. We employ this scheme to devise two novel reduced-rank adaptive algorithms according to the constant modulus (CM) criterion with different constraints. The first devised algorithm is formulated as a constrained joint iterative optimization of a projection matrix and a reduced-rank filter with respect to the CM criterion subject to a constraint on the array response. The constrained constant modulus (CCM) expressions for the projection matrix and the reduced-rank weight vector are derived, and a low-complexity adaptive algorithm is presented to jointly estimate them for implementation. The second proposed algorithm is extended from the first one and implemented according to the CM criterion subject to a constraint on the array response and an orthogonal constraint on the projection matrix. The Gram-Schmidt (GS) technique is employed to achieve this orthogonal constraint and improve the performance. Simulation results are given to show superior performance of the proposed algorithms in comparison with existing methods.
A Multi-objective Perspective for Operator Scheduling using Fine-grained DVS Architecture
Venue: arXiv cs.OH 2013
Year: 2013

The stringent power budget of fine grained power managed digital integrated circuits have driven chip designers to optimize power at the cost of area and delay, which were the traditional cost criteria for circuit optimization. The emerging scenario motivates us to revisit the classical operator scheduling problem under the availability of DVFS enabled functional units that can trade-off cycles with power. We study the design space defined due to this trade-off and present a branch-and-bound(B/B) algorithm to explore this state space and report the pareto-optimal front with respect to area and power. The scheduling also aims at maximum resource sharing and is able to attain sufficient area and power gains for complex benchmarks when timing constraints are relaxed by sufficient amount. Experimental results show that the algorithm that operates without any user constraint(area/power) is able to solve the problem for most available benchmarks, and the use of power budget or area budget constraints leads to significant performance gain.
False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time
Venue: arXiv cs.GT 2013
Year: 2013

False-name manipulation refers to the question of whether a player in a weighted voting game can increase her power by splitting into several players and distributing her weight among these false identities. Analogously to this splitting problem, the beneficial merging problem asks whether a coalition of players can increase their power in a weighted voting game by merging their weights. Aziz et al. [ABEP11] analyze the problem of whether merging or splitting players in weighted voting games is beneficial in terms of the Shapley-Shubik and the normalized Banzhaf index, and so do Rey and Rothe [RR10] for the probabilistic Banzhaf index. All these results provide merely NP-hardness lower bounds for these problems, leaving the question about their exact complexity open. For the Shapley--Shubik and the probabilistic Banzhaf index, we raise these lower bounds to hardness for PP, "probabilistic polynomial time", and provide matching upper bounds for beneficial merging and, whenever the number of false identities is fixed, also for beneficial splitting, thus resolving previous conjectures in the affirmative. It follows from our results that beneficial merging and splitting for these two power indices cannot be solved in NP, unless the polynomial hierarchy collapses, which is considered highly unlikely.
Effect of Query Formation on Web Search Engine Results
Venue: arXiv cs.IR 2013
Year: 2013

Query in a search engine is generally based on natural language. A query can be expressed in more than one way without changing its meaning as it depends on thinking of human being at a particular moment. Aim of the searcher is to get most relevant results immaterial of how the query has been expressed. In the present paper, we have examined the results of search engine for change in coverage and similarity of first few results when a query is entered in two semantically same but in different formats. Searching has been made through Google search engine. Fifteen pairs of queries have been chosen for the study. The t-test has been used for the purpose and the results have been checked on the basis of total documents found, similarity of first five and first ten documents found in the results of a query entered in two different formats. It has been found that the total coverage is same but first few results are significantly different.
Concept-based indexing in text information retrieval
Venue: arXiv cs.IR 2013
Year: 2013

Traditional information retrieval systems rely on keywords to index documents and queries. In such systems, documents are retrieved based on the number of shared keywords with the query. This lexical-focused retrieval leads to inaccurate and incomplete results when different keywords are used to describe the documents and queries. Semantic-focused retrieval approaches attempt to overcome this problem by relying on concepts rather than on keywords to indexing and retrieval. The goal is to retrieve documents that are semantically relevant to a given user query. This paper addresses this issue by proposing a solution at the indexing level. More precisely, we propose a novel approach for semantic indexing based on concepts identified from a linguistic resource. In particular, our approach relies on the joint use of WordNet and WordNetDomains lexical databases for concept identification. Furthermore, we propose a semantic-based concept weighting scheme that relies on a novel definition of concept centrality. The resulting system is evaluated on the TIME test collection. Experimental results show the effectiveness of our proposition over traditional IR approaches.
Three Layer Hierarchical Model for Chord
Venue: arXiv cs.NI 2013
Year: 2013

Increasing popularity of decentralized P2P architecture emphasizes on the need to come across an overlay structure that can provide efficient content discovery mechanism, accommodate high churn rate and adapt to failures. Traditional p2p systems are not able to solve the problems relating scalability and high churn rates. Hierarchical model were introduced to provide better fault isolation, effective bandwidth utilization, a superior adaptation to the underlying physical network and a reduction of the lookup path length as additional advantages. It is more efficient and easier to manage than traditional p2p networks. This paper discusses a further step in p2p hierarchy via 3-layers hierarchical model with distributed database architecture in different layer, each of which is connected through its root. The peers are divided into three categories according to their physical stability and strength. They are Ultra Super-peer, Super-peer and Ordinary Peer and we assign these peers to first, second and third level of hierarchy respectively. Peers in a group in lower layer have their own local database which hold as associated super-peer in middle layer and access the database among the peers through user queries. In our 3-layer hierarchical model for DHT algorithms, we used an advanced Chord algorithm with optimized finger table which can remove the redundant entry in the finger table in upper layer that influences the system to reduce the lookup latency. Our research work finally resulted that our model really provides faster search since the network lookup latency is decreased by reducing the number of hops. The peers in such network then can contribute with improve functionality and can perform well in P2P networks.
On Finding Lekkerkerker-Boland Subgraphs
Venue: arXiv cs.DM 2013
Year: 2013

Lekkerkerker and Boland characterized the minimal forbidden induced subgraphs for the class of interval graphs. We give a linear-time algorithm to find one in any graph that is not an interval graph. Tucker characterized the minimal forbidden submatrices of matrices that do not have the consecutive-ones property. We give a linear-time algorithm to find one in any matrix that does not have the consecutive-ones property.
Approximate k-nearest neighbour based spatial clustering using k-d tree
Venue: arXiv cs.DB 2013
Year: 2013

Different spatial objects that vary in their characteristics, such as molecular biology and geography, are presented in spatial areas. Methods to organize, manage, and maintain those objects in a structured manner are required. Data mining raised different techniques to overcome these requirements. There are many major tasks of data mining, but the mostly used task is clustering. Data set within the same cluster share common features that give each cluster its characteristics. In this paper, an implementation of Approximate kNN-based spatial clustering algorithm using the K-d tree is proposed. The major contribution achieved by this research is the use of the k-d tree data structure for spatial clustering, and comparing its performance to the brute-force approach. The results of the work performed in this paper revealed better performance using the k-d tree, compared to the traditional brute-force approach.
Improving DTN Routing Performance Using Many-to-Many Communication: A Performance Modeling Study
Venue: arXiv cs.NI 2013
Year: 2013

Delay-Tolerant Networks (DTNs) have emerged as an exciting research area with a number of useful applications. Most of these applications would benefit greatly by a reduction in the message delivery delay experienced in the network. The delay performance of DTNs is adversely affected by contention, especially severe in the presence of higher traffic rates and node densities. Many-to-Many (M2M) communication can handle this contention much better than traditional one-to- one communication employing CSMA. In this paper, for the first time, we analytically model the expected delivery delay of a DTN employing epidemic routing and M2M communication. The accuracy of our model is demonstrated by matching the analytical results against those from simulations. We also show using simulations that M2M communication significantly improves the delay performance (with respect to one-to-one CSMA) for high contention scenarios. We believe our work will enable the effective application of M2M communication to reduce delivery delays in DTNs.
Security Assessment of Software Design using Neural Network
Venue: arXiv cs.CR 2013
Year: 2013

Security flaws in software applications today has been attributed mostly to design flaws. With limited budget and time to release software into the market, many developers often consider security as an afterthought. Previous research shows that integrating security into software applications at a later stage of software development lifecycle (SDLC) has been found to be more costly than when it is integrated during the early stages. To assist in the integration of security early in the SDLC stages, a new approach for assessing security during the design phase by neural network is investigated in this paper. Our findings show that by training a back propagation neural network to identify attack patterns, possible attacks can be identified from design scenarios presented to it. The result of performance of the neural network is presented in this paper.
Transfer Learning for Voice Activity Detection: A Denoising Deep Neural Network Perspective
Venue: arXiv cs.LG 2013
Year: 2013

Mismatching problem between the source and target noisy corpora severely hinder the practical use of the machine-learning-based voice activity detection (VAD). In this paper, we try to address this problem in the transfer learning prospective. Transfer learning tries to find a common learning machine or a common feature subspace that is shared by both the source corpus and the target corpus. The denoising deep neural network is used as the learning machine. Three transfer techniques, which aim to learn common feature representations, are used for analysis. Experimental results demonstrate the effectiveness of the transfer learning schemes on the mismatch problem.
The Powerful Model Adpredictor for Search Engine Switching Detection Challenge
Venue: arXiv cs.IR 2013
Year: 2013

The purpose of the Switching Detection Challenge in the 2013 WSCD workshop was to predict users' search engine swithcing actions given records about search sessions and logs.Our solution adopted the powerful prediction model Adpredictor and utilized the method of feature engineering. We successfully applied the click through rate (CTR) prediction model Adpredicitor into our solution framework, and then the discovery of effective features and the multiple classification of different switching type make our model outperforms many competitors. We achieved an AUC score of 0.84255 on the private leaderboard and ranked the 5th among all the competitors in the competition.
New Hardness Results for Guarding Orthogonal Polygons with Sliding Cameras
Venue: arXiv cs.CG 2013
Year: 2013

Let $P$ be an orthogonal polygon. Consider a sliding camera that travels back and forth along an orthogonal line segment $s\in P$ as its \emph{trajectory}. The camera can see a point $p\in P$ if there exists a point $q\in s$ such that $pq$ is a line segment normal to $s$ that is completely inside $P$. In the \emph{minimum-cardinality sliding cameras problem}, the objective is to find a set $S$ of sliding cameras of minimum cardinality to guard $P$ (i.e., every point in $P$ can be seen by some sliding camera) while in the \emph{minimum-length sliding cameras problem} the goal is to find such a set $S$ so as to minimize the total length of trajectories along which the cameras in $S$ travel. In this paper, we first settle the complexity of the minimum-length sliding cameras problem by showing that it is polynomial tractable even for orthogonal polygons with holes, answering a question asked by Katz and Morgenstern (2011). We next show that the minimum-cardinality sliding cameras problem is \textsc{NP}-hard when $P$ is allowed to have holes, which partially answers another question asked by Katz and Morgenstern (2011).
Distributed Fuzzy Optimal Spectrum Sensing In Cognitive Radio
Venue: arXiv cs.NI 2013
Year: 2013

The spectrum is a scarce resource and must utilize efficiently, the cognitive radio is a prospective solution for underutilized spectrum. The spectrum sensing is a key functionality to alleviate interference of secondary user to primary. The cognitive radios must detect the existence of the primary user and vacate the band for the primary immediately if the primary user detected. In cooperative sensing, every cognitive radio communicates their decision to fusion center via reporting channel. The reporting channels are not error free, which results corruption in the secondary's decision or information due to multipath fading and shadowing. This paper investigates the distributed fuzzy optimal cooperative spectrum sensing. The data and decision fusion with fuzzy detection is investigated in this paper. The simulation result shows the significant improvement in sensing performance over AND, OR and majority rules. The optimality in spectrum sensing is achieved by the proposed method with 1/3 of total malicious secondary users. The proposed scheme outperforms in the presence of malicious users.
Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
Venue: arXiv cs.LG 2013
Year: 2013

Relationships between entities in datasets are often of multiple nature, like geographical distance, social relationships, or common interests among people in a social network, for example. This information can naturally be modeled by a set of weighted and undirected graphs that form a global multilayer graph, where the common vertex set represents the entities and the edges on different layers capture the similarities of the entities in term of the different modalities. In this paper, we address the problem of analyzing multi-layer graphs and propose methods for clustering the vertices by efficiently merging the information provided by the multiple modalities. To this end, we propose to combine the characteristics of individual graph layers using tools from subspace analysis on a Grassmann manifold. The resulting combination can then be viewed as a low dimensional representation of the original data which preserves the most important information from diverse relationships between entities. We use this information in new clustering methods and test our algorithm on several synthetic and real world datasets where we demonstrate superior or competitive performances compared to baseline and state-of-the-art techniques. Our generic framework further extends to numerous analysis and learning problems that involve different types of information on graphs.
Efficient Parallel Computation of the Estimated Covariance Matrix
Venue: arXiv cs.DS 2013
Year: 2013

Computation of a signal's estimated covariance matrix is an important building block in signal processing, e.g., for spectral estimation. Each matrix element is a sum of products of elements in the input matrix taken over a sliding window. Any given product contributes to multiple output elements, thereby complicating parallelization. We present a novel algorithm that attains very high parallelism without repeating multiplications or requiring inter-core synchronization. Key to this is the assignment to each core of distinct diagonal segments of the output matrix, selected such that no multiplications need to be repeated yet only one core writes to any given output-matrix element, and exploitation of a shared memory (including L1 cache) that obviates the need for a corresponding awkward partitioning of the memory among cores. Implementation on Plurality's HyperCore shared-memory many-core architecture demonstrates linear speedup of up to 64 cores and speedups of ~85X for 128 cores. On an x86 system we demonstrate that the new algorithm has consider parallel speedups but also show that a sequential implementation of the new algorithm outperforms the parallel implementation of the baseline approach. On a quad-core x86 system, the new algorithm is 20X faster than sequential baseline and 5X than parallel implementation of the baseline.
Conditions for Robustness of Polar Codes in the Presence of Channel Mismatch
Venue: arXiv cs.IT 2013
Year: 2013

A challenging problem related to the design of polar codes is "robustness against channel parameter variations" as stated in Arıkan's original work. In this paper, we describe how the problem of robust polar code design can be viewed as a mismatch decoding problem. We propose conditions which ensure a polar encoder/decoder designed for a mismatched B-DMC can be used to communicate reliably. In particular, the analysis shows that the original polar code construction method is robust over the class of binary symmetric channels.