OpenRaiser/Intern-Atlas huggingface dataset:
On $r$-Simple $k$-Path
Venue: arXiv cs.DS 2014
Year: 2014

An $r$-simple $k$-path is a {path} in the graph of length $k$ that passes through each vertex at most $r$ times. The $r$-SIMPLE $k$-PATH problem, given a graph $G$ as input, asks whether there exists an $r$-simple $k$-path in $G$. We first show that this problem is NP-Complete. We then show that there is a graph $G$ that contains an $r$-simple $k$-path and no simple path of length greater than $4\log k/\log r$. So this, in a sense, motivates this problem especially when one's goal is to find a short path that visits many vertices in the graph while bounding the number of visits at each vertex. We then give a randomized algorithm that runs in time $$\mathrm{poly}(n)\cdot 2^{O( k\cdot \log r/r)}$$ that solves the $r$-SIMPLE $k$-PATH on a graph with $n$ vertices with one-sided error. We also show that a randomized algorithm with running time $\mathrm{poly}(n)\cdot 2^{(c/2)k/ r}$ with $c<1$ gives a randomized algorithm with running time $\poly(n)\cdot 2^{cn}$ for the Hamiltonian path problem in a directed graph - an outstanding open problem. So in a sense our algorithm is optimal up to an $O(\log r)$ factor.
Estimation of Human Body Shape and Posture Under Clothing
Venue: arXiv cs.CV 2014
Year: 2014

Estimating the body shape and posture of a dressed human subject in motion represented as a sequence of (possibly incomplete) 3D meshes is important for virtual change rooms and security. To solve this problem, statistical shape spaces encoding human body shape and posture variations are commonly used to constrain the search space for the shape estimate. In this work, we propose a novel method that uses a posture-invariant shape space to model body shape variation combined with a skeleton-based deformation to model posture variation. Our method can estimate the body shape and posture of both static scans and motion sequences of dressed human body scans. In case of motion sequences, our method takes advantage of motion cues to solve for a single body shape estimate along with a sequence of posture estimates. We apply our approach to both static scans and motion sequences and demonstrate that using our method, higher fitting accuracy is achieved than when using a variant of the popular SCAPE model as statistical model.
k-Sparse Autoencoders
Venue: arXiv cs.LG 2014
Year: 2014

Recently, it has been observed that when representations are learnt in a way that encourages sparsity, improved performance is obtained on classification tasks. These methods involve combinations of activation functions, sampling steps and different kinds of penalties. To investigate the effectiveness of sparsity by itself, we propose the k-sparse autoencoder, which is an autoencoder with linear activation function, where in hidden layers only the k highest activities are kept. When applied to the MNIST and NORB datasets, we find that this method achieves better classification results than denoising autoencoders, networks trained with dropout, and RBMs. k-sparse autoencoders are simple to train and the encoding stage is very fast, making them well-suited to large problem sizes, where conventional sparse coding algorithms cannot be applied.
Exploring Regional Development of Digital Humanities Research: A Case Study for Taiwan
Venue: arXiv cs.DL 2014
Year: 2014

This study analyzed references and source papers of the Proceedings of 2009-2012 International Conference of Digital Archives and Digital Humanities (DADH), which was held annually in Taiwan. A total of 59 sources and 1,104 references were investigated, based on descriptive analysis and subject analysis of library practices on cataloguing. Preliminary results showed historical materials, events, bureaucracies, and people of Taiwan and China in the Qing Dynasty were the major subjects in the tempo-spatial dimensions. The subject-date figure depicted a long-low head and short-high tail curve, which demonstrated both characteristics of research of humanities and application of technology in digital humanities. The dates of publication of the references spanned over 360 years, which shows a long time span in research materials. A majority of the papers (61.41%) were single-authored, which is in line with the common research practice in the humanities. Books published by general publishers were the major type of references, and this was the same as that of established humanities research. The next step of this study will focus on the comparison of characteristics of both sources and references of international journals with those reported in this article.
Dual-Branch MRC Receivers under Spatial Interference Correlation and Nakagami Fading
Venue: arXiv cs.IT 2014
Year: 2014

