OpenRaiser/Intern-Atlas huggingface dataset:
Bayesian Error-Bars for Belief Net Inference
Venue: arXiv cs.AI 2013
Year: 2013

A Bayesian Belief Network (BN) is a model of a joint distribution over a setof n variables, with a DAG structure to represent the immediate dependenciesbetween the variables, and a set of parameters (aka CPTables) to represent thelocal conditional probabilities of a node, given each assignment to itsparents. In many situations, these parameters are themselves random variables - this may reflect the uncertainty of the domain expert, or may come from atraining sample used to estimate the parameter values. The distribution overthese "CPtable variables" induces a distribution over the response the BNwill return to any "What is Pr(H | E)?" query. This paper investigates thevariance of this response, showing first that it is asymptotically normal,then providing its mean and asymptotical variance. We then present aneffective general algorithm for computing this variance, which has the samecomplexity as simply computing the (mean value of) the response itself - ie,O(n 2^w), where n is the number of variables and w is the effective treewidth. Finally, we provide empirical evidence that this algorithm, whichincorporates assumptions and approximations, works effectively in practice,given only small samples.
Cross-covariance modelling via DAGs with hidden variables
Venue: arXiv cs.LG 2013
Year: 2013

DAG models with hidden variables present many difficulties that are not present when all nodes are observed. In particular, fully observed DAG models are identified and correspond to well-defined sets ofdistributions, whereas this is not true if nodes are unobserved. Inthis paper we characterize exactly the set of distributions given by a class of one-dimensional Gaussian latent variable models. These models relate two blocks of observed variables, modeling only the cross-covariance matrix. We describe the relation of this model to the singular value decomposition of the cross-covariance matrix. We show that, although the model is underidentified, useful information may be extracted. We further consider an alternative parametrization in which one latent variable is associated with each block. Our analysis leads to some novel covariance equivalence results for Gaussian hidden variable models.
A New Approach for Solving Singular Systems in Topology Optimization Using Krylov Subspace Methods
Venue: arXiv cs.CE 2013
Year: 2013

In topology optimization, the design parameter with no contribution to the objective function vanishes. This causes the stiffness matrix to become singular. We show that a local optimal solution is obtained by Conjugate Residual Method and Conjugate Gradient Method even if the stiffness matrix becomes singular. We prove that CGMconverges to a local optimal solution in that case. Computer simulation shows that CGM gives the same solutions obtained by CRM in case of a cantilever beam problem.
Completely Positive formulation of the Graph Isomorphism Problem
Venue: arXiv cs.DS 2013
Year: 2013

Given two graphs $G_1$ and $G_2$ on $n$ vertices each, we define a graph $G$ on vertex set $V_1\times V_2$ and the edge set as the union of edges of $G_1\times \bar{G_2}$, $\bar{G_1}\times G_2$, $\{(v,u'),(v,u"))(|u',u"\in V_2\}$ for each $v\in V_1$, and $\{((u',v),(u",v))|u',u"\in V_1\}$ for each $v\in V_2$. We consider the completely-positive Lovász $\vartheta$ function, i.e., $cp\vartheta$ function for $G$. We show that the function evaluates to $n$ whenever $G_1$ and $G_2$ are isomorphic and to less than $n-1/(4n^4)$ when non-isomorphic. Hence this function provides a test for graph isomorphism. We also provide some geometric insight into the feasible region of the completely positive program.
Science 3.0: Corrections to the Science 2.0 paradigm
Venue: arXiv cs.DL 2013
Year: 2013

