OpenRaiser/Intern-Atlas huggingface dataset:
Multilingual Medical Documents Classification Based on MesH Domain Ontology
Venue: arXiv cs.IR 2012
Year: 2012

This article deals with the semantic Web and ontologies. It addresses the issue of the classification of multilingual Web documents, based on domain ontology. The objective is being able, using a model, to classify documents in different languages. We will try to solve this problematic using two different approaches. The two approaches will have two elementary stages: the creation of the model using machine learning algorithms on a labeled corpus, then the classification of documents after detecting their languages and mapping their terms into the concepts of the language of reference (English). But each one will deal with the multilingualism with a different approach. One supposes the ontology is monolingual, whereas the other considers it multilingual. To show the feasibility and the importance of our work, we implemented it on a domain that attracts nowadays a lot of attention from the data mining community: the biomedical domain. The selected documents are from the biomedical benchmark corpus Ohsumed, and the associated ontology is the thesaurus MeSH (Medical Subject Headings). The main idea in our work is a new document representation, the masterpiece of all good classification, based on concept. The experimental results show that the recommended ideas are promising.
Joint Demapping and Decoding for DQPSK Optical Coherent Receivers
Venue: arXiv cs.IT 2012
Year: 2012

We present a low-complexity joint demapper-decoder scheme for coherent optical receivers with DQPSK modulation. The new technique reduces to 0.7dB the gap between QPSK and DQPSK in 100Gb/s coherent optical systems.
Symmetry of Information: A Closer Look
Venue: arXiv cs.IT 2012
Year: 2012

Symmetry of information establishes a relation between the information that x has about y (denoted I(x : y)) and the information that y has about x (denoted I(y : x)). In classical information theory, the two are exactly equal, but in algorithmical information theory, there is a small excess quantity of information that differentiates the two terms, caused by the necessity of packaging information in a way that makes it accessible to algorithms. It was shown in [Zim11] that in the case of strings with simple complexity (that is the Kolmogorov complexity of their Kolmogorov complexity is small), the relevant information can be packed in a very economical way, which leads to a tighter relation between I(x : y) and I(y : x) than the one provided in the classical symmetry-of-information theorem of Kolmogorov and Levin. We give here a simpler proof of this result, using a suggestion of Alexander Shen. This result implies a van Lambalgen- type theorem for finite strings and plain complexity: If x is c-random and y is c-random relative to x, then xy is O(c)-random. We show that a similar result holds for prefix-free complexity and weak-K-randomness.
Convergent Propagation Algorithms via Oriented Trees
Venue: arXiv cs.LG 2012
Year: 2012

Inference problems in graphical models are often approximated by casting them as constrained optimization problems. Message passing algorithms, such as belief propagation, have previously been suggested as methods for solving these optimization problems. However, there are few convergence guarantees for such algorithms, and the algorithms are therefore not guaranteed to solve the corresponding optimization problem. Here we present an oriented tree decomposition algorithm that is guaranteed to converge to the global optimum of the Tree-Reweighted (TRW) variational problem. Our algorithm performs local updates in the convex dual of the TRW problem - an unconstrained generalized geometric program. Primal updates, also local, correspond to oriented reparametrization operations that leave the distribution intact.
A new parameter Learning Method for Bayesian Networks with Qualitative Influences
Venue: arXiv cs.AI 2012
Year: 2012

We propose a new method for parameter learning in Bayesian networks with qualitative influences. This method extends our previous work from networks of binary variables to networks of discrete variables with ordered values. The specified qualitative influences correspond to certain order restrictions on the parameters in the network. These parameters may therefore be estimated using constrained maximum likelihood estimation. We propose an alternative method, based on the isotonic regression. The constrained maximum likelihood estimates are fairly complicated to compute, whereas computation of the isotonic regression estimates only requires the repeated application of the Pool Adjacent Violators algorithm for linear orders. Therefore, the isotonic regression estimator is to be preferred from the viewpoint of computational complexity. Through experiments on simulated and real data, we show that the new learning method is competitive in performance to the constrained maximum likelihood estimator, and that both estimators improve on the standard estimator.
Bayesian structure learning using dynamic programming and MCMC
Venue: arXiv cs.LG 2012
Year: 2012

MCMC methods for sampling from the space of DAGs can mix poorly due to the local nature of the proposals that are commonly used. It has been shown that sampling from the space of node orders yields better results [FK03, EW06]. Recently, Koivisto and Sood showed how one can analytically marginalize over orders using dynamic programming (DP) [KS04, Koi06]. Their method computes the exact marginal posterior edge probabilities, thus avoiding the need for MCMC. Unfortunately, there are four drawbacks to the DP technique: it can only use modular priors, it can only compute posteriors over modular features, it is difficult to compute a predictive density, and it takes exponential time and space. We show how to overcome the first three of these problems by using the DP algorithm as a proposal distribution for MCMC in DAG space. We show that this hybrid technique converges to the posterior faster than other methods, resulting in more accurate structure learning and higher predictive likelihoods on test data.
Statistical Translation, Heat Kernels and Expected Distances
Venue: arXiv cs.LG 2012
Year: 2012

