OpenRaiser/Intern-Atlas huggingface dataset:
An Information-Theoretic Analysis of Hard and Soft Assignment Methods for Clustering
Venue: arXiv cs.LG 2013
Year: 2013

Assignment methods are at the heart of many algorithms for unsupervised learning and clustering - in particular, the well-known K-means and Expectation-Maximization (EM) algorithms. In this work, we study several different methods of assignment, including the "hard" assignments used by K-means and the ?soft' assignments used by EM. While it is known that K-means minimizes the distortion on the data and EM maximizes the likelihood, little is known about the systematic differences of behavior between the two algorithms. Here we shed light on these differences via an information-theoretic analysis. The cornerstone of our results is a simple decomposition of the expected distortion, showing that K-means (and its extension for inferring general parametric densities from unlabeled sample data) must implicitly manage a trade-off between how similar the data assigned to each cluster are, and how the data are balanced among the clusters. How well the data are balanced is measured by the entropy of the partition defined by the hard assignments. In addition to letting us predict and verify systematic differences between K-means and EM on specific examples, the decomposition allows us to give a rather general argument showing that K ?means will consistently find densities with less "overlap" than EM. We also study a third natural assignment method that we call posterior assignment, that is close in spirit to the soft assignments of EM, but leads to a surprisingly different algorithm.
Probabilistic Acceptance
Venue: arXiv cs.AI 2013
Year: 2013

The idea of fully accepting statements when the evidence has rendered them probable enough faces a number of difficulties. We leave the interpretation of probability largely open, but attempt to suggest a contextual approach to full belief. We show that the difficulties of probabilistic acceptance are not as severe as they are sometimes painted, and that though there are oddities associated with probabilistic acceptance they are in some instances less awkward than the difficulties associated with other nonmonotonic formalisms. We show that the structure at which we arrive provides a natural home for statistical inference.
Learning Bayesian Networks from Incomplete Databases
Venue: arXiv cs.AI 2013
Year: 2013

Bayesian approaches to learn the graphical structure of Bayesian Belief Networks (BBNs) from databases share the assumption that the database is complete, that is, no entry is reported as unknown. Attempts to relax this assumption involve the use of expensive iterative methods to discriminate among different structures. This paper introduces a deterministic method to learn the graphical structure of a BBN from a possibly incomplete database. Experimental evaluations show a significant robustness of this method and a remarkable independence of its execution time from the number of missing data.
Conditional Utility, Utility Independence, and Utility Networks
Venue: arXiv cs.GT 2013
Year: 2013

We introduce a new interpretation of two related notions - conditional utility and utility independence. Unlike the traditional interpretation, the new interpretation renders the notions the direct analogues of their probabilistic counterparts. To capture these notions formally, we appeal to the notion of utility distribution, introduced in previous paper. We show that utility distributions, which have a structure that is identical to that of probability distributions, can be viewed as a special case of an additive multiattribute utility functions, and show how this special case permits us to capture the novel senses of conditional utility and utility independence. Finally, we present the notion of utility networks, which do for utilities what Bayesian networks do for probabilities. Specifically, utility networks exploit the new interpretation of conditional utility and utility independence to compactly represent a utility distribution.
Lexical Access for Speech Understanding using Minimum Message Length Encoding
Venue: arXiv cs.CL 2013
Year: 2013

The Lexical Access Problem consists of determining the intended sequence of words corresponding to an input sequence of phonemes (basic speech sounds) that come from a low-level phoneme recognizer. In this paper we present an information-theoretic approach based on the Minimum Message Length Criterion for solving the Lexical Access Problem. We model sentences using phoneme realizations seen in training, and word and part-of-speech information obtained from text corpora. We show results on multiple-speaker, continuous, read speech and discuss a heuristic using equivalence classes of similar sounding words which speeds up the recognition process without significant deterioration in recognition accuracy.
Independence of Causal Influence and Clique Tree Propagation
Venue: arXiv cs.AI 2013
Year: 2013

This paper explores the role of independence of causal influence (ICI) in Bayesian network inference. ICI allows one to factorize a conditional probability table into smaller pieces. We describe a method for exploiting the factorization in clique tree propagation (CTP) - the state-of-the-art exact inference algorithm for Bayesian networks. We also present empirical results showing that the resulting algorithm is significantly more efficient than the combination of CTP and previous techniques for exploiting ICI.
On the Capacity Region for Index Coding
Venue: arXiv cs.IT 2013
Year: 2013

