OpenRaiser/Intern-Atlas huggingface dataset:
Large Neighborhood Local Search for the Maximum Set Packing Problem
Venue: arXiv cs.DS 2013
Year: 2013

In this paper we consider the classical maximum set packing problem where set cardinality is upper bounded by $k$. We show how to design a variant of a polynomial-time local search algorithm with performance guarantee $(k+2)/3$. This local search algorithm is a special case of a more general procedure that allows to swap up to $Θ(\log n)$ elements per iteration. We also design problem instances with locality gap $k/3$ even for a wide class of exponential time local search procedures, which can swap up to $cn$ elements for a constant $c$. This shows that our analysis of this class of algorithms is almost tight.
Adaptive Minimum BER Reduced-Rank Linear Detection for Massive MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose a novel adaptive reduced-rank strategy for very large multiuser multi-input multi-output (MIMO) systems. The proposed reduced-rank scheme is based on the concept of joint iterative optimization (JIO) of filters according to the minimization of the bit error rate (BER) cost function. The proposed optimization technique adjusts the weights of a projection matrix and a reduced-rank filter jointly. We develop stochastic gradient (SG) algorithms for their adaptive implementation and introduce a novel automatic rank selection method based on the BER criterion. Simulation results for multiuser MIMO systems show that the proposed adaptive algorithms significantly outperform existing schemes.
On the multiple unicast capacity of 3-source, 3-terminal directed acyclic networks
Venue: arXiv cs.IT 2013
Year: 2013

We consider the multiple unicast problem with three source-terminal pairs over directed acyclic networks with unit-capacity edges. The three $s_i-t_i$ pairs wish to communicate at unit-rate via network coding. The connectivity between the $s_i - t_i$ pairs is quantified by means of a connectivity level vector, $[k_1 k_2 k_3]$ such that there exist $k_i$ edge-disjoint paths between $s_i$ and $t_i$. In this work we attempt to classify networks based on the connectivity level. It can be observed that unit-rate transmission can be supported by routing if $k_i \geq 3$, for all $i = 1, \dots, 3$. In this work, we consider, connectivity level vectors such that $\min_{i = 1, \dots, 3} k_i < 3$. We present either a constructive linear network coding scheme or an instance of a network that cannot support the desired unit-rate requirement, for all such connectivity level vectors except the vector $[1~2~4]$ (and its permutations). The benefits of our schemes extend to networks with higher and potentially different edge capacities. Specifically, our experimental results indicate that for networks where the different source-terminal paths have a significant overlap, our constructive unit-rate schemes can be packed along with routing to provide higher throughput as compared to a pure routing approach.
Preference-Based Unawareness
Venue: arXiv cs.GT 2013
Year: 2013

Morris (1996, 1997) introduced preference-based definitions of knowledge and belief in standard state-space structures. This paper extends this preference-based approach to unawareness structures (Heifetz, Meier, and Schipper, 2006, 2008). By defining unawareness and knowledge in terms of preferences over acts in unawareness structures and showing their equivalence to the epistemic notions of unawareness and knowledge, we try to build a bridge between decision theory and epistemic logic. Unawareness of an event is characterized behaviorally as the event being null and its negation being null.
Random-walk domination in large graphs: problem definitions and fast solutions
Venue: arXiv cs.SI 2013
Year: 2013

We introduce and formulate two types of random-walk domination problems in graphs motivated by a number of applications in practice (e.g., item-placement problem in online social network, Ads-placement problem in advertisement networks, and resource-placement problem in P2P networks). Specifically, given a graph $G$, the goal of the first type of random-walk domination problem is to target $k$ nodes such that the total hitting time of an $L$-length random walk starting from the remaining nodes to the targeted nodes is minimal. The second type of random-walk domination problem is to find $k$ nodes to maximize the expected number of nodes that hit any one targeted node through an $L$-length random walk. We prove that these problems are two special instances of the submodular set function maximization with cardinality constraint problem. To solve them effectively, we propose a dynamic-programming (DP) based greedy algorithm which is with near-optimal performance guarantee. The DP-based greedy algorithm, however, is not very efficient due to the expensive marginal gain evaluation. To further speed up the algorithm, we propose an approximate greedy algorithm with linear time complexity w.r.t.\ the graph size and also with near-optimal performance guarantee. The approximate greedy algorithm is based on a carefully designed random-walk sampling and sample-materialization techniques. Extensive experiments demonstrate the effectiveness, efficiency and scalability of the proposed algorithms.
Linking Things on the Web: A Pragmatic Examination of Linked Data for Libraries, Archives and Museums
Venue: arXiv cs.DL 2013
Year: 2013

