OpenRaiser/Intern-Atlas huggingface dataset:
Low-Rank Approximation of Weighted Tree Automata
Venue: arXiv cs.LG 2015
Year: 2015

We describe a technique to minimize weighted tree automata (WTA), a powerful formalisms that subsumes probabilistic context-free grammars (PCFGs) and latent-variable PCFGs. Our method relies on a singular value decomposition of the underlying Hankel matrix defined by the WTA. Our main theoretical result is an efficient algorithm for computing the SVD of an infinite Hankel matrix implicitly represented as a WTA. We provide an analysis of the approximation error induced by the minimization, and we evaluate our method on real-world data originating in newswire treebank. We show that the model achieves lower perplexity than previous methods for PCFG minimization, and also is much more stable due to the absence of local optima.
Color Aesthetics and Social Networks in Complete Tang Poems: Explorations and Discoveries
Venue: arXiv cs.CL 2015
Year: 2015

The Complete Tang Poems (CTP) is the most important source to study Tang poems. We look into CTP with computational tools from specific linguistic perspectives, including distributional semantics and collocational analysis. From such quantitative viewpoints, we compare the usage of "wind" and "moon" in the poems of Li Bai and Du Fu. Colors in poems function like sounds in movies, and play a crucial role in the imageries of poems. Thus, words for colors are studied, and "white" is the main focus because it is the most frequent color in CTP. We also explore some cases of using colored words in antithesis pairs that were central for fostering the imageries of the poems. CTP also contains useful historical information, and we extract person names in CTP to study the social networks of the Tang poets. Such information can then be integrated with the China Biographical Database of Harvard University.
Quantum Alternation: Prospects and Problems
Venue: arXiv cs.PL 2015
Year: 2015

We propose a notion of quantum control in a quantum programming language which permits the superposition of finitely many quantum operations without performing a measurement. This notion takes the form of a conditional construct similar to the IF statement in classical programming languages. We show that adding such a quantum IF statement to the QPL programming language simplifies the presentation of several quantum algorithms. This motivates the possibility of extending the denotational semantics of QPL to include this form of quantum alternation. We give a denotational semantics for this extension of QPL based on Kraus decompositions rather than on superoperators. Finally, we clarify the relation between quantum alternation and recursion, and discuss the possibility of lifting the semantics defined by Kraus operators to the superoperator semantics defined by Selinger.
Total and Partial Computation in Categorical Quantum Foundations
Venue: arXiv cs.LO 2015
Year: 2015

This paper uncovers the fundamental relationship between total and partial computation in the form of an equivalence of certain categories. This equivalence involves on the one hand effectuses, which are categories for total computation, introduced by Jacobs for the study of quantum/effect logic. On the other hand, it involves what we call FinPACs with effects; they are finitely partially additive categories equipped with effect algebra structures, serving as categories for partial computation. It turns out that the Kleisli category of the lift monad (-)+1 on an effectus is always a FinPAC with effects, and this construction gives rise to the equivalence. Additionally, state-and-effect triangles over FinPACs with effects are presented.
Background subtraction - separating the modeling and the inference
Venue: arXiv cs.CV 2015
Year: 2015

In its early implementations, background modeling was a process of building a model for the background of a video with a stationary camera, and identifying pixels that did not conform well to this model. The pixels that were not well-described by the background model were assumed to be moving objects. Many systems today maintain models for the foreground as well as the background, and these models compete to explain the pixels in a video. In this paper, we argue that the logical endpoint of this evolution is to simply use Bayes' rule to classify pixels. In particular, it is essential to have a background likelihood, a foreground likelihood, and a prior at each pixel. A simple application of Bayes' rule then gives a posterior probability over the label. The only remaining question is the quality of the component models: the background likelihood, the foreground likelihood, and the prior. We describe a model for the likelihoods that is built by using not only the past observations at a given pixel location, but by also including observations in a spatial neighborhood around the location. This enables us to model the influence between neighboring pixels and is an improvement over earlier pixelwise models that do not allow for such influence. Although similar in spirit to the joint domain-range model, we show that our model overcomes certain deficiencies in that model. We use a spatially dependent prior for the background and foreground. The background and foreground labels from the previous frame, after spatial smoothing to account for movement of objects,are used to build the prior for the current frame.
Background Modeling Using Adaptive Pixelwise Kernel Variances in a Hybrid Feature Space
Venue: arXiv cs.CV 2015
Year: 2015