A new inner bound on the capacity region of a general index coding problem is established. Unlike most existing bounds that are based on graph theoretic or algebraic tools, the bound is built on a random coding scheme and optimal decoding, and has a simple polymatroidal single-letter expression. The utility of the inner bound is demonstrated by examples that include the capacity region for all index coding problems with up to five messages (there are 9846 nonisomorphic ones).
The Affects of Different Queuing Algorithms within the Router on QoS VoIP application Using OPNET
Venue: arXiv cs.NI 2013
Year: 2013

Voice over Internet Protocol is a service from the Internet services that allows users to communicate with each other. Quality of Service is very sensitive to delay so that Voice over Internet Protocol needs it. The objective of this research is to study the effect of different queuing algorithms within the router on Voice over Internet Protocol Quality of Service. In this work, simulation tool OPNET Modeler is used to implement the proposed network (Voice over Internet Protocol Network). The proposed network is a private network for a company that has two locations located at two different countries around the world in order to simulate the communications within the same location as a local and the communications between two locations as a long distance and analyze Voice over Internet Protocol Quality of Service through measuring the major factors that affect the Quality of Service for Voice over Internet Protocol according to international telecommunication union standards such as: delay, jitter and packet loss. In this research, a comparison was carried out between different queue algorithms like First in First out (FIFO), Priority queue and Weight Fair Queuing and it was found that Priority queue and Weight Fair Queuing algorithms are the most appropriate to improve Voice over Internet Protocol Quality of Service .
On the Capacity Region of the Two-User Interference Channel
Venue: arXiv cs.IT 2013
Year: 2013

One of the key open problems in network information theory is to obtain the capacity region for the two-user Interference Channel (IC). In this paper, new results are derived for this channel. As a first result, a noisy interference regime is given for the general IC where the sum-rate capacity is achieved by treating interference as noise at the receivers. To obtain this result, a single-letter outer bound in terms of some auxiliary random variables is first established for the sum-rate capacity of the general IC and then those conditions under which this outer bound is reduced to the achievable sum-rate given by the simple treating interference as noise strategy are specified. The main benefit of this approach is that it is applicable for any two-user IC (potentially non-Gaussian). For the special case of Gaussian channel, our result is reduced to the noisy interference regime that was previously obtained. Next, some results are given on the Han-Kobayashi (HK) achievable rate region. The evaluation of this rate region is in general difficult. In this paper, a simple characterization of the HK rate region is derived for some special cases, specifically, for a novel very weak interference regime. As a remarkable characteristic, it is shown that for this very weak interference regime, the achievable sum-rate due to the HK region is identical to the one given by the simple treating interference as noise strategy.
SWATI: Synthesizing Wordlengths Automatically Using Testing and Induction
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, we present an automated technique SWATI: Synthesizing Wordlengths Automatically Using Testing and Induction, which uses a combination of Nelder-Mead optimization based testing, and induction from examples to automatically synthesize optimal fixedpoint implementation of numerical routines. The design of numerical software is commonly done using floating-point arithmetic in design-environments such as Matlab. However, these designs are often implemented using fixed-point arithmetic for speed and efficiency reasons especially in embedded systems. The fixed-point implementation reduces implementation cost, provides better performance, and reduces power consumption. The conversion from floating-point designs to fixed-point code is subject to two opposing constraints: (i) the word-width of fixed-point types must be minimized, and (ii) the outputs of the fixed-point program must be accurate. In this paper, we propose a new solution to this problem. Our technique takes the floating-point program, specified accuracy and an implementation cost model and provides the fixed-point program with specified accuracy and optimal implementation cost. We demonstrate the effectiveness of our approach on a set of examples from the domain of automated control, robotics and digital signal processing.
HTC Scientific Computing in a Distributed Cloud Environment
Venue: arXiv cs.DC 2013
Year: 2013

This paper describes the use of a distributed cloud computing system for high-throughput computing (HTC) scientific applications. The distributed cloud computing system is composed of a number of separate Infrastructure-as-a-Service (IaaS) clouds that are utilized in a unified infrastructure. The distributed cloud has been in production-quality operation for two years with approximately 500,000 completed jobs where a typical workload has 500 simultaneous embarrassingly-parallel jobs that run for approximately 12 hours. We review the design and implementation of the system which is based on pre-existing components and a number of custom components. We discuss the operation of the system, and describe our plans for the expansion to more sites and increased computing capacity.
A new compressive video sensing framework for mobile broadcast
Venue: arXiv cs.MM 2013
Year: 2013