Despite being ubiquitous in practice, the performance of maximal-ratio combining (MRC) in the presence of interference is not well understood. Because the interference received at each antenna originates from the same set of interferers, but partially de-correlates over the fading channel, it possesses a complex correlation structure. This work develops a realistic analytic model that accurately accounts for the interference correlation using stochastic geometry. Modeling interference by a Poisson shot noise process with independent Nakagami fading, we derive the link success probability for dual-branch interference-aware MRC. Using this result, we show that the common assumption that all receive antennas experience equal interference power underestimates the true performance, although this gap rapidly decays with increasing the Nakagami parameter $m_{\text{I}}$ of the interfering links. In contrast, ignoring interference correlation leads to a highly optimistic performance estimate for MRC, especially for large $m_{\text{I}}$. In the low outage probability regime, our success probability expression can be considerably simplified. Observations following from the analysis include: (i) for small path loss exponents, MRC and minimum mean square error combining exhibit similar performance, and (ii) the gains of MRC over selection combining are smaller in the interference-limited case than in the well-studied noise-limited case.
Efficient Solution of a Class of Quantified Constraints with Quantifier Prefix Exists-Forall
Venue: arXiv cs.LO 2014
Year: 2014

In various applications the search for certificates for certain properties (e.g., stability of dynamical systems, program termination) can be formulated as a quantified constraint solving problem with quantifier prefix exists-forall. In this paper, we present an algorithm for solving a certain class of such problems based on interval techniques in combination with conservative linear programming approximation. In comparison with previous work, the method is more general - allowing general Boolean structure in the input constraint, and more efficient - using splitting heuristics that learn from the success of previous linear programming approximations.
Distinction between features extracted using deep belief networks
Venue: arXiv cs.LG 2014
Year: 2014

Data representation is an important pre-processing step in many machine learning algorithms. There are a number of methods used for this task such as Deep Belief Networks (DBNs) and Discrete Fourier Transforms (DFTs). Since some of the features extracted using automated feature extraction methods may not always be related to a specific machine learning task, in this paper we propose two methods in order to make a distinction between extracted features based on their relevancy to the task. We applied these two methods to a Deep Belief Network trained for a face recognition task.
Shape and Content: Incorporating Domain Knowledge into Shape Analysis
Venue: arXiv cs.PL 2014
Year: 2014

The verification community has studied dynamic data structures primarily in a bottom-up way by analyzing pointers and the shapes induced by them. Recent work in fields such as separation logic has made significant progress in extracting shapes from program source code. Many real world programs however manipulate complex data whose structure and content is most naturally described by formalisms from object oriented programming and databases. In this paper, we look at the verification of programs with dynamic data structures from the perspective of content representation. Our approach is based on description logic, a widely used knowledge representation paradigm which gives a logical underpinning for diverse modeling frameworks such as UML and ER. Technically, we assume that we have separation logic shape invariants obtained from a shape analysis tool, and requirements on the program data in terms of description logic. We show that the two-variable fragment of first order logic with counting and trees %(whose decidability was proved at LICS 2013) can be used as a joint framework to embed suitable fragments of description logic and separation logic.
Active Discovery of Network Roles for Predicting the Classes of Network Nodes
Venue: arXiv cs.LG 2014
Year: 2014