The Web publishing paradigm of Linked Data has been gaining traction in the cultural heritage sector: libraries, archives and museums. At first glance, the principles of Linked Data seem simple enough. However experienced Web developers, designers and architects who attempt to put these ideas into practice often find themselves having to digest and understand debates about Web architecture, the semantic web, artificial intelligence and the philosophical nature of identity. In this paper I will discuss some of the reasons why Linked Data is of interest to the cultural heritage community, what some of the pain points are for deploying it, and characterize some pragmatic ways for cultural heritage organizations to realize the goals of Linked Data with examples from the Web we have today.
A Receiver-Centric OFCDM Approach with Subcarrier Grouping
Venue: arXiv cs.IT 2013
Year: 2013

In this letter, following a cross-layer design concept, we propose a novel subcarrier grouping technique for Orthogonal Frequency and Code Division Multiplexing (OFCDM) multiuser systems. We adopt a two dimensional (2D) spreading, so as to achieve both frequency- and time-domain channel gain. Furthermore, we enable a receiver-centric approach, where the receiver rather than a potential sender controls the admission decision of the communication establishment. We study the robustness of the proposed scheme in terms of the Bit-Error-Rate (BER) and the outage probability. The derived results indicate that the proposed scheme outperforms the classical OFCDM approach.
Energy-Efficient Resource Allocation in OFDMA Systems with Hybrid Energy Harvesting Base Station
Venue: arXiv cs.IT 2013
Year: 2013

We study resource allocation algorithm design for energy-efficient communication in an OFDMA downlink network with hybrid energy harvesting base station. Specifically, an energy harvester and a constant energy source driven by a non-renewable resource are used for supplying the energy required for system operation. We first consider a deterministic offline system setting. In particular, assuming availability of non-causal knowledge about energy arrivals and channel gains, an offline resource allocation problem is formulated as a non-convex optimization problem taking into account the circuit energy consumption, a finite energy storage capacity, and a minimum required data rate. We transform this non-convex optimization problem into a convex optimization problem by applying time-sharing and fractional programming which results in an efficient asymptotically optimal offline iterative resource allocation algorithm. In each iteration, the transformed problem is solved by using Lagrange dual decomposition. The obtained resource allocation policy maximizes the weighted energy efficiency of data transmission. Subsequently, we focus on online algorithm design. A stochastic dynamic programming approach is employed to obtain the optimal online resource allocation algorithm which requires a prohibitively high complexity. To strike a balance between system performance and computational complexity, we propose a low complexity suboptimal online iterative algorithm which is motivated by the offline optimization.
An Ontology for Modelling and Supporting the Process of Authoring Technical Assessments
Venue: arXiv cs.IR 2013
Year: 2013

In this paper, we present a semantic web approach for modelling the process of creating new technical and regulatory documents related to the Building sector. This industry, among other industries, is currently experiencing a phenomenal growth in its technical and regulatory texts. Therefore, it is urgent and crucial to improve the process of creating regulations by automating it as much as possible. We focus on the creation of particular technical documents issued by the French Scientific and Technical Centre for Building (CSTB), called Technical Assessments, and we propose services based on Semantic Web models and techniques for modelling the process of their creation.
Design Features for the Social Web: The Architecture of Deme
Venue: arXiv cs.SI 2013
Year: 2013

We characterize the "social Web" and argue for several features that are desirable for users of socially oriented web applications. We describe the architecture of Deme, a web content management system (WCMS) and extensible framework, and show how it implements these desired features. We then compare Deme on our desiderata with other web technologies: traditional HTML, previous open source WCMSs (illustrated by Drupal), commercial Web 2.0 applications, and open-source, object-oriented web application frameworks. The analysis suggests that a WCMS can be well suited to building social websites if it makes more of the features of object-oriented programming, such as polymorphism, and class inheritance, available to non-programmers in an accessible vocabulary.
A theoretical framework for conducting multi-level studies of complex social systems with agent-based models and empirical data
Venue: arXiv cs.MA 2013
Year: 2013