High dimensional structured data such as text and images is often poorly understood and misrepresented in statistical modeling. The standard histogram representation suffers from high variance and performs poorly in general. We explore novel connections between statistical translation, heat kernels on manifolds and graphs, and expected distances. These connections provide a new framework for unsupervised metric learning for text documents. Experiments indicate that the resulting distances are generally superior to their more standard counterparts.
Reachability Under Uncertainty
Venue: arXiv cs.DS 2012
Year: 2012

In this paper we introduce a new network reachability problem where the goal is to find the most reliable path between two nodes in a network, represented as a directed acyclic graph. Individual edges within this network may fail according to certain probabilities, and these failure probabilities may depend on the values of one or more hidden variables. This problem may be viewed as a generalization of shortest-path problems for finding minimum cost paths or Viterbi-type problems for finding highest-probability sequences of states, where the addition of the hidden variables introduces correlations that are not handled by previous algorithms. We give theoretical results characterizing this problem including an NP-hardness proof. We also give an exact algorithm and a more efficient approximation algorithm for this problem.
Optimizing Memory-Bounded Controllers for Decentralized POMDPs
Venue: arXiv cs.AI 2012
Year: 2012

We present a memory-bounded optimization approach for solving infinite-horizon decentralized POMDPs. Policies for each agent are represented by stochastic finite state controllers. We formulate the problem of optimizing these policies as a nonlinear program, leveraging powerful existing nonlinear optimization techniques for solving the problem. While existing solvers only guarantee locally optimal solutions, we show that our formulation produces higher quality controllers than the state-of-the-art approach. We also incorporate a shared source of randomness in the form of a correlation device to further increase solution quality with only a limited increase in space and time. Our experimental results show that nonlinear optimization can be used to provide high quality, concise solutions to decentralized decision problems under uncertainty.
Reasoning at the Right Time Granularity
Venue: arXiv cs.AI 2012
Year: 2012

Most real-world dynamic systems are composed of different components that often evolve at very different rates. In traditional temporal graphical models, such as dynamic Bayesian networks, time is modeled at a fixed granularity, generally selected based on the rate at which the fastest component evolves. Inference must then be performed at this fastest granularity, potentially at significant computational cost. Continuous Time Bayesian Networks (CTBNs) avoid time-slicing in the representation by modeling the system as evolving continuously over time. The expectation-propagation (EP) inference algorithm of Nodelman et al. (2005) can then vary the inference granularity over time, but the granularity is uniform across all parts of the system, and must be selected in advance. In this paper, we provide a new EP algorithm that utilizes a general cluster graph architecture where clusters contain distributions that can overlap in both space (set of variables) and time. This architecture allows different parts of the system to be modeled at very different time granularities, according to their current rate of evolution. We also provide an information-theoretic criterion for dynamically re-partitioning the clusters during inference to tune the level of approximation to the current rate of evolution. This avoids the need to hand-select the appropriate granularity, and allows the granularity to adapt as information is transmitted across the network. We present experiments demonstrating that this approach can result in significant computational savings.
Consensus ranking under the exponential model
Venue: arXiv cs.LG 2012
Year: 2012

We analyze the generalized Mallows model, a popular exponential model over rankings. Estimating the central (or consensus) ranking from data is NP-hard. We obtain the following new results: (1) We show that search methods can estimate both the central ranking pi0 and the model parameters theta exactly. The search is n! in the worst case, but is tractable when the true distribution is concentrated around its mode; (2) We show that the generalized Mallows model is jointly exponential in (pi0; theta), and introduce the conjugate prior for this model class; (3) The sufficient statistics are the pairwise marginal probabilities that item i is preferred to item j. Preliminary experiments confirm the theoretical predictions and compare the new algorithm and existing heuristics.
AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Weighted Graphical Models
Venue: arXiv cs.AI 2012
Year: 2012