Nodes in real world networks often have class labels, or underlying attributes, that are related to the way in which they connect to other nodes. Sometimes this relationship is simple, for instance nodes of the same class are may be more likely to be connected. In other cases, however, this is not true, and the way that nodes link in a network exhibits a different, more complex relationship to their attributes. Here, we consider networks in which we know how the nodes are connected, but we do not know the class labels of the nodes or how class labels relate to the network links. We wish to identify the best subset of nodes to label in order to learn this relationship between node attributes and network links. We can then use this discovered relationship to accurately predict the class labels of the rest of the network nodes. We present a model that identifies groups of nodes with similar link patterns, which we call network roles, using a generative blockmodel. The model then predicts labels by learning the mapping from network roles to class labels using a maximum margin classifier. We choose a subset of nodes to label according to an iterative margin-based active learning strategy. By integrating the discovery of network roles with the classifier optimisation, the active learning process can adapt the network roles to better represent the network for node classification. We demonstrate the model by exploring a selection of real world networks, including a marine food web and a network of English words. We show that, in contrast to other network classifiers, this model achieves good classification accuracy for a range of networks with different relationships between class labels and network links.
Extending Contexts with Ontologies for Multidimensional Data Quality Assessment
Venue: arXiv cs.DB 2014
Year: 2014

Data quality and data cleaning are context dependent activities. Starting from this observation, in previous work a context model for the assessment of the quality of a database instance was proposed. In that framework, the context takes the form of a possibly virtual database or data integration system into which a database instance under quality assessment is mapped, for additional analysis and processing, enabling quality assessment. In this work we extend contexts with dimensions, and by doing so, we make possible a multidimensional assessment of data quality assessment. Multidimensional contexts are represented as ontologies written in Datalog+-. We use this language for representing dimensional constraints, and dimensional rules, and also for doing query answering based on dimensional navigation, which becomes an important auxiliary activity in the assessment of data. We show ideas and mechanisms by means of examples.
On the Complexity of Temporal-Logic Path Checking
Venue: arXiv cs.LO 2014
Year: 2014

Given a formula in a temporal logic such as LTL or MTL, a fundamental problem is the complexity of evaluating the formula on a given finite word. For LTL, the complexity of this task was recently shown to be in NC. In this paper, we present an NC algorithm for MTL, a quantitative (or metric) extension of LTL, and give an NCC algorithm for UTL, the unary fragment of LTL. At the time of writing, MTL is the most expressive logic with an NC path-checking algorithm, and UTL is the most expressive fragment of LTL with a more efficient path-checking algorithm than for full LTL (subject to standard complexity-theoretic assumptions). We then establish a connection between LTL path checking and planar circuits, which we exploit to show that any further progress in determining the precise complexity of LTL path checking would immediately entail more efficient evaluation algorithms than are known for a certain class of planar circuits. The connection further implies that the complexity of LTL path checking depends on the Boolean connectives allowed: adding Boolean exclusive or yields a temporal logic with P-complete path-checking problem.
A discretization-free sparse and parametric approach for linear array signal processing
Venue: arXiv cs.IT 2014
Year: 2014

Direction of arrival (DOA) estimation in array processing using uniform/sparse linear arrays is concerned in this paper. While sparse methods via approximate parameter discretization have been popular in the past decade, the discretization may cause problems, e.g., modeling error and increased computations due to dense sampling. In this paper, an exact discretization-free method, named as sparse and parametric approach (SPA), is proposed for uniform and sparse linear arrays. SPA carries out parameter estimation in the continuous range based on well-established covariance fitting criteria and convex optimization. It guarantees to produce a sparse parameter estimate without discretization required by existing sparse methods. Theoretical analysis shows that the SPA parameter estimator is a large-snapshot realization of the maximum likelihood estimator and is statistically consistent (in the number of snapshots) under uncorrelated sources. Other merits of SPA include improved resolution, applicability to arbitrary number of snapshots, robustness to correlation of the sources and no requirement of user-parameters. Numerical simulations are carried out to verify our analysis and demonstrate advantages of SPA compared to existing methods.
Separating a Voronoi Diagram via Local Search
Venue: arXiv cs.CG 2014
Year: 2014