A formal but intuitive framework is introduced to bridge the gap between data obtained from empirical studies and that generated by agent-based models. This is based on three key tenets. Firstly, a simulation can be given multiple formal descriptions corresponding to static and dynamic properties at different levels of observation. These can be easily mapped to empirically observed phenomena and data obtained from them. Secondly, an agent-based model generates a set of closed systems, and computational simulation is the means by which we sample from this set. Thirdly, properties at different levels and statistical relationships between them can be used to classify simulations as those that instantiate a more sophisticated set of constraints. These can be validated with models obtained from statistical models of empirical data (for example, structural equation or multi-level models) and hence provide more stringent criteria for validating the agent-based model itself.
A Distributed Approach to Interference Alignment in OFDM-based Two-tiered Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this contribution, we consider a two-tiered network and focus on the coexistence between the two tiers at physical layer. We target our efforts on a long term evolution advanced (LTE-A) orthogonal frequency division multiple access (OFDMA) macro-cell sharing the spectrum with a randomly deployed second tier of small-cells. In such networks, high levels of co-channel interference between the macro and small base stations (MBS/SBS) may largely limit the potential spectral efficiency gains provided by the frequency reuse 1. To address this issue, we propose a novel cognitive interference alignment based scheme to protect the macro-cell from the cross-tier interference, while mitigating the co-tier interference in the second tier. Remarkably, only local channel state information (CSI) and autonomous operations are required in the second tier, resulting in a completely self-organizing approach for the SBSs. The optimal precoder that maximizes the spectral efficiency of the link between each SBS and its served user equipment is found by means of a distributed one-shot strategy. Numerical findings reveal non-negligible spectral efficiency enhancements with respect to traditional time division multiple access approaches at any signal to noise (SNR) regime. Additionally, the proposed technique exhibits significant robustness to channel estimation errors, achieving remarkable results for the imperfect CSI case and yielding consistent performance enhancements to the network.
Layered Interference Networks with Delayed CSI: DoF Scaling with Distributed Transmitters
Venue: arXiv cs.IT 2013
Year: 2013

The layered interference network is investigated with delayed channel state information (CSI) at all nodes. It is demonstrated how multi-hopping can be utilized to increase the achievable degrees of freedom (DoF). In particular, a multi-phase transmission scheme is proposed for the $K$-user $2K$-hop interference network in order to systematically exploit the layered structure of the network and delayed CSI to achieve DoF values that scale with $K$. This result provides the first example of a network with distributed transmitters and delayed CSI whose DoF scales with the number of users.
A Labeled Graph Kernel for Relationship Extraction
Venue: arXiv cs.CL 2013
Year: 2013

In this paper, we propose an approach for Relationship Extraction (RE) based on labeled graph kernels. The kernel we propose is a particularization of a random walk kernel that exploits two properties previously studied in the RE literature: (i) the words between the candidate entities or connecting them in a syntactic representation are particularly likely to carry information regarding the relationship; and (ii) combining information from distinct sources in a kernel may help the RE system make better decisions. We performed experiments on a dataset of protein-protein interactions and the results show that our approach obtains effectiveness values that are comparable with the state-of-the art kernel methods. Moreover, our approach is able to outperform the state-of-the-art kernels when combined with other kernel methods.
Chain Graphs for Learning
Venue: arXiv cs.AI 2013
Year: 2013

Chain graphs combine directed and undirected graphs and their underlying mathematics combines properties of the two. This paper gives a simplified definition of chain graphs based on a hierarchical combination of Bayesian (directed) and Markov (undirected) networks. Examples of a chain graph are multivariate feed-forward networks, clustering with conditional interaction between variables, and forms of Bayes classifiers. Chain graphs are then extended using the notation of plates so that samples and data analysis problems can be represented in a graphical model as well. Implications for learning are discussed in the conclusion.
Generating the Structure of a Fuzzy Rule under Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

The aim of this paper is to present a method for identifying the structure of a rule in a fuzzy model. For this purpose, an ATMS shall be used (Zurita 1994). An algorithm obtaining the identification of the structure will be suggested (Castro 1995). The minimal structure of the rule (with respect to the number of variables that must appear in the rule) will be found by this algorithm. Furthermore, the identification parameters shall be obtained simultaneously. The proposed method shall be applied for classification to an example. The {em Iris Plant Database} shall be learnt for all three kinds of plants.
Implementation of Continuous Bayesian Networks Using Sums of Weighted Gaussians
Venue: arXiv cs.AI 2013
Year: 2013

Bayesian networks provide a method of representing conditional independence between random variables and computing the probability distributions associated with these random variables. In this paper, we extend Bayesian network structures to compute probability density functions for continuous random variables. We make this extension by approximating prior and conditional densities using sums of weighted Gaussian distributions and then finding the propagation rules for updating the densities in terms of these weights. We present a simple example that illustrates the Bayesian network for continuous variables; this example shows the effect of the network structure and approximation errors on the computation of densities for variables in the network.
Testing Identifiability of Causal Effects
Venue: arXiv cs.AI 2013
Year: 2013

This paper concerns the probabilistic evaluation of the effects of actions in the presence of unmeasured variables. We show that the identification of causal effect between a singleton variable X and a set of variables Y can be accomplished systematically, in time polynomial in the number of variables in the graph. When the causal effect is identifiable, a closed-form expression can be obtained for the probability that the action will achieve a specified goal, or a set of goals.
Stochastic Simulation Algorithms for Dynamic Probabilistic Networks
Venue: arXiv cs.AI 2013
Year: 2013

