OpenRaiser/Intern-Atlas huggingface dataset:
Web-Based Question Answering: A Decision-Making Perspective
Venue: arXiv cs.IR 2012
Year: 2012

We describe an investigation of the use of probabilistic models and cost-benefit analyses to guide resource-intensive procedures used by a Web-based question answering system. We first provide an overview of research on question-answering systems. Then, we present details on AskMSR, a prototype web-based question answering system. We discuss Bayesian analyses of the quality of answers generated by the system and show how we can endow the system with the ability to make decisions about the number of queries issued to a search engine, given the cost of queries and the expected value of query results in refining an ultimate answer. Finally, we review the results of a set of experiments.
A Robust Independence Test for Constraint-Based Learning of Causal Structure
Venue: arXiv cs.AI 2012
Year: 2012

Constraint-based (CB) learning is a formalism for learning a causal network with a database D by performing a series of conditional-independence tests to infer structural information. This paper considers a new test of independence that combines ideas from Bayesian learning, Bayesian network inference, and classical hypothesis testing to produce a more reliable and robust test. The new test can be calculated in the same asymptotic time and space required for the standard tests such as the chi-squared test, but it allows the specification of a prior distribution over parameters and can be used when the database is incomplete. We prove that the test is correct, and we demonstrate empirically that, when used with a CB causal discovery algorithm with noninformative priors, it recovers structural features more reliably and it produces networks with smaller KL-Divergence, especially as the number of nodes increases or the number of records decreases. Another benefit is the dramatic reduction in the probability that a CB algorithm will stall during the search, providing a remedy for an annoying problem plaguing CB learning when the database is small.
Using the structure of d-connecting paths as a qualitative measure of the strength of dependence
Venue: arXiv cs.AI 2012
Year: 2012

Pearls concept OF a d - connecting path IS one OF the foundations OF the modern theory OF graphical models : the absence OF a d - connecting path IN a DAG indicates that conditional independence will hold IN ANY distribution factorising according TO that graph. IN this paper we show that IN singly - connected Gaussian DAGs it IS possible TO USE the form OF a d - connection TO obtain qualitative information about the strength OF conditional dependence.More precisely, the squared partial correlations BETWEEN two given variables, conditioned ON different subsets may be partially ordered BY examining the relationship BETWEEN the d - connecting path AND the SET OF variables conditioned upon.
Budgeted Learning of Naive-Bayes Classifiers
Venue: arXiv cs.LG 2012
Year: 2012

Frequently, acquiring training data has an associated cost. We consider the situation where the learner may purchase data during training, subject TO a budget. IN particular, we examine the CASE WHERE each feature label has an associated cost, AND the total cost OF ALL feature labels acquired during training must NOT exceed the budget.This paper compares methods FOR choosing which feature label TO purchase next, given the budget AND the CURRENT belief state OF naive Bayes model parameters.Whereas active learning has traditionally focused ON myopic(greedy) strategies FOR query selection, this paper presents a tractable method FOR incorporating knowledge OF the budget INTO the decision making process, which improves performance.
LAYERWIDTH: Analysis of a New Metric for Directed Acyclic Graphs
Venue: arXiv cs.DS 2012
Year: 2012

We analyze a new property of directed acyclic graphs (DAGs), called layerwidth, arising from a class of DAGs proposed by Eiter and Lukasiewicz. This class of DAGs permits certain problems of structural model-based causality and explanation to be tractably solved. In this paper, we first address an open question raised by Eiter and Lukasiewicz - the computational complexity of deciding whether a given graph has a bounded layerwidth. After proving that this problem is NP-complete, we proceed by proving numerous important properties of layerwidth that are helpful in efficiently computing the optimal layerwidth. Finally, we compare this new DAG property to two other important DAG properties: treewidth and bandwidth.
Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models
Venue: arXiv cs.AI 2012
Year: 2012