Compiling graphical models has recently been under intense investigation, especially for probabilistic modeling and processing. We present here a novel data structure for compiling weighted graphical models (in particular, probabilistic models), called AND/OR Multi-Valued Decision Diagram (AOMDD). This is a generalization of our previous work on constraint networks, to weighted models. The AOMDD is based on the frameworks of AND/OR search spaces for graphical models, and Ordered Binary Decision Diagrams (OBDD). The AOMDD is a canonical representation of a graphical model, and its size and compilation time are bounded exponentially by the treewidth of the graph, rather than pathwidth as is known for OBDDs. We discuss a Variable Elimination schedule for compilation, and present the general APPLY algorithm that combines two weighted AOMDDs, and also present a search based method for compilation method. The preliminary experimental evaluation is quite encouraging, showing the potential of the AOMDD data structure.
Survey Propagation Revisited
Venue: arXiv cs.AI 2012
Year: 2012

Survey propagation (SP) is an exciting new technique that has been remarkably successful at solving very large hard combinatorial problems, such as determining the satisfiability of Boolean formulas. In a promising attempt at understanding the success of SP, it was recently shown that SP can be viewed as a form of belief propagation, computing marginal probabilities over certain objects called covers of a formula. This explanation was, however, shortly dismissed by experiments suggesting that non-trivial covers simply do not exist for large formulas. In this paper, we show that these experiments were misleading: not only do covers exist for large hard random formulas, SP is surprisingly accurate at computing marginals over these covers despite the existence of many cycles in the formulas. This re-opens a potentially simpler line of reasoning for understanding SP, in contrast to some alternative lines of explanation that have been proposed assuming covers do not exist.
Ranking Under Uncertainty
Venue: arXiv cs.AI 2012
Year: 2012

Ranking objects is a simple and natural procedure for organizing data. It is often performed by assigning a quality score to each object according to its relevance to the problem at hand. Ranking is widely used for object selection, when resources are limited and it is necessary to select a subset of most relevant objects for further processing. In real world situations, the object's scores are often calculated from noisy measurements, casting doubt on the ranking reliability. We introduce an analytical method for assessing the influence of noise levels on the ranking reliability. We use two similarity measures for reliability evaluation, Top-K-List overlap and Kendall's tau measure, and show that the former is much more sensitive to noise than the latter. We apply our method to gene selection in a series of microarray experiments of several cancer types. The results indicate that the reliability of the lists obtained from these experiments is very poor, and that experiment sizes which are necessary for attaining reasonably stable Top-K-Lists are much larger than those currently available. Simulations support our analytical results.
Learning Selectively Conditioned Forest Structures with Applications to DBNs and Classification
Venue: arXiv cs.LG 2012
Year: 2012

Dealing with uncertainty in Bayesian Network structures using maximum a posteriori (MAP) estimation or Bayesian Model Averaging (BMA) is often intractable due to the superexponential number of possible directed, acyclic graphs. When the prior is decomposable, two classes of graphs where efficient learning can take place are tree structures, and fixed-orderings with limited in-degree. We show how MAP estimates and BMA for selectively conditioned forests (SCF), a combination of these two classes, can be computed efficiently for ordered sets of variables. We apply SCFs to temporal data to learn Dynamic Bayesian Networks having an intra-timestep forest and inter-timestep limited in-degree structure, improving model accuracy over DBNs without the combination of structures. We also apply SCFs to Bayes Net classification to learn selective forest augmented Naive Bayes classifiers. We argue that the built-in feature selection of selective augmented Bayes classifiers makes them preferable to similar non-selective classifiers based on empirical evidence.
Bayesian Active Distance Metric Learning
Venue: arXiv cs.LG 2012
Year: 2012

Distance metric learning is an important component for many tasks, such as statistical classification and content-based image retrieval. Existing approaches for learning distance metrics from pairwise constraints typically suffer from two major problems. First, most algorithms only offer point estimation of the distance metric and can therefore be unreliable when the number of training examples is small. Second, since these algorithms generally select their training examples at random, they can be inefficient if labeling effort is limited. This paper presents a Bayesian framework for distance metric learning that estimates a posterior distribution for the distance metric from labeled pairwise constraints. We describe an efficient algorithm based on the variational method for the proposed Bayesian approach. Furthermore, we apply the proposed Bayesian framework to active distance metric learning by selecting those unlabeled example pairs with the greatest uncertainty in relative distance. Experiments in classification demonstrate that the proposed framework achieves higher classification accuracy and identifies more informative training examples than the non-Bayesian approach and state-of-the-art distance metric learning algorithms.
Policy Iteration for Relational MDPs
Venue: arXiv cs.AI 2012
Year: 2012

Relational Markov Decision Processes are a useful abstraction for complex reinforcement learning problems and stochastic planning problems. Recent work developed representation schemes and algorithms for planning in such problems using the value iteration algorithm. However, exact versions of more complex algorithms, including policy iteration, have not been developed or analyzed. The paper investigates this potential and makes several contributions. First we observe two anomalies for relational representations showing that the value of some policies is not well defined or cannot be calculated for restricted representation schemes used in the literature. On the other hand, we develop a variant of policy iteration that can get around these anomalies. The algorithm includes an aspect of policy improvement in the process of policy evaluation and thus differs from the original algorithm. We show that despite this difference the algorithm converges to the optimal policy.
Improved Dynamic Schedules for Belief Propagation
Venue: arXiv cs.LG 2012
Year: 2012