Stochastic simulation algorithms such as likelihood weighting often give fast, accurate approximations to posterior probabilities in probabilistic networks, and are the methods of choice for very large networks. Unfortunately, the special characteristics of dynamic probabilistic networks (DPNs), which are used to represent stochastic temporal processes, mean that standard simulation algorithms perform very poorly. In essence, the simulation trials diverge further and further from reality as the process is observed over time. In this paper, we present simulation algorithms that use the evidence observed at each time step to push the set of trials back towards reality. The first algorithm, "evidence reversal" (ER) restructures each time slice of the DPN so that the evidence nodes for the slice become ancestors of the state variables. The second algorithm, called "survival of the fittest" sampling (SOF), "repopulates" the set of trials at each time step using a stochastic reproduction rate weighted by the likelihood of the evidence according to each trial. We compare the performance of each algorithm with likelihood weighting on the original network, and also investigate the benefits of combining the ER and SOF methods. The ER/SOF combination appears to maintain bounded error independent of the number of time steps in the simulation.
On the Detection of Conflicts in Diagnostic Bayesian Networks Using Abstraction
Venue: arXiv cs.AI 2013
Year: 2013

An important issue in the use of expert systems is the so-called brittleness problem. Expert systems model only a limited part of the world. While the explicit management of uncertainty in expert systems itigates the brittleness problem, it is still possible for a system to be used, unwittingly, in ways that the system is not prepared to address. Such a situation may be detected by the method of straw models, first presented by Jensen et al. [1990] and later generalized and justified by Laskey [1991]. We describe an algorithm, which we have implemented, that takes as input an annotated diagnostic Bayesian network (the base model) and constructs, without assistance, a bipartite network to be used as a straw model. We show that in some cases this straw model is better that the independent straw model of Jensen et al., the only other straw model for which a construction algorithm has been designed and implemented.
Sensitivities: An Alternative to Conditional Probabilities for Bayesian Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

We show an alternative way of representing a Bayesian belief network by sensitivities and probability distributions. This representation is equivalent to the traditional representation by conditional probabilities, but makes dependencies between nodes apparent and intuitively easy to understand. We also propose a QR matrix representation for the sensitivities and/or conditional probabilities which is more efficient, in both memory requirements and computational speed, than the traditional representation for computer-based implementations of probabilistic inference. We use sensitivities to show that for a certain class of binary networks, the computation time for approximate probabilistic inference with any positive upper bound on the error of the result is independent of the size of the network. Finally, as an alternative to traditional algorithms that use conditional probabilities, we describe an exact algorithm for probabilistic inference that uses the QR-representation for sensitivities and updates probability distributions of nodes in a network according to messages from the neighbors.
Refining Reasoning in Qualitative Probabilistic Networks
Venue: arXiv cs.AI 2013
Year: 2013

In recent years there has been a spate of papers describing systems for probabilisitic reasoning which do not use numerical probabilities. In some cases the simple set of values used by these systems make it impossible to predict how a probability will change or which hypothesis is most likely given certain evidence. This paper concentrates on such situations, and suggests a number of ways in which they may be resolved by refining the representation.
Path Planning under Time-Dependent Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

Standard algorithms for finding the shortest path in a graph require that the cost of a path be additive in edge costs, and typically assume that costs are deterministic. We consider the problem of uncertain edge costs, with potential probabilistic dependencies among the costs. Although these dependencies violate the standard dynamic-programming decomposition, we identify a weaker stochastic consistency condition that justifies a generalized dynamic-programming approach based on stochastic dominance. We present a revised path-planning algorithm and prove that it produces optimal paths under time-dependent uncertain costs. We test the algorithm by applying it to a model of stochastic bus networks, and present empirical performance results comparing it to some alternatives. Finally, we consider extensions of these concepts to a more general class of problems of heuristic search under uncertainty.
A Method for Implementing a Probabilistic Model as a Relational Database
Venue: arXiv cs.AI 2013
Year: 2013

This paper discusses a method for implementing a probabilistic inference system based on an extended relational data model. This model provides a unified approach for a variety of applications such as dynamic programming, solving sparse linear equations, and constraint propagation. In this framework, the probability model is represented as a generalized relational database. Subsequent probabilistic requests can be processed as standard relational queries. Conventional database management systems can be easily adopted for implementing such an approximate reasoning system.
Cognitive Interference Alignment for OFDM Two-tiered Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this contribution, we introduce an interference alignment scheme that allows the coexistence of an orthogonal frequency division multiplexing (OFDM) macro-cell and a cognitive small-cell, deployed in a two-tiered structure and transmitting over the same bandwidth. We derive the optimal linear strategy for the single antenna secondary base station, maximizing the spectral efficiency of the opportunistic link, accounting for both signal sub-space structure and power loading strategy. Our analytical and numerical findings prove that the precoder structure proposed is optimal for the considered scenario in the face of Rayleigh and exponential decaying channels.