Recent work on background subtraction has shown developments on two major fronts. In one, there has been increasing sophistication of probabilistic models, from mixtures of Gaussians at each pixel [7], to kernel density estimates at each pixel [1], and more recently to joint domainrange density estimates that incorporate spatial information [6]. Another line of work has shown the benefits of increasingly complex feature representations, including the use of texture information, local binary patterns, and recently scale-invariant local ternary patterns [4]. In this work, we use joint domain-range based estimates for background and foreground scores and show that dynamically choosing kernel variances in our kernel estimates at each individual pixel can significantly improve results. We give a heuristic method for selectively applying the adaptive kernel calculations which is nearly as accurate as the full procedure but runs much faster. We combine these modeling improvements with recently developed complex features [4] and show significant improvements on a standard backgrounding benchmark.
A Survey on 5G: The Next Generation of Mobile Communication
Venue: arXiv cs.IT 2015
Year: 2015

The rapidly increasing number of mobile devices, voluminous data, and higher data rate are pushing to rethink the current generation of the cellular mobile communication. The next or fifth generation (5G) cellular networks are expected to meet high-end requirements. The 5G networks are broadly characterized by three unique features: ubiquitous connectivity, extremely low latency, and very high-speed data transfer. The 5G networks would provide novel architectures and technologies beyond state-of-the-art architectures and technologies. In this paper, our intent is to find an answer to the question: "what will be done by 5G and how?" We investigate and discuss serious limitations of the fourth generation (4G) cellular networks and corresponding new features of 5G networks. We identify challenges in 5G networks, new technologies for 5G networks, and present a comparative study of the proposed architectures that can be categorized on the basis of energy-efficiency, network hierarchy, and network types. Interestingly, the implementation issues, e.g., interference, QoS, handoff, security-privacy, channel access, and load balancing, hugely effect the realization of 5G networks. Furthermore, our illustrations highlight the feasibility of these models through an evaluation of existing real-experiments and testbeds.
Basic requirements for proven-in-use arguments
Venue: arXiv cs.SE 2015
Year: 2015

Proven-in-use arguments are needed when pre-developed products with an in-service history are to be used in different environments than those they were originally developed for. A product may include software modules or may be stand-alone integrated hardware and software modules.The topic itself is not new, but most recent approaches have been based on elementary probability such as urn models which lead to very restrictive requirements for the system or software to which it has been applied. The aim of this paper is to base the argumentation on a general probabilistic model based on Grigelionis or Palm Khintchine theorems, so that the results can be applied to a very general class of products without unnecessary limitations. The advantage of such an approach is also that the same requirements hold for a broad class of products.
Modeling trend progression through an extension of the Polya Urn Process
Venue: arXiv cs.SI 2015
Year: 2015

Knowing how and when trends are formed is a frequently visited research goal. In our work, we focus on the progression of trends through (social) networks. We use a random graph (RG) model to mimic the progression of a trend through the network. The context of the trend is not included in our model. We show that every state of the RG model maps to a state of the Polya process. We find that the limit of the component size distribution of the RG model shows power-law behaviour. These results are also supported by simulations.
A Survey of Link Recommendation for Social Networks: Methods, Theoretical Foundations, and Future Research Directions
Venue: arXiv cs.SI 2015
Year: 2015

Link recommendation has attracted significant attentions from both industry practitioners and academic researchers. In industry, link recommendation has become a standard and most important feature in online social networks, prominent examples of which include "People You May Know" on LinkedIn and "You May Know" on Google+. In academia, link recommendation has been and remains a highly active research area. This paper surveys state-of-the-art link recommendation methods, which can be broadly categorized into learning-based methods and proximity-based methods. We further identify social and economic theories, such as social interaction theory, that underlie these methods and explain from a theoretical perspective why a link recommendation method works. Finally, we propose to extend link recommendation research in several directions that include utility-based link recommendation, diversity of link recommendation, link recommendation from incomplete data, and experimental study of link recommendation.
Abstraction Refinement Guided by a Learnt Probabilistic Model
Venue: arXiv cs.PL 2015
Year: 2015

The core challenge in designing an effective static program analysis is to find a good program abstraction -- one that retains only details relevant to a given query. In this paper, we present a new approach for automatically finding such an abstraction. Our approach uses a pessimistic strategy, which can optionally use guidance from a probabilistic model. Our approach applies to parametric static analyses implemented in Datalog, and is based on counterexample-guided abstraction refinement. For each untried abstraction, our probabilistic model provides a probability of success, while the size of the abstraction provides an estimate of its cost in terms of analysis time. Combining these two metrics, probability and cost, our refinement algorithm picks an optimal abstraction. Our probabilistic model is a variant of the Erdos-Renyi random graph model, and it is tunable by what we call hyperparameters. We present a method to learn good values for these hyperparameters, by observing past runs of the analysis on an existing codebase. We evaluate our approach on an object sensitive pointer analysis for Java programs, with two client analyses (PolySite and Downcast).
Next Generation Multicuts for Semi-Planar Graphs
Venue: arXiv cs.CV 2015
Year: 2015