Belief propagation and its variants are popular methods for approximate inference, but their running time and even their convergence depend greatly on the schedule used to send the messages. Recently, dynamic update schedules have been shown to converge much faster on hard networks than static schedules, namely the residual BP schedule of Elidan et al. [2006]. But that RBP algorithm wastes message updates: many messages are computed solely to determine their priority, and are never actually performed. In this paper, we show that estimating the residual, rather than calculating it directly, leads to significant decreases in the number of messages required for convergence, and in the total running time. The residual is estimated using an upper bound based on recent work on message errors in BP. On both synthetic and real-world networks, this dramatically decreases the running time of BP, in some cases by a factor of five, without affecting the quality of the solution.
The McDougal Cave and Counting issues
Venue: arXiv cs.DS 2012
Year: 2012

In this paper I investigate the problem of tagging elements of a set, and the elements of those elements, uniquely, when they admit an order, and two boundary elements are tagged. A heuristic sorting algorithm is also investigated. (Updated grammar and spellings.)
Imperfect Delayed CSIT can be as Useful as Perfect Delayed CSIT: DoF Analysis and Constructions for the BC
Venue: arXiv cs.IT 2012
Year: 2012

In the setting of the two-user broadcast channel, where a two-antenna transmitter communicates information to two single-antenna receivers, recent work by Maddah-Ali and Tse has shown that perfect knowledge of delayed channel state information at the transmitter (perfect delayed CSIT) can be useful, even in the absence of any knowledge of current CSIT. Similar benefits of perfect delayed CSIT were revealed in recent work by Kobayashi et al., Yang et al., and Gou and Jafar, which extended the above to the case of perfect delayed CSIT and imperfect current CSIT. The work here considers the general problem of communicating, over the aforementioned broadcast channel, with imperfect delayed and imperfect current CSIT, and reveals that even substantially degraded and imperfect delayed-CSIT is in fact sufficient to achieve the aforementioned gains previously associated to perfect delayed CSIT. The work proposes novel multi-phase broadcasting schemes that properly utilize knowledge of imperfect delayed and imperfect current CSIT, to match in many cases the optimal degrees-of-freedom (DoF) region achieved with perfect delayed CSIT. In addition to the theoretical limits and explicitly constructed precoders, the work applies towards gaining practical insight as to when it is worth improving CSIT quality.
Home Healthcare Process: Challenges and Open Issues
Venue: arXiv cs.SE 2012
Year: 2012

Home healthcare is part of the most critical research and development healthcare areas. The objective is to decentralize healthcare, leading to a shift from in-hospital care to more advanced home healthcare, while improving efficiency, individualisation, equity and quality of healthcare delivery and limiting financial resources. In this paper, we adopt a process approach to tackle the home healthcare domain in order to highlight the importance of organisational aspects in the success of an ICT-home healthcare project. Such projects should be supported by an automated system, called in this paper, Home Healthcare support system. We examine HH processes from two selected perspectives (complexity and dynamics) to illustrate the requirements of a HH support system. We advocate that satisfying these requirements is part of the most important challenges in the home healthcare research domain and we propose first track of solutions by attempting to benefit from past experiences in 3 process research communities.
Robust Downlink Throughput Maximization in MIMO Cognitive Network with more Realistic Conditions: Imperfect Channel Information & Presence of Primary Transmitter
Venue: arXiv cs.IT 2012
Year: 2012

Designing an efficient scheme in physical layer enables cognitive radio (CR) users to efficiently utilize resources dedicated to primary users (PUs). In this paper in order to maximize the SU's throughput, the SU's transceivers beamforming is designed through new model considering the presence of the PU's transmitter. Since presence of primary transmitter basically degrades CR's system performance; proposed beamforming design considers intra-system interference between PUs and SUs. An optimization problem based on maximizing CR network throughput subject to controlling interference power from SU transmitter to PU receiver has been formulated. Due to limited cooperation between PU and SU network, channel state information (CSI) between two networks are assumed to be partially available, subsequently conventional CSI uncertainty model known as norm bounded error model has been employed. The proposed optimization problem, which is basically difficult to solve, has been converted to a semi definite program which can be efficiently solved by optimization toolbox software e.g., CVX-Mathlab. Furthermore, alternative time efficient and close form solutions are derived. The superiority of the proposed approach in comparison with the previous works has been confirmed through the simulation results.