The two most popular types of graphical model are directed models (Bayesian networks) and undirected models (Markov random fields, or MRFs). Directed and undirected models offer complementary properties in model construction, expressing conditional independencies, expressing arbitrary factorizations of joint distributions, and formulating message-passing inference algorithms. We show that the strengths of these two representations can be combined in a single type of graphical model called a 'factor graph'. Every Bayesian network or MRF can be easily converted to a factor graph that expresses the same conditional independencies, expresses the same factorization of the joint distribution, and can be used for probabilistic inference through application of a single, simple message-passing algorithm. In contrast to chain graphs, where message-passing is implemented on a hypergraph, message-passing can be directly implemented on the factor graph. We describe a modified 'Bayes-ball' algorithm for establishing conditional independence in factor graphs, and we show that factor graphs form a strict superset of Bayesian networks and MRFs. In particular, we give an example of a commonly-used 'mixture of experts' model fragment, whose independencies cannot be represented in a Bayesian network or an MRF, but can be represented in a factor graph. We finish by giving examples of real-world problems that are not well suited to representation in Bayesian networks and MRFs, but are well-suited to representation in factor graphs.
A Distance-Based Branch and Bound Feature Selection Algorithm
Venue: arXiv cs.LG 2012
Year: 2012

There is no known efficient method for selecting k Gaussian features from n which achieve the lowest Bayesian classification error. We show an example of how greedy algorithms faced with this task are led to give results that are not optimal. This motivates us to propose a more robust approach. We present a Branch and Bound algorithm for finding a subset of k independent Gaussian features which minimizes the naive Bayesian classification error. Our algorithm uses additive monotonic distance measures to produce bounds for the Bayesian classification error in order to exclude many feature subsets from evaluation, while still returning an optimal solution. We test our method on synthetic data as well as data obtained from gene expression profiling.
Systematic vs. Non-systematic Algorithms for Solving the MPE Task
Venue: arXiv cs.AI 2012
Year: 2012

The paper continues the study of partitioning based inference of heuristics for search in the context of solving the Most Probable Explanation task in Bayesian Networks. We compare two systematic Branch and Bound search algorithms, BBBT (for which the heuristic information is constructed during search and allows dynamic variable/value ordering) and its predecessor BBMB (for which the heuristic information is pre-compiled), against a number of popular local search algorithms for the MPE problem. We show empirically that, when viewed as approximation schemes, BBBT/BBMB are superior to all of these best known SLS algorithms, especially when the domain sizes increase beyond 2. This is in contrast with the performance of SLS vs. systematic search on CSP/SAT problems, where SLS often significantly outperforms systematic algorithms. As far as we know, BBBT/BBMB are currently the best performing algorithms for solving the MPE task.
Collaborative Ensemble Learning: Combining Collaborative and Content-Based Information Filtering via Hierarchical Bayes
Venue: arXiv cs.LG 2012
Year: 2012

Collaborative filtering (CF) and content-based filtering (CBF) have widely been used in information filtering applications. Both approaches have their strengths and weaknesses which is why researchers have developed hybrid systems. This paper proposes a novel approach to unify CF and CBF in a probabilistic framework, named collaborative ensemble learning. It uses probabilistic SVMs to model each user's profile (as CBF does).At the prediction phase, it combines a society OF users profiles, represented by their respective SVM models, to predict an active users preferences(the CF idea).The combination scheme is embedded in a probabilistic framework and retains an intuitive explanation.Moreover, collaborative ensemble learning does not require a global training stage and thus can incrementally incorporate new data.We report results based on two data sets. For the Reuters-21578 text data set, we simulate user ratings under the assumption that each user is interested in only one category. In the second experiment, we use users' opinions on a set of 642 art images that were collected through a web-based survey. For both data sets, collaborative ensemble achieved excellent performance in terms of recommendation accuracy.
Subtraction makes computing integers faster
Venue: arXiv cs.CC 2012
Year: 2012