A new video coding method based on compressive sampling is proposed. In this method, a video is coded using compressive measurements on video cubes. Video reconstruction is performed by minimization of total variation (TV) of the pixelwise DCT coefficients along the temporal direction. A new reconstruction algorithm is developed from TVAL3, an efficient TV minimization algorithm based on the alternating minimization and augmented Lagrangian methods. Video coding with this method is inherently scalable, and has applications in mobile broadcast.
Gaussian State Amplification with Noisy State Observations
Venue: arXiv cs.IT 2013
Year: 2013

The problem of simultaneous message transmission and state amplification in a Gaussian channel with additive Gaussian state is studied when the sender has imperfect noncausal knowledge of the state sequence. Inner and outer bounds to the rate--state-distortion region are provided. The coding scheme underlying the inner bound combines analog signaling and Gelfand-Pinsker coding, where the latter deviates from the operating point of Costa's dirty paper coding.
Building an Expert System for Evaluation of Commercial Cloud Services
Venue: arXiv cs.DC 2013
Year: 2013

Commercial Cloud services have been increasingly supplied to customers in industry. To facilitate customers' decision makings like cost-benefit analysis or Cloud provider selection, evaluation of those Cloud services are becoming more and more crucial. However, compared with evaluation of traditional computing systems, more challenges will inevitably appear when evaluating rapidly-changing and user-uncontrollable commercial Cloud services. This paper proposes an expert system for Cloud evaluation that addresses emerging evaluation challenges in the context of Cloud Computing. Based on the knowledge and data accumulated by exploring the existing evaluation work, this expert system has been conceptually validated to be able to give suggestions and guidelines for implementing new evaluation experiments. As such, users can conveniently obtain evaluation experiences by using this expert system, which is essentially able to make existing efforts in Cloud services evaluation reusable and sustainable.
A Factor Framework for Experimental Design for Performance Evaluation of Commercial Cloud Services
Venue: arXiv cs.DC 2013
Year: 2013

Given the diversity of commercial Cloud services, performance evaluations of candidate services would be crucial and beneficial for both service customers (e.g. cost-benefit analysis) and providers (e.g. direction of service improvement). Before an evaluation implementation, the selection of suitable factors (also called parameters or variables) plays a prerequisite role in designing evaluation experiments. However, there seems a lack of systematic approaches to factor selection for Cloud services performance evaluation. In other words, evaluators randomly and intuitively concerned experimental factors in most of the existing evaluation studies. Based on our previous taxonomy and modeling work, this paper proposes a factor framework for experimental design for performance evaluation of commercial Cloud services. This framework capsules the state-of-the-practice of performance evaluation factors that people currently take into account in the Cloud Computing domain, and in turn can help facilitate designing new experiments for evaluating Cloud services.
Ontology-Based Administration of Web Directories
Venue: arXiv cs.IR 2013
Year: 2013

Administration of a Web directory and maintenance of its content and the associated structure is a delicate and labor intensive task performed exclusively by human domain experts. Subsequently there is an imminent risk of a directory structures becoming unbalanced, uneven and difficult to use to all except for a few users proficient with the particular Web directory and its domain. These problems emphasize the need to establish two important issues: i) generic and objective measures of Web directories structure quality, and ii) mechanism for fully automated development of a Web directory's structure. In this paper we demonstrate how to formally and fully integrate Web directories with the Semantic Web vision. We propose a set of criteria for evaluation of a Web directory's structure quality. Some criterion functions are based on heuristics while others require the application of ontologies. We also suggest an ontology-based algorithm for construction of Web directories. By using ontologies to describe the semantics of Web resources and Web directories' categories it is possible to define algorithms that can build or rearrange the structure of a Web directory. Assessment procedures can provide feedback and help steer the ontology-based construction process. The issues raised in the article can be equally applied to new and existing Web directories.
Virtual Machine Consolidation for Datacenter Energy Improvement
Venue: arXiv cs.DC 2013
Year: 2013

Rapid growth and proliferation of cloud computing services around the world has increased the necessity and significance of improving the energy efficiency of could implementations. Virtual machines (VM) comprise the backend of most, if not all, cloud computing services. Several VMs are often consolidated on a physical machine to better utilize its resources. We take into account the cooling and network structure of the datacenter hosting the physical machines when consolidating the VMs so that fewer racks and routers are employed, without compromising the service-level agreements, so that unused routing and cooling equipment can be turned off to reduce energy consumption. Our experimental results on four benchmarks shows that our technique improves energy consumption of servers, network equipment, and cooling systems by 2.5%, 18.8%, and 28.2% respectively, resulting in a total of 14.7% improvement on average in the entire datacenter.
Lower bounds on the minimum distance of long codes in the Lee metric
Venue: arXiv cs.IT 2013
Year: 2013