The concept of Science 2.0 was introduced almost a decade ago to describe the new generation of online-based tools for researchers allowing easier data sharing, collaboration and publishing. Although technically sound, the concept still does not work as expected. Here we provide a systematic line of arguments to modify the concept of Science 2.0, making it more consistent with the spirit and traditions of science and Internet. Our first correction to the Science 2.0 paradigm concerns the open-access publication models charging fees to the authors. As discussed elsewhere, we show that the monopoly of such publishing models increases biases and inequalities in the representation of scientific ideas based on the author's income. Our second correction concerns post-publication comments online, which are all essentially non-anonymous in the current Science 2.0 paradigm. We conclude that scientific post-publication discussions require special anonymization systems. We further analyze the reasons of the failure of the current post-publication peer-review models and suggest what needs to be changed in Science 3.0 to convert Internet into a large journal club.
Robust Text Detection in Natural Scene Images
Venue: arXiv cs.CV 2013
Year: 2013

Text detection in natural scene images is an important prerequisite for many content-based image analysis tasks. In this paper, we propose an accurate and robust method for detecting texts in natural scene images. A fast and effective pruning algorithm is designed to extract Maximally Stable Extremal Regions (MSERs) as character candidates using the strategy of minimizing regularized variations. Character candidates are grouped into text candidates by the ingle-link clustering algorithm, where distance weights and threshold of the clustering algorithm are learned automatically by a novel self-training distance metric learning algorithm. The posterior probabilities of text candidates corresponding to non-text are estimated with an character classifier; text candidates with high probabilities are then eliminated and finally texts are identified with a text classifier. The proposed system is evaluated on the ICDAR 2011 Robust Reading Competition dataset; the f measure is over 76% and is significantly better than the state-of-the-art performance of 71%. Experimental results on a publicly available multilingual dataset also show that our proposed method can outperform the other competitive method with the f measure increase of over 9 percent. Finally, we have setup an online demo of our proposed scene text detection system at http://kems.ustb.edu.cn/learning/yin/dtext.
Nash equilibria with partial monitoring; Computation and Lemke-Howson algorithm
Venue: arXiv cs.GT 2013
Year: 2013

In two player bi-matrix games with partial monitoring, actions played are not observed, only some messages are received. Those games satisfy a crucial property of usual bi-matrix games: there are only a finite number of required (mixed) best replies. This is very helpful while investigating sets of Nash equilibria: for instance, in some cases, it allows to relate it to the set of equilibria of some auxiliary game with full monitoring. In the general case, the Lemke-Howson algorithm is extended and, under some genericity assumption, its output are Nash equilibria of the original game. As a by product, we obtain an oddness property on their number.
On the Power of Many One-Bit Provers
Venue: arXiv cs.CC 2013
Year: 2013