We study the problem of multicut segmentation. We introduce modified versions of the Semi-PlanarCC based on bounding Lagrange multipliers. We apply our work to natural image segmentation.
A Construction of Linear Codes over $\f_{2^t}$ from Boolean Functions
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we present a construction of linear codes over $\f_{2^t}$ from Boolean functions, which is a generalization of Ding's method \cite[Theorem 9]{Ding15}. Based on this construction, we give two classes of linear codes $\tilde{\C}_{f}$ and $\C_f$ (see Theorem \ref{thm-maincode1} and Theorem \ref{thm-maincodenew}) over $\f_{2^t}$ from a Boolean function $f:\f_{q}\rightarrow \f_2$, where $q=2^n$ and $\f_{2^t}$ is some subfield of $\f_{q}$. The complete weight enumerator of $\tilde{\C}_{f}$ can be easily determined from the Walsh spectrum of $f$, while the weight distribution of the code $\C_f$ can also be easily settled. Particularly, the number of nonzero weights of $\tilde{\C}_{f}$ and $\C_f$ is the same as the number of distinct Walsh values of $f$. As applications of this construction, we show several series of linear codes over $\f_{2^t}$ with two or three weights by using bent, semibent, monomial and quadratic Boolean function $f$.
Robotics Technology in Mental Health Care
Venue: arXiv cs.RO 2015
Year: 2015

This chapter discusses the existing and future use of robotics and intelligent sensing technology in mental health care. While the use of this technology is nascent in mental health care, it represents a potentially useful tool in the practitioner's toolbox. The goal of this chapter is to provide a brief overview of the field, discuss the recent use of robotics technology in mental health care practice, explore some of the design issues and ethical issues of using robots in this space, and finally to explore the potential of emerging technology.
On the Capacity Achieving Probability Measures for Molecular Receivers
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, diffusion-based molecular commu- nication with ligand receptor receivers is studied. Information messages are assumed to be encoded via variations of the con- centration of molecules. The randomness in the ligand reception process induces uncertainty in the communication; limiting the rate of information decoding. We model the ligand receptor receiver by a set of finite-state Markov channels and study the general capacity of such a receiver. Furthermore, the i.i.d. capacity of the receiver is characterized as a lower bound for the general capacity. It is also proved that a finite support probability measure can achieve the i.i.d. capacity of the receiver. Moreover, a bound on the number of points in the support of the probability measure is obtained.
CASO: Cost-Aware Secure Outsourcing of General Computational Problems
Venue: arXiv cs.CR 2015
Year: 2015

Computation outsourcing is an integral part of cloud computing. It enables end-users to outsource their computational tasks to the cloud and utilize the shared cloud resources in a pay-per-use manner. However, once the tasks are outsourced, the end-users will lose control of their data, which may result in severe security issues especially when the data is sensitive. To address this problem, secure outsourcing mechanisms have been proposed to ensure security of the end-users' outsourced data. In this paper, we investigate outsourcing of general computational problems which constitute the mathematical basics for problems emerged from various fields such as engineering and finance. To be specific, we propose affine mapping based schemes for the problem transformation and outsourcing so that the cloud is unable to learn any key information from the transformed problem. Meanwhile, the overhead for the transformation is limited to an acceptable level compared to the computational savings introduced by the outsourcing itself. Furthermore, we develop cost-aware schemes to balance the trade-offs between end-users' various security demands and computational overhead. We also propose a verification scheme to ensure that the end-users will always receive a valid solution from the cloud. Our extensive complexity and security analysis show that our proposed Cost-Aware Secure Outsourcing (CASO) scheme is both practical and effective.
On Stabbing Queries for Generalized Longest Repeat
Venue: arXiv cs.DS 2015
Year: 2015

A longest repeat query on a string, motivated by its applications in many subfields including computational biology, asks for the longest repetitive substring(s) covering a particular string position (point query). In this paper, we extend the longest repeat query from point query to \emph{interval query}, allowing the search for longest repeat(s) covering any position interval, and thus significantly improve the usability of the solution. Our method for interval query takes a different approach using the insight from a recent work on \emph{shortest unique substrings} [1], as the prior work's approach for point query becomes infeasible in the setting of interval query. Using the critical insight from [1], we propose an indexing structure, which can be constructed in the optimal $O(n)$ time and space for a string of size $n$, such that any future interval query can be answered in $O(1)$ time. Further, our solution can find \emph{all} longest repeats covering any given interval using optimal $O(occ)$ time, where $occ$ is the number of longest repeats covering that given interval, whereas the prior $O(n)$-time and space work can find only one candidate for each point query. Experiments with real-world biological data show that our proposal is competitive with prior works, both time and space wise, while providing with the new functionality of interval queries as opposed to point queries provided by prior works.
Max-Sum Diversification, Monotone Submodular Functions and Semi-metric Spaces
Venue: arXiv cs.LG 2015
Year: 2015