Given a set $\mathsf{P}$ of $n$ points in $\mathbb{R}^d$, we show how to insert a set $\mathsf{X}$ of $O( n^{1-1/d} )$ additional points, such that $\mathsf{P}$ can be broken into two sets $\mathsf{P}_1$ and $\mathsf{P}_2$, of roughly equal size, such that in the Voronoi diagram $\mathcal{V}( \mathsf{P} \cup \mathsf{X} )$, the cells of $\mathsf{P}_1$ do not touch the cells of $\mathsf{P}_2$; that is, $\mathsf{X}$ separates $\mathsf{P}_1$ from $\mathsf{P}_2$ in the Voronoi diagram. Given such a partition $(\mathsf{P}_1,\mathsf{P}_2)$ of $\mathsf{P}$, we present approximation algorithms to compute the minimum size separator realizing this partition. Finally, we present a simple local search algorithm that is a PTAS for geometric hitting set of fat objects (which can also be used to approximate the optimal Voronoi partition).
A Review: Expert System for Diagnosis of Myocardial Infarction
Venue: arXiv cs.AI 2014
Year: 2014

A computer Program Capable of performing at a human-expert level in a narrow problem domain area is called an expert system. Management of uncertainty is an intrinsically important issue in the design of expert systems because much of the information in the knowledge base of a typical expert system is imprecise, incomplete or not totally reliable. In this paper, the author present s the review of past work that has been carried out by various researchers based on development of expert systems for the diagnosis of cardiac disease
Schur Complement Based Analysis of MIMO Zero-Forcing for Rician Fading
Venue: arXiv cs.IT 2014
Year: 2014

For multiple-input/multiple-output (MIMO) spatial multiplexing with zero-forcing detection (ZF), signal-to-noise ratio (SNR) analysis for Rician fading involves the cumbersome noncentral-Wishart distribution (NCWD) of the transmit sample-correlation (Gramian) matrix. An \textsl{approximation} with a \textsl{virtual} CWD previously yielded for the ZF SNR an approximate (virtual) Gamma distribution. However, analytical conditions qualifying the accuracy of the SNR-distribution approximation were unknown. Therefore, we have been attempting to exactly characterize ZF SNR for Rician fading. Our previous attempts succeeded only for the sole Rician-fading stream under Rician--Rayleigh fading, by writing it as scalar Schur complement (SC) in the Gramian. Herein, we pursue a more general, matrix-SC-based analysis to characterize SNRs when several streams may undergo Rician fading. On one hand, for full-Rician fading, the SC distribution is found to be exactly a CWD if and only if a channel-mean--correlation \textsl{condition} holds. Interestingly, this CWD then coincides with the \textsl{virtual} CWD ensuing from the \textsl{approximation}. Thus, under the \textsl{condition}, the actual and virtual SNR-distributions coincide. On the other hand, for Rician--Rayleigh fading, the matrix-SC distribution is characterized in terms of determinant of matrix with elementary-function entries, which also yields a new characterization of the ZF SNR. Average error probability results validate our analysis vs.~simulation.
Unification modulo a 2-sorted Equational theory for Cipher-Decipher Block Chaining
Venue: arXiv cs.LO 2014
Year: 2014

We investigate unification problems related to the Cipher Block Chaining (CBC) mode of encryption. We first model chaining in terms of a simple, convergent, rewrite system over a signature with two disjoint sorts: list and element. By interpreting a particular symbol of this signature suitably, the rewrite system can model several practical situations of interest. An inference procedure is presented for deciding the unification problem modulo this rewrite system. The procedure is modular in the following sense: any given problem is handled by a system of `list-inferences', and the set of equations thus derived between the element-terms of the problem is then handed over to any (`black-box') procedure which is complete for solving these element-equations. An example of application of this unification procedure is given, as attack detection on a Needham-Schroeder like protocol, employing the CBC encryption mode based on the associative-commutative (AC) operator XOR. The 2-sorted convergent rewrite system is then extended into one that fully captures a block chaining encryption-decryption mode at an abstract level, using no AC-symbols; and unification modulo this extended system is also shown to be decidable.
Sparsity-Aware Adaptive Algorithms Based on Alternating Optimization with Shrinkage
Venue: arXiv cs.SY 2014
Year: 2014