We show some facts regarding the question whether, for any number $n$, the length of the shortest Addition Multiplications Chain (AMC) computing $n$ is polynomial in the length of the shortest division-free Straight Line Program (SLP) that computes $n$. If the answer to this question is "yes", then we can show a stronger upper bound for $\mathrm{PosSLP}$, the important problem which essentially captures the notion of efficient computation over the reals. If the answer is "no", then this would demonstrate how subtraction helps generating integers super-polynomially faster, given that addition and multiplication can be done in unit time. In this paper, we show that, for almost all numbers, AMCs and SLPs need same asymptotic length for computation. However, for one specific form of numbers, SLPs are strictly more powerful than AMCs by at least one step of computation.
Wireless Public key Infrastructure for Mobile Phones
Venue: arXiv cs.CR 2012
Year: 2012

Mobile devices play an important role in the wireless network environment for providing different services over internet. The business transactions over wireless electronic devices are not secure and hence the messages are prone to be intercepted and modified by an intruder. So, devices supporting wireless internet must be guaranteed at the same level of security as the wired network. PKI (Public Key Infrastructure) used in the wired environment is not suitable for wireless environment because of the less powerful processor and small memory. This arises a need for the development of a Wireless Public Key Infrastructure (WPKI) that provides the similar security level as the wired PKI suitable for mobile phone. In this paper, a discussion of public key infrastructure and an experimental set up for Wireless Public key Infrastructure for mobile phones are made.
Lossless Data Compression at Finite Blocklengths
Venue: arXiv cs.IT 2012
Year: 2012

This paper provides an extensive study of the behavior of the best achievable rate (and other related fundamental limits) in variable-length lossless compression. In the non-asymptotic regime, the fundamental limits of fixed-to-variable lossless compression with and without prefix constraints are shown to be tightly coupled. Several precise, quantitative bounds are derived, connecting the distribution of the optimal codelengths to the source information spectrum, and an exact analysis of the best achievable rate for arbitrary sources is given. Fine asymptotic results are proved for arbitrary (not necessarily prefix) compressors on general mixing sources. Non-asymptotic, explicit Gaussian approximation bounds are established for the best achievable rate on Markov sources. The source dispersion and the source varentropy rate are defined and characterized. Together with the entropy rate, the varentropy rate serves to tightly approximate the fundamental non-asymptotic limits of fixed-to-variable compression for all but very small blocklengths.
Enhanced skin colour classifier using RGB Ratio model
Venue: arXiv cs.CV 2012
Year: 2012

Skin colour detection is frequently been used for searching people, face detection, pornographic filtering and hand tracking. The presence of skin or non-skin in digital image can be determined by manipulating pixels colour or pixels texture. The main problem in skin colour detection is to represent the skin colour distribution model that is invariant or least sensitive to changes in illumination condition. Another problem comes from the fact that many objects in the real world may possess almost similar skin-tone colour such as wood, leather, skin-coloured clothing, hair and sand. Moreover, skin colour is different between races and can be different from a person to another, even with people of the same ethnicity. Finally, skin colour will appear a little different when different types of camera are used to capture the object or scene. The objective in this study is to develop a skin colour classifier based on pixel-based using RGB ratio model. The RGB ratio model is a newly proposed method that belongs under the category of an explicitly defined skin region model. This skin classifier was tested with SIdb dataset and two benchmark datasets; UChile and TDSD datasets to measure classifier performance. The performance of skin classifier was measured based on true positive (TF) and false positive (FP) indicator. This newly proposed model was compared with Kovac, Saleh and Swift models. The experimental results showed that the RGB ratio model outperformed all the other models in term of detection rate. The RGB ratio model is able to reduce FP detection that caused by reddish objects colour as well as be able to detect darkened skin and skin covered by shadow.
Near-Optimal Multi-Unit Auctions with Ordered Bidders
Venue: arXiv cs.GT 2012
Year: 2012