In many applications such as web-based search, document summarization, facility location and other applications, the results are preferable to be both representative and diversified subsets of documents. The goal of this study is to select a good "quality", bounded-size subset of a given set of items, while maintaining their diversity relative to a semi-metric distance function. This problem was first studied by Borodin et al\cite{borodin}, but a crucial property used throughout their proof is the triangle inequality. In this modified proof, we want to relax the triangle inequality and relate the approximation ratio of max-sum diversification problem to the parameter of the relaxed triangle inequality in the normal form of the problem (i.e., a uniform matroid) and also in an arbitrary matroid.
A Survey of the Trends in Facial and Expression Recognition Databases and Methods
Venue: arXiv cs.CV 2015
Year: 2015

Automated facial identification and facial expression recognition have been topics of active research over the past few decades. Facial and expression recognition find applications in human-computer interfaces, subject tracking, real-time security surveillance systems and social networking. Several holistic and geometric methods have been developed to identify faces and expressions using public and local facial image databases. In this work we present the evolution in facial image data sets and the methodologies for facial identification and recognition of expressions such as anger, sadness, happiness, disgust, fear and surprise. We observe that most of the earlier methods for facial and expression recognition aimed at improving the recognition rates for facial feature-based methods using static images. However, the recent methodologies have shifted focus towards robust implementation of facial/expression recognition from large image databases that vary with space (gathered from the internet) and time (video recordings). The evolution trends in databases and methodologies for facial and expression recognition can be useful for assessing the next-generation topics that may have applications in security systems or personal identification systems that involve "Quantitative face" assessments.
A Winner-Take-All Approach to Emotional Neural Networks with Universal Approximation Property
Venue: arXiv cs.AI 2015
Year: 2015

Here, we propose a brain-inspired winner-take-all emotional neural network (WTAENN) and prove the universal approximation property for the novel architecture. WTAENN is a single layered feedforward neural network that benefits from the excitatory, inhibitory, and expandatory neural connections as well as the winner-take-all (WTA) competitions in the human brain s nervous system. The WTA competition increases the information capacity of the model without adding hidden neurons. The universal approximation capability of the proposed architecture is illustrated on two example functions, trained by a genetic algorithm, and then applied to several competing recent and benchmark problems such as in curve fitting, pattern recognition, classification and prediction. In particular, it is tested on twelve UCI classification datasets, a facial recognition problem, three real world prediction problems (2 chaotic time series of geomagnetic activity indices and wind farm power generation data), two synthetic case studies with constant and nonconstant noise variance as well as k-selector and linear programming problems. Results indicate the general applicability and often superiority of the approach in terms of higher accuracy and lower model complexity, especially where low computational complexity is imperative.
Poisson Inverse Problems by the Plug-and-Play scheme
Venue: arXiv cs.CV 2015
Year: 2015

The Anscombe transform offers an approximate conversion of a Poisson random variable into a Gaussian one. This transform is important and appealing, as it is easy to compute, and becomes handy in various inverse problems with Poisson noise contamination. Solution to such problems can be done by first applying the Anscombe transform, then applying a Gaussian-noise-oriented restoration algorithm of choice, and finally applying an inverse Anscombe transform. The appeal in this approach is due to the abundance of high-performance restoration algorithms designed for white additive Gaussian noise (we will refer to these hereafter as "Gaussian-solvers"). This process is known to work well for high SNR images, where the Anscombe transform provides a rather accurate approximation. When the noise level is high, the above path loses much of its effectiveness, and the common practice is to replace it with a direct treatment of the Poisson distribution. Naturally, with this we lose the ability to leverage on vastly available Gaussian-solvers. In this work we suggest a novel method for coupling Gaussian denoising algorithms to Poisson noisy inverse problems, which is based on a general approach termed "Plug-and-Play". Deploying the Plug-and-Play approach to such problems leads to an iterative scheme that repeats several key steps: 1) A convex programming task of simple form that can be easily treated; 2) A powerful Gaussian denoising algorithm of choice; and 3) A simple update step. Such a modular method, just like the Anscombe transform, enables other developers to plug their own Gaussian denoising algorithms to our scheme in an easy way. While the proposed method bares some similarity to the Anscombe operation, it is in fact based on a different mathematical basis, which holds true for all SNR ranges.