We study the class of languages, denoted by $\MIP[k, 1-ε, s]$, which have $k$-prover games where each prover just sends a \emph{single} bit, with completeness $1-ε$ and soundness error $s$. For the case that $k=1$ (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson ({\em Computational Complexity'02}) demonstrate that $\SZK$ exactly characterizes languages having 1-bit proof systems with"non-trivial" soundness (i.e., $1/2 < s \leq 1-2ε$). We demonstrate that for the case that $k\geq 2$, 1-bit $k$-prover games exhibit a significantly richer structure: + (Folklore) When $s \leq \frac{1}{2^k} - ε$, $\MIP[k, 1-ε, s] = \BPP$; + When $\frac{1}{2^k} + ε\leq s < \frac{2}{2^k}-ε$, $\MIP[k, 1-ε, s] = \SZK$; + When $s \ge \frac{2}{2^k} + ε$, $\AM \subseteq \MIP[k, 1-ε, s]$; + For $s \le 0.62 k/2^k$ and sufficiently large $k$, $\MIP[k, 1-ε, s] \subseteq \EXP$; + For $s \ge 2k/2^{k}$, $\MIP[k, 1, 1-ε, s] = \NEXP$. As such, 1-bit $k$-prover games yield a natural "quantitative" approach to relating complexity classes such as $\BPP$,$\SZK$,$\AM$, $\EXP$, and $\NEXP$. We leave open the question of whether a more fine-grained hierarchy (between $\AM$ and $\NEXP$) can be established for the case when $s \geq \frac{2}{2^k} + ε$.
Rateless Resilient Network Coding Against Byzantine Adversaries
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers rateless network error correction codes for reliable multicast in the presence of adversarial errors. Most existing network error correction codes are designed for a given network capacity and maximum number of errors known a priori to the encoder and decoder. However, in certain practical settings it may be necessary to operate without such a priori knowledge. We present rateless coding schemes for two adversarial models, where the source sends more redundancy over time, until decoding succeeds. The first model assumes there is a secret channel between the source and the destination that the adversaries cannot overhear. The rate of the channel is negligible compared to the main network. In the second model, instead of a secret channel, the source and destination share random secrets independent of the input information. The amount of secret information required is negligible compared to the amount of information sent. Both schemes are optimal in that decoding succeeds with high probability when the total amount of information received by the sink satisfies the cut set bound with respect to the amount of message and error information. The schemes are distributed, polynomial-time and end-to-end in that other than the source and destination nodes, other intermediate nodes carry out classical random linear network coding.
Conditions on the generator for forging ElGamal signature
Venue: arXiv cs.CR 2013
Year: 2013

This paper describes new conditions on parameters selection that lead to an efficient algorithm for forging ElGamal digital signature. Our work is inspired by Bleichenbacher's ideas.
Novel Subcarrier-pair based Opportunistic DF Protocol for Cooperative Downlink OFDMA
Venue: arXiv cs.IT 2013
Year: 2013

A novel subcarrier-pair based opportunistic DF protocol is proposed for cooperative downlink OFDMA transmission aided by a decode-and-forward (DF) relay. Specifically, user message bits are transmitted in two consecutive equal-duration time slots. A subcarrier in the first slot can be paired with a subcarrier in the second slot for the DF relay-aided transmission to a user. In particular, the source and the relay can transmit simultaneously to implement beamforming at the subcarrier in the second slot for the relay-aided transmission. Each unpaired subcarrier in either the first or second slot is used by the source for direct transmission to a user without the relay's assistance. The sum rate maximized resource allocation (RA) problem is addressed for this protocol under a total power constraint. It is shown that the novel protocol leads to a maximum sum rate greater than or equal to that for a benchmark one, which does not allow the source to implement beamforming at the subcarrier in the second slot for the relay-aided transmission. Then, a polynomial-complexity RA algorithm is developed to find an (at least approximately) optimum resource allocation (i.e., source/relay power, subcarrier pairing and assignment to users) for either the proposed or benchmark protocol. Numerical experiments illustrate that the novel protocol can lead to a much greater sum rate than the benchmark one.
A Low-Complexity Encoding of Quasi-Cyclic Codes Based on Galois Fourier Transform
Venue: arXiv cs.IT 2013
Year: 2013

The encoding complexity of a general (en,ek) quasi-cyclic code is O[(e^2)(n-k)k]. This paper presents a novel low-complexity encoding algorithm for quasi-cyclic (QC) codes based on matrix transformation. First, a message vector is encoded into a transformed codeword in the transform domain. Then, the transmitted codeword is obtained from the transformed codeword by the inverse Galois Fourier transform. For binary QC codes, a simple and fast mapping is required to post-process the transformed codeword such that the transmitted codeword is binary as well. The complexity of our proposed encoding algorithm is O[e(n-k)k] symbol operations for non-binary codes and O[ek(n-k)(log_2 e)] bit operations for binary codes. These complexities are much lower than their traditional counterpart O[(e^2)(n-k)k]. For example, our complexity of encoding a 64-ary (4095,2160) QC code is only 1.59% of that of traditional encoding, and our complexities of encoding the binary (4095, 2160) and (8176, 7154) QC codes are respectively 9.52% and 1.77% of those of traditional encoding. We also study the application of our low-complexity encoding algorithm to one of the most important subclasses of QC codes, namely QC-LDPC codes, especially when their parity-check matrices are rank deficient.
Bicategorical Semantics for Nondeterministic Computation
Venue: arXiv cs.LO 2013
Year: 2013

We outline a bicategorical syntax for the interaction between public and private information in classical information theory. We use this to give high-level graphical definitions of encrypted communication and secret sharing protocols, including a characterization of their security properties. Remarkably, this makes it clear that the protocols have an identical abstract form to the quantum teleportation and dense coding procedures, yielding evidence of a deep connection between classical and quantum information processing. We also formulate public-key cryptography using our scheme. Specific implementations of these protocols as nondeterministic classical procedures are recovered by applying our formalism in a symmetric monoidal bicategory of matrices of relations.
Negative Imaginary Systems Theory in the Robust Control of Highly Resonant Flexible Structures
Venue: arXiv cs.SY 2013
Year: 2013

This paper covers recent developments in the theory of negative imaginary systems and their application to the control of highly resonant flexible structures. The theory of negative imaginary systems arose out of a desire to unify a number of classical methods for the control of lightly damped structures with collocated force actuators and position sensors including positive position feedback and integral force feedback. The key result is a stability result which shows why these methods are guaranteed to yield robust closed loop stability in the face of unmodelled spillover dynamics. Related results to be presented connect the theory of negative imaginary systems to positive real systems theory and a negative imaginary lemma has been established which is analogous to the positive real lemma. The paper also presents recent controller synthesis results based on the theory of negative imaginary systems.
Saturating Auto-Encoders
Venue: arXiv cs.LG 2013
Year: 2013

We introduce a simple new regularizer for auto-encoders whose hidden-unit activation functions contain at least one zero-gradient (saturated) region. This regularizer explicitly encourages activations in the saturated region(s) of the corresponding activation function. We call these Saturating Auto-Encoders (SATAE). We show that the saturation regularizer explicitly limits the SATAE's ability to reconstruct inputs which are not near the data manifold. Furthermore, we show that a wide variety of features can be learned when different activation functions are used. Finally, connections are established with the Contractive and Sparse Auto-Encoders.
SkyDe: a Skype-based Steganographic Method
Venue: arXiv cs.CR 2013
Year: 2013

This paper introduces SkyDe (Skype Hide), a new steganographic method that utilizes Skype encrypted packets with silence to provide the means for clandestine communication. It is possible to reuse packets that do not carry voice signals for steganographic purposes because Skype does not use any silence suppression mechanism. The method's proof-of-concept implementation and first experimental results are presented. They prove that the method is feasible and offers steganographic bandwidth as high as 2.8 kbps.
Mandated data archiving greatly improves access to research data
Venue: arXiv cs.DL 2013
Year: 2013

The data underlying scientific papers should be accessible to researchers both now and in the future, but how best can we ensure that these data are available? Here we examine the effectiveness of four approaches to data archiving: no stated archiving policy, recommending (but not requiring) archiving, and two versions of mandating data deposition at acceptance. We control for differences between data types by trying to obtain data from papers that use a single, widespread population genetic analysis, STRUCTURE. At one extreme, we found that mandated data archiving policies that require the inclusion of a data availability statement in the manuscript improve the odds of finding the data online almost a thousand-fold compared to having no policy. However, archiving rates at journals with less stringent policies were only very slightly higher than those with no policy at all. At one extreme, we found that mandated data archiving policies that require the inclusion of a data availability statement in the manuscript improve the odds of finding the data online almost a thousand fold compared to having no policy. However, archiving rates at journals with less stringent policies were only very slightly higher than those with no policy at all. We also assessed the effectiveness of asking for data directly from authors and obtained over half of the requested datasets, albeit with about 8 days delay and some disagreement with authors. Given the long term benefits of data accessibility to the academic community, we believe that journal based mandatory data archiving policies and mandatory data availability statements should be more widely adopted.
Switched linear encoding with rectified linear autoencoders
Venue: arXiv cs.LG 2013
Year: 2013

Several recent results in machine learning have established formal connections between autoencoders---artificial neural network models that attempt to reproduce their inputs---and other coding models like sparse coding and K-means. This paper explores in depth an autoencoder model that is constructed using rectified linear activations on its hidden units. Our analysis builds on recent results to further unify the world of sparse linear coding models. We provide an intuitive interpretation of the behavior of these coding models and demonstrate this intuition using small, artificial datasets with known distributions.
Separation Properties of Sets of Probability Measures
Venue: arXiv cs.AI 2013
Year: 2013

This paper analyzes independence concepts for sets of probability measures associated with directed acyclic graphs. The paper shows that epistemic independence and the standard Markov condition violate desirable separation properties. The adoption of a contraction condition leads to d-separation but still fails to guarantee a belief separation property. To overcome this unsatisfactory situation, a strong Markov condition is proposed, based on epistemic independence. The main result is that the strong Markov condition leads to strong independence and does enforce separation properties; this result implies that (1) separation properties of Bayesian networks do extend to epistemic independence and sets of probability measures, and (2) strong independence has a clear justification based on epistemic independence and the strong Markov condition.
Experiments with Random Projection
Venue: arXiv cs.LG 2013
Year: 2013

Recent theoretical work has identified random projection as a promising dimensionality reduction technique for learning mixtures of Gausians. Here we summarize these results and illustrate them by a wide variety of experiments on synthetic and real data.
Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks
Venue: arXiv cs.LG 2013
Year: 2013

Particle filters (PFs) are powerful sampling-based inference/learning algorithms for dynamic Bayesian networks (DBNs). They allow us to treat, in a principled way, any type of probability distribution, nonlinearity and non-stationarity. They have appeared in several fields under such names as "condensation", "sequential Monte Carlo" and "survival of the fittest". In this paper, we show how we can exploit the structure of the DBN to increase the efficiency of particle filtering, using a technique known as Rao-Blackwellisation. Essentially, this samples some of the variables, and marginalizes out the rest exactly, using the Kalman filter, HMM filter, junction tree algorithm, or any other finite dimensional optimal filter. We show that Rao-Blackwellised particle filters (RBPFs) lead to more accurate estimates than standard PFs. We demonstrate RBPFs on two problems, namely non-stationary online regression with radial basis function networks and robot localization and map building. We also discuss other potential application areas and provide references to some finite dimensional optimal filters.
Maximum Entropy and the Glasses You Are Looking Through
Venue: arXiv cs.AI 2013
Year: 2013

We give an interpretation of the Maximum Entropy (MaxEnt) Principle in game-theoretic terms. Based on this interpretation, we make a formal distinction between different ways of {em applying/} Maximum Entropy distributions. MaxEnt has frequently been criticized on the grounds that it leads to highly representation dependent results. Our distinction allows us to avoid this problem in many cases.
Making Sensitivity Analysis Computationally Efficient
Venue: arXiv cs.AI 2013
Year: 2013

To investigate the robustness of the output probabilities of a Bayesian network, a sensitivity analysis can be performed. A one-way sensitivity analysis establishes, for each of the probability parameters of a network, a function expressing a posterior marginal probability of interest in terms of the parameter. Current methods for computing the coefficients in such a function rely on a large number of network evaluations. In this paper, we present a method that requires just a single outward propagation in a junction tree for establishing the coefficients in the functions for all possible parameters; in addition, an inward propagation is required for processing evidence. Conversely, the method requires a single outward propagation for computing the coefficients in the functions expressing all possible posterior marginals in terms of a single parameter. We extend these results to an n-way sensitivity analysis in which sets of parameters are studied.
Conversation as Action Under Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

Conversations abound with uncetainties of various kinds. Treating conversation as inference and decision making under uncertainty, we propose a task independent, multimodal architecture for supporting robust continuous spoken dialog called Quartet. We introduce four interdependent levels of analysis, and describe representations, inference procedures, and decision strategies for managing uncertainties within and between the levels. We highlight the approach by reviewing interactions between a user and two spoken dialog systems developed using the Quartet architecture: Prsenter, a prototype system for navigating Microsoft PowerPoint presentations, and the Bayesian Receptionist, a prototype system for dealing with tasks typically handled by front desk receptionists at the Microsoft corporate campus.