We construct prior-free auctions with constant-factor approximation guarantees with ordered bidders, in both unlimited and limited supply settings. We compare the expected revenue of our auctions on a bid vector to the monotone price benchmark, the maximum revenue that can be obtained from a bid vector using supply-respecting prices that are nonincreasing in the bidder ordering and bounded above by the second-highest bid. As a consequence, our auctions are simultaneously near-optimal in a wide range of Bayesian multi-unit environments.
Reducing Reconciliation Communication Cost with Compressed Sensing
Venue: arXiv cs.IT 2012
Year: 2012

We consider a reconciliation problem, where two hosts wish to synchronize their respective sets. Efficient solutions for minimizing the communication cost between the two hosts have been previously proposed in the literature. However, they rely on prior knowledge about the size of the set differences between the two sets to be reconciled. In this paper, we propose a method which can achieve comparable efficiency without assuming this prior knowledge. Our method uses compressive sensing techniques which can leverage the expected sparsity in set differences. We study the performance of the method via theoretical analysis and numerical simulations.
Identification of Nonlinear Systems From the Knowledge Around Different Operating Conditions: A Feed-Forward Multi-Layer ANN Based Approach
Venue: arXiv cs.SY 2012
Year: 2012

The paper investigates nonlinear system identification using system output data at various linearized operating points. A feed-forward multi-layer Artificial Neural Network (ANN) based approach is used for this purpose and tested for two target applications i.e. nuclear reactor power level monitoring and an AC servo position control system. Various configurations of ANN using different activation functions, number of hidden layers and neurons in each layer are trained and tested to find out the best configuration. The training is carried out multiple times to check for consistency and the mean and standard deviation of the root mean square errors (RMSE) are reported for each configuration.
A survey of service oriented architecture systems testing
Venue: arXiv cs.SE 2012
Year: 2012

Service oriented architecture (SOA) is one of the latest software architectures. This architecture is created in direction of the business requirements and removed the gap between softwares and businesses. The software testing is the rising cost of activities in development software. SOA has different specifications and features proportion of the other software architectures. First this paper reviews SOA testing challenges and existing solution(s) for those challenges. Then that reports a survey of recent research to SOA systems testing, that covers both functional and non-functional testing. Those are presented for different levels of functional testing, including unit, integration, and regression testing.
Large Scale Estimation in Cyberphysical Systems using Streaming Data: a Case Study with Smartphone Traces
Venue: arXiv cs.RO 2012
Year: 2012

Controlling and analyzing cyberphysical and robotics systems is increasingly becoming a Big Data challenge. Pushing this data to, and processing in the cloud is more efficient than on-board processing. However, current cloud-based solutions are not suitable for the latency requirements of these applications. We present a new concept, Discretized Streams or D-Streams, that enables massively scalable computations on streaming data with latencies as short as a second. We experiment with an implementation of D-Streams on top of the Spark computing framework. We demonstrate the usefulness of this concept with a novel algorithm to estimate vehicular traffic in urban networks. Our online EM algorithm can estimate traffic on a very large city network (the San Francisco Bay Area) by processing tens of thousands of observations per second, with a latency of a few seconds.
Improved Semidefinite Programming Bound on Sizes of Codes
Venue: arXiv cs.IT 2012
Year: 2012

Let $A(n,d)$ (respectively $A(n,d,w)$) be the maximum possible number of codewords in a binary code (respectively binary constant-weight $w$ code) of length $n$ and minimum Hamming distance at least $d$. By adding new linear constraints to Schrijver's semidefinite programming bound, which is obtained from block-diagonalising the Terwilliger algebra of the Hamming cube, we obtain two new upper bounds on $A(n,d)$, namely $A(18,8) \leq 71$ and $A(19,8) \leq 131$. Twenty three new upper bounds on $A(n,d,w)$ for $n \leq 28$ are also obtained by a similar way.
A Dynamic Network Approach to Breakthrough Innovation
Venue: arXiv cs.SI 2012
Year: 2012