The Gilbert type bound for codes in the title is reviewed, both for small and large alphabets. Constructive lower bounds better than these existential bounds are derived from geometric codes, either over Fp or Fp2 ; or over even degree extensions of Fp: In the latter case the approach is concatena- tion with a good code for the Hamming metric as outer code and a short code for the Lee metric as an inner code. In the former case lower bounds on the minimum Lee distance are derived by algebraic geometric arguments inspired by results of Wu, Kuijper, Udaya (2007).
A Time Series Forest for Classification and Feature Extraction
Venue: arXiv cs.LG 2013
Year: 2013

We propose a tree ensemble method, referred to as time series forest (TSF), for time series classification. TSF employs a combination of the entropy gain and a distance measure, referred to as the Entrance (entropy and distance) gain, for evaluating the splits. Experimental studies show that the Entrance gain criterion improves the accuracy of TSF. TSF randomly samples features at each tree node and has a computational complexity linear in the length of a time series and can be built using parallel computing techniques such as multi-core computing used here. The temporal importance curve is also proposed to capture the important temporal characteristics useful for classification. Experimental studies show that TSF using simple features such as mean, deviation and slope outperforms strong competitors such as one-nearest-neighbor classifiers with dynamic time warping, is computationally efficient, and can provide insights into the temporal characteristics.
Analysis of Evidence Using Formal Event Reconstruction
Venue: arXiv cs.FL 2013
Year: 2013

This paper expands upon the finite state machine approach for the formal analysis of digital evidence. The proposed method may be used to support the feasibility of a given statement by testing it against a relevant system model. To achieve this, a novel method for modeling the system and evidential statements is given. The method is then examined in a case study example.
Compressed Sensing with Incremental Sparse Measurements
Venue: arXiv cs.IT 2013
Year: 2013

This paper proposes a verification-based decoding approach for reconstruction of a sparse signal with incremental sparse measurements. In its first step, the verification-based decoding algorithm is employed to reconstruct the signal with a fixed number of sparse measurements. Often, it may fail as the number of sparse measurements may be not enough, possibly due to an underestimate of the signal sparsity. However, we observe that even if this first recovery fails, many component samples of the sparse signal have been identified. Hence, it is natural to further employ incremental measurements tuned to the unidentified samples with known locations. This approach has been proven very efficiently by extensive simulations.
RIO: Minimizing User Interaction in Debugging of Knowledge Bases
Venue: arXiv cs.AI 2013
Year: 2013

The best currently known interactive debugging systems rely upon some meta-information in terms of fault probabilities in order to improve their efficiency. However, misleading meta information might result in a dramatic decrease of the performance and its assessment is only possible a-posteriori. Consequently, as long as the actual fault is unknown, there is always some risk of suboptimal interactions. In this work we present a reinforcement learning strategy that continuously adapts its behavior depending on the performance achieved and minimizes the risk of using low-quality meta information. Therefore, this method is suitable for application scenarios where reliable prior fault estimates are difficult to obtain. Using diverse real-world knowledge bases, we show that the proposed interactive query strategy is scalable, features decent reaction time, and outperforms both entropy-based and no-risk strategies on average w.r.t. required amount of user interaction.
Selecting the State-Representation in Reinforcement Learning
Venue: arXiv cs.LG 2013
Year: 2013

The problem of selecting the right state-representation in a reinforcement learning problem is considered. Several models (functions mapping past observations to a finite set) of the observations are given, and it is known that for at least one of these models the resulting state dynamics are indeed Markovian. Without knowing neither which of the models is the correct one, nor what are the probabilistic characteristics of the resulting MDP, it is required to obtain as much reward as the optimal policy for the correct model (or for the best of the correct models, if there are several). We propose an algorithm that achieves that, with a regret of order T^{2/3} where T is the horizon time.
A Tensor Approach to Learning Mixed Membership Community Models
Venue: arXiv cs.LG 2013
Year: 2013

Community detection is the task of detecting hidden communities from observed interactions. Guaranteed community detection has so far been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and provide guaranteed community detection for a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced by Airoldi et al. This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. Moreover, it contains the stochastic block model as a special case. We propose a unified approach to learning these models via a tensor spectral decomposition method. Our estimator is based on low-order moment tensor of the observed network, consisting of 3-star counts. Our learning method is fast and is based on simple linear algebraic operations, e.g. singular value decomposition and tensor power iterations. We provide guaranteed recovery of community memberships and model parameters and present a careful finite sample analysis of our learning method. As an important special case, our results match the best known scaling requirements for the (homogeneous) stochastic block model.