This letter proposes a novel sparsity-aware adaptive filtering scheme and algorithms based on an alternating optimization strategy with shrinkage. The proposed scheme employs a two-stage structure that consists of an alternating optimization of a diagonally-structured matrix that speeds up the convergence and an adaptive filter with a shrinkage function that forces the coefficients with small magnitudes to zero. We devise alternating optimization least-mean square (LMS) algorithms for the proposed scheme and analyze its mean-square error. Simulations for a system identification application show that the proposed scheme and algorithms outperform in convergence and tracking existing sparsity-aware algorithms.
Chaff from the Wheat : Characterization and Modeling of Deleted Questions on Stack Overflow
Venue: arXiv cs.IR 2014
Year: 2014

Stack Overflow is the most popular CQA for programmers on the web with 2.05M users, 5.1M questions and 9.4M answers. Stack Overflow has explicit, detailed guidelines on how to post questions and an ebullient moderation community. Despite these precise communications and safeguards, questions posted on Stack Overflow can be extremely off topic or very poor in quality. Such questions can be deleted from Stack Overflow at the discretion of experienced community members and moderators. We present the first study of deleted questions on Stack Overflow. We divide our study into two parts (i) Characterization of deleted questions over approx. 5 years (2008-2013) of data, (ii) Prediction of deletion at the time of question creation. Our characterization study reveals multiple insights on question deletion phenomena. We observe a significant increase in the number of deleted questions over time. We find that it takes substantial time to vote a question to be deleted but once voted, the community takes swift action. We also see that question authors delete their questions to salvage reputation points. We notice some instances of accidental deletion of good quality questions but such questions are voted back to be undeleted quickly. We discover a pyramidal structure of question quality on Stack Overflow and find that deleted questions lie at the bottom (lowest quality) of the pyramid. We also build a predictive model to detect the deletion of question at the creation time. We experiment with 47 features based on User Profile, Community Generated, Question Content and Syntactic style and report an accuracy of 66%. Our feature analysis reveals that all four categories of features are important for the prediction task. Our findings reveal important suggestions for content quality maintenance on community based question answering websites.
A Hybrid NN/HMM Modeling Technique for Online Arabic Handwriting Recognition
Venue: arXiv cs.CV 2014
Year: 2014

In this work we propose a hybrid NN/HMM model for online Arabic handwriting recognition. The proposed system is based on Hidden Markov Models (HMMs) and Multi Layer Perceptron Neural Networks (MLPNNs). The input signal is segmented to continuous strokes called segments based on the Beta-Elliptical strategy by inspecting the extremum points of the curvilinear velocity profile. A neural network trained with segment level contextual information is used to extract class character probabilities. The output of this network is decoded by HMMs to provide character level recognition. In evaluations on the ADAB database, we achieved 96.4% character recognition accuracy that is statistically significantly important in comparison with character recognition accuracies obtained from state-of-the-art online Arabic systems.8
Zero-Shot Learning for Semantic Utterance Classification
Venue: arXiv cs.CL 2014
Year: 2014

We propose a novel zero-shot learning method for semantic utterance classification (SUC). It learns a classifier $f: X \to Y$ for problems where none of the semantic categories $Y$ are present in the training set. The framework uncovers the link between categories and utterances using a semantic space. We show that this semantic space can be learned by deep neural networks trained on large amounts of search engine query log data. More precisely, we propose a novel method that can learn discriminative semantic features without supervision. It uses the zero-shot learning framework to guide the learning of the semantic features. We demonstrate the effectiveness of the zero-shot semantic learning algorithm on the SUC dataset collected by (Tur, 2012). Furthermore, we achieve state-of-the-art results by combining the semantic features with a supervised method.