This paper outlines a framework for the study of innovation that treats discoveries as additions to evolving networks. As inventions enter they expand or limit the reach of the ideas they build on by influencing how successive discoveries use those ideas. The approach is grounded in novel measures of the extent to which an innovation amplifies or disrupts the status quo. Those measures index the effects inventions have on subsequent uses of prior discoveries. In so doing, they characterize a theoretically important but elusive feature of innovation. We validate our approach by showing it: (1) discriminates among innovations of similar impact in analyses of U.S. patents; (2) identifies discoveries that amplify and disrupt technology streams in select case studies; (3) implies disruptive patents decrease the use of their predecessors by 60% in difference-in-differences estimation; and, (4) yields novel findings in analyses of patenting at 110 U.S. universities.
Robust Adaptive Beamforming for General-Rank Signal Model with Positive Semi-Definite Constraint via POTDC
Venue: arXiv cs.IT 2012
Year: 2012

The robust adaptive beamforming (RAB) problem for general-rank signal model with an additional positive semi-definite constraint is considered. Using the principle of the worst-case performance optimization, such RAB problem leads to a difference-of-convex functions (DC) optimization problem. The existing approaches for solving the resulted non-convex DC problem are based on approximations and find only suboptimal solutions. Here we solve the non-convex DC problem rigorously and give arguments suggesting that the solution is globally optimal. Particularly, we rewrite the problem as the minimization of a one-dimensional optimal value function whose corresponding optimization problem is non-convex. Then, the optimal value function is replaced with another equivalent one, for which the corresponding optimization problem is convex. The new one-dimensional optimal value function is minimized iteratively via polynomial time DC (POTDC) algorithm.We show that our solution satisfies the Karush-Kuhn-Tucker (KKT) optimality conditions and there is a strong evidence that such solution is also globally optimal. Towards this conclusion, we conjecture that the new optimal value function is a convex function. The new RAB method shows superior performance compared to the other state-of-the-art general-rank RAB methods.
Energy-Efficient Resource Allocation in Multiuser OFDM Systems with Wireless Information and Power Transfer
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we study the resource allocation algorithm design for multiuser orthogonal frequency division multiplexing (OFDM) downlink systems with simultaneous wireless information and power transfer. The algorithm design is formulated as a non-convex optimization problem for maximizing the energy efficiency of data transmission (bit/Joule delivered to the users). In particular, the problem formulation takes into account the minimum required system data rate, heterogeneous minimum required power transfers to the users, and the circuit power consumption. Subsequently, by exploiting the method of time-sharing and the properties of nonlinear fractional programming, the considered non-convex optimization problem is solved using an efficient iterative resource allocation algorithm. For each iteration, the optimal power allocation and user selection solution are derived based on Lagrange dual decomposition. Simulation results illustrate that the proposed iterative resource allocation algorithm achieves the maximum energy efficiency of the system and reveal how energy efficiency, system capacity, and wireless power transfer benefit from the presence of multiple users in the system.
Capacity Bounds for Dirty Paper with Exponential Dirt
Venue: arXiv cs.IT 2012
Year: 2012

The additive exponential noise channel with additive exponential interference (AENC-AEI) known non-causally at the transmitter is studied. This channel can be considered as an exponential version of the discrete memoryless channel with state known non-causally at the encoder considered by Gelfand and Pinsker. We make use of Gelfand-Pinsker classic capacity Theorem to derive inner and outer bounds on the capacity of this channel under a non-negative input constraint as well as a constraint on the mean value of the input. First we obtain an outer bound for AENC-AEI. Then by using the input distribution achieving the outer bound, we derive an inner bound which this inner bound coincides with the obtained outer bound at high signal to noise ratios (SNRs) and therefore, gives the capacity of the AENC-AEI at high SNRs.
Some Constacyclic Codes over Finite Chain Rings
Venue: arXiv cs.IT 2012
Year: 2012

For $λ$ an $n$-th power of a unit in a finite chain ring we prove that $λ$-constacyclic repeated-root codes over some finite chain rings are equivalent to cyclic codes. This allows us to simplify the structure of some constacylic codes. We also study the $α+p β$-constacyclic codes of length $p^s$ over the Galois ring $GR(p^e,r)$.