OpenRaiser/Intern-Atlas huggingface dataset:
Error-Correcting Factorization
Venue: arXiv cs.CV 2015
Year: 2015

Error Correcting Output Codes (ECOC) is a successful technique in multi-class classification, which is a core problem in Pattern Recognition and Machine Learning. A major advantage of ECOC over other methods is that the multi- class problem is decoupled into a set of binary problems that are solved independently. However, literature defines a general error-correcting capability for ECOCs without analyzing how it distributes among classes, hindering a deeper analysis of pair-wise error-correction. To address these limitations this paper proposes an Error-Correcting Factorization (ECF) method, our contribution is three fold: (I) We propose a novel representation of the error-correction capability, called the design matrix, that enables us to build an ECOC on the basis of allocating correction to pairs of classes. (II) We derive the optimal code length of an ECOC using rank properties of the design matrix. (III) ECF is formulated as a discrete optimization problem, and a relaxed solution is found using an efficient constrained block coordinate descent approach. (IV) Enabled by the flexibility introduced with the design matrix we propose to allocate the error-correction on classes that are prone to confusion. Experimental results in several databases show that when allocating the error-correction to confusable classes ECF outperforms state-of-the-art approaches.
Optimizing a Certified Proof Checker for a Large-Scale Computer-Generated Proof
Venue: arXiv cs.LO 2015
Year: 2015

In recent work, we formalized the theory of optimal-size sorting networks with the goal of extracting a verified checker for the large-scale computer-generated proof that 25 comparisons are optimal when sorting 9 inputs, which required more than a decade of CPU time and produced 27 GB of proof witnesses. The checker uses an untrusted oracle based on these witnesses and is able to verify the smaller case of 8 inputs within a couple of days, but it did not scale to the full proof for 9 inputs. In this paper, we describe several non-trivial optimizations of the algorithm in the checker, obtained by appropriately changing the formalization and capitalizing on the symbiosis with an adequate implementation of the oracle. We provide experimental evidence of orders of magnitude improvements to both runtime and memory footprint for 8 inputs, and actually manage to check the full proof for 9 inputs.
Approximating Nearest Neighbor Distances
Venue: arXiv cs.CG 2015
Year: 2015

Several researchers proposed using non-Euclidean metrics on point sets in Euclidean space for clustering noisy data. Almost always, a distance function is desired that recognizes the closeness of the points in the same cluster, even if the Euclidean cluster diameter is large. Therefore, it is preferred to assign smaller costs to the paths that stay close to the input points. In this paper, we consider the most natural metric with this property, which we call the nearest neighbor metric. Given a point set P and a path $γ$, our metric charges each point of $γ$ with its distance to P. The total charge along $γ$ determines its nearest neighbor length, which is formally defined as the integral of the distance to the input points along the curve. We describe a $(3+\varepsilon)$-approximation algorithm and a $(1+\varepsilon)$-approximation algorithm to compute the nearest neighbor metric. Both approximation algorithms work in near-linear time. The former uses shortest paths on a sparse graph using only the input points. The latter uses a sparse sample of the ambient space, to find good approximate geodesic paths.
Transducer Descriptions of DNA Code Properties and Undecidability of Antimorphic Problems
Venue: arXiv cs.FL 2015
Year: 2015

This work concerns formal descriptions of DNA code properties, and builds on previous work on transducer descriptions of classic code properties and on trajectory descriptions of DNA code properties. This line of research allows us to give a property as input to an algorithm, in addition to any regular language, which can then answer questions about the language and the property. Here we define DNA code properties via transducers and show that this method is strictly more expressive than that of trajectories, without sacrificing the efficiency of deciding the satisfaction question. We also show that the maximality question can be undecidable. Our undecidability results hold not only for the fixed DNA involution but also for any fixed antimorphic permutation. Moreover, we also show the undecidability of the antimorphic version of the Post Corresponding Problem, for any fixed antimorphic permutation.
Efficient Upsampling of Natural Images
Venue: arXiv cs.CV 2015
Year: 2015

We propose a novel method of efficient upsampling of a single natural image. Current methods for image upsampling tend to produce high-resolution images with either blurry salient edges, or loss of fine textural detail, or spurious noise artifacts. In our method, we mitigate these effects by modeling the input image as a sum of edge and detail layers, operating upon these layers separately, and merging the upscaled results in an automatic fashion. We formulate the upsampled output image as the solution to a non-convex energy minimization problem, and propose an algorithm to obtain a tractable approximate solution. Our algorithm comprises two main stages. 1) For the edge layer, we use a nonparametric approach by constructing a dictionary of patches from a given image, and synthesize edge regions in a higher-resolution version of the image. 2) For the detail layer, we use a global parametric texture enhancement approach to synthesize detail regions across the image. We demonstrate that our method is able to accurately reproduce sharp edges as well as synthesize photorealistic textures, while avoiding common artifacts such as ringing and haloing. In addition, our method involves no training phase or estimation of model parameters, and is easily parallelizable. We demonstrate the utility of our method on a number of challenging standard test photos.
Algorithms for Longest Common Abelian Factors
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we consider the problem of computing the longest common abelian factor (LCAF) between two given strings. We present a simple $O(σ~ n^2)$ time algorithm, where $n$ is the length of the strings and $σ$ is the alphabet size, and a sub-quadratic running time solution for the binary string case, both having linear space requirement. Furthermore, we present a modified algorithm applying some interesting tricks and experimentally show that the resulting algorithm runs faster.
An Efficient Coding Method for Coding Region-of-Interest Locations in AVS2
Venue: arXiv cs.MM 2015
Year: 2015

Region-of-Interest (ROI) location information in videos has many practical usages in video coding field, such as video content analysis and user experience improvement. Although ROI-based coding has been studied widely by many researchers to improve coding efficiency for video contents, the ROI location information itself is seldom coded in video bitstream. In this paper, we will introduce our proposed ROI location coding tool which has been adopted in surveillance profile of AVS2 video coding standard (surveillance profile). Our tool includes three schemes: direct-coding scheme, differential- coding scheme, and reconstructed-coding scheme. We will illustrate the details of these schemes, and perform analysis of their advantages and disadvantages, respectively.
Stabilizing Server-Based Storage in Byzantine Asynchronous Message-Passing Systems
Venue: arXiv cs.DC 2015
Year: 2015

A stabilizing Byzantine single-writer single-reader (SWSR) regular register, which stabilizes after the first invoked write operation, is first presented. Then, new/old ordering inversions are eliminated by the use of a (bounded) sequence number for writes, obtaining a practically stabilizing SWSR atomic register. A practically stabilizing Byzantine single-writer multi-reader (SWMR) atomic register is then obtained by using several copies of SWSR atomic registers. Finally, bounded time-stamps, with a time-stamp per writer, together with SWMR atomic registers, are used to construct a practically stabilizing Byzantine multi-writer multi-reader (MWMR) atomic register. In a system of $n$ servers implementing an atomic register, and in addition to transient failures, the constructions tolerate t<n/8 Byzantine servers if communication is asynchronous, and t<n/3 Byzantine servers if it is synchronous. The noteworthy feature of the proposed algorithms is that (to our knowledge) these are the first that build an atomic read/write storage on top of asynchronous servers prone to transient failures, and where up to t of them can be Byzantine.
The NLP Engine: A Universal Turing Machine for NLP
Venue: arXiv cs.CL 2015
Year: 2015

It is commonly accepted that machine translation is a more complex task than part of speech tagging. But how much more complex? In this paper we make an attempt to develop a general framework and methodology for computing the informational and/or processing complexity of NLP applications and tasks. We define a universal framework akin to a Turning Machine that attempts to fit (most) NLP tasks into one paradigm. We calculate the complexities of various NLP tasks using measures of Shannon Entropy, and compare `simple' ones such as part of speech tagging to `complex' ones such as machine translation. This paper provides a first, though far from perfect, attempt to quantify NLP tasks under a uniform paradigm. We point out current deficiencies and suggest some avenues for fruitful research.
On Integrating Information Visualization Techniques into Data Mining: A Review
Venue: arXiv cs.GR 2015
Year: 2015

The exploding growth of digital data in the information era and its immeasurable potential value has called for different types of data-driven techniques to exploit its value for further applications. Information visualization and data mining are two research field with such goal. While the two communities advocates different approaches of problem solving, the vision of combining the sophisticated algorithmic techniques from data mining as well as the intuitivity and interactivity of information visualization is tempting. In this paper, we attempt to survey recent researches and real world systems integrating the wisdom in two fields towards more effective and efficient data analytics. More specifically, we study the intersection from a data mining point of view, explore how information visualization can be used to complement and improve different stages of data mining through established theories for optimized visual presentation as well as practical toolsets for rapid development. We organize the survey by identifying three main stages of typical process of data mining, the preliminary analysis of data, the model construction, as well as the model evaluation, and study how each stage can benefit from information visualization.
Novel Metaknowledge-based Processing Technique for Multimedia Big Data clustering challenges
Venue: arXiv cs.DB 2015
Year: 2015

Past research has challenged us with the task of showing relational patterns between text-based data and then clustering for predictive analysis using Golay Code technique. We focus on a novel approach to extract metaknowledge in multimedia datasets. Our collaboration has been an on-going task of studying the relational patterns between datapoints based on metafeatures extracted from metaknowledge in multimedia datasets. Those selected are significant to suit the mining technique we applied, Golay Code algorithm. In this research paper we summarize findings in optimization of metaknowledge representation for 23-bit representation of structured and unstructured multimedia data in order to
Fusing Data with Correlations
Venue: arXiv cs.DB 2015
Year: 2015

Many applications rely on Web data and extraction systems to accomplish knowledge-driven tasks. Web information is not curated, so many sources provide inaccurate, or conflicting information. Moreover, extraction systems introduce additional noise to the data. We wish to automatically distinguish correct data and erroneous data for creating a cleaner set of integrated data. Previous work has shown that a naïve voting strategy that trusts data provided by the majority or at least a certain number of sources may not work well in the presence of copying between the sources. However, correlation between sources can be much broader than copying: sources may provide data from complementary domains (\emph{negative correlation}), extractors may focus on different types of information (\emph{negative correlation}), and extractors may apply common rules in extraction (\emph{positive correlation, without copying}). In this paper we present novel techniques modeling correlations between sources and applying it in truth finding.
Scaling up Copy Detection
Venue: arXiv cs.DB 2015
Year: 2015

Recent research shows that copying is prevalent for Deep-Web data and considering copying can significantly improve truth finding from conflicting values. However, existing copy detection techniques do not scale for large sizes and numbers of data sources, so truth finding can be slowed down by one to two orders of magnitude compared with the corresponding techniques that do not consider copying. In this paper, we study {\em how to improve scalability of copy detection on structured data}. Our algorithm builds an inverted index for each \emph{shared} value and processes the index entries in decreasing order of how much the shared value can contribute to the conclusion of copying. We show how we use the index to prune the data items we consider for each pair of sources, and to incrementally refine our results in iterative copy detection. We also apply a sampling strategy with which we are able to further reduce copy-detection time while still obtaining very similar results as on the whole data set. Experiments on various real data sets show that our algorithm can reduce the time for copy detection by two to three orders of magnitude; in other words, truth finding can benefit from copy detection with very little overhead.
Data Fusion: Resolving Conflicts from Multiple Sources
Venue: arXiv cs.DB 2015
Year: 2015

Many data management applications, such as setting up Web portals, managing enterprise data, managing community data, and sharing scientific data, require integrating data from multiple sources. Each of these sources provides a set of values and different sources can often provide conflicting values. To present quality data to users, it is critical to resolve conflicts and discover values that reflect the real world; this task is called {\em data fusion}. This paper describes a novel approach that finds true values from conflicting information when there are a large number of sources, among which some may copy from others. We present a case study on real-world data showing that the described algorithm can significantly improve accuracy of truth discovery and is scalable when there are a large number of data sources.
Seeded PageRank Solution Paths
Venue: arXiv cs.SI 2015
Year: 2015

We study the behavior of network diffusions based on the PageRank random walk from a set of seed nodes. These diffusions are known to reveal small, localized clusters (or communities) and also large macro-scale clusters by varying a parameter that has a dual-interpretation as an accuracy bound and as a regularization level. We propose a new method that quickly approximates the result of the diffusion for all values of this parameter. Our method efficiently generates an approximate $\textit{solution path}$ or $\textit{regularization path}$ associated with a PageRank diffusion, and it reveals cluster structures at multiple size-scales between small and large. We formally prove a runtime bound on this method that is independent of the size of the network, and we investigate multiple optimizations to our method that can be more practical in some settings. We demonstrate that these methods identify refined clustering structure on a number of real-world networks with up to 2 billion edges.
GPU Based Path Integral Control with Learned Dynamics
Venue: arXiv cs.RO 2015
Year: 2015

We present an algorithm which combines recent advances in model based path integral control with machine learning approaches to learning forward dynamics models. We take advantage of the parallel computing power of a GPU to quickly take a massive number of samples from a learned probabilistic dynamics model, which we use to approximate the path integral form of the optimal control. The resulting algorithm runs in a receding-horizon fashion in realtime, and is subject to no restrictive assumptions about costs, constraints, or dynamics. A simple change to the path integral control formulation allows the algorithm to take model uncertainty into account during planning, and we demonstrate its performance on a quadrotor navigation task. In addition to this novel adaptation of path integral control, this is the first time that a receding-horizon implementation of iterative path integral control has been run on a real system.
Variation of word frequencies in Russian literary texts
Venue: arXiv cs.CL 2015
Year: 2015

We study the variation of word frequencies in Russian literary texts. Our findings indicate that the standard deviation of a word's frequency across texts depends on its average frequency according to a power law with exponent $0.62,$ showing that the rarer words have a relatively larger degree of frequency volatility (i.e., "burstiness"). Several latent factors models have been estimated to investigate the structure of the word frequency distribution. The dependence of a word's frequency volatility on its average frequency can be explained by the asymmetry in the distribution of latent factors.
On the Null Space Constant for $l_p$ Minimization
Venue: arXiv cs.IT 2015
Year: 2015

The literature on sparse recovery often adopts the $l_p$ "norm" $(p\in[0,1])$ as the penalty to induce sparsity of the signal satisfying an underdetermined linear system. The performance of the corresponding $l_p$ minimization problem can be characterized by its null space constant. In spite of the NP-hardness of computing the constant, its properties can still help in illustrating the performance of $l_p$ minimization. In this letter, we show the strict increase of the null space constant in the sparsity level $k$ and its continuity in the exponent $p$. We also indicate that the constant is strictly increasing in $p$ with probability $1$ when the sensing matrix ${\bf A}$ is randomly generated. Finally, we show how these properties can help in demonstrating the performance of $l_p$ minimization, mainly in the relationship between the the exponent $p$ and the sparsity level $k$.
Segment-Sliding Reconstruction of Pulsed Radar Echoes with Sub-Nyquist Sampling
Venue: arXiv cs.IT 2015
Year: 2015

It has been shown that analog-to-information con- version (AIC) is an efficient scheme to perform sub-Nyquist sampling of pulsed radar echoes. However, it is often impractical, if not infeasible, to reconstruct full-range Nyquist samples because of huge storage and computational load requirements. Based on the analyses of AIC measurement system, this paper develops a novel segment-sliding reconstruction (SegSR) scheme to effectively reconstruct the Nyquist samples. The SegSR per- forms segment-by-segment reconstruction in a sliding mode and can be implemented in real-time. An important characteristic that distinguish the proposed SegSR from the existing methods is that the measurement matrix in each segment satisfies the restricted isometry property (RIP) condition. Partial support in the previous segment can be incorporated into the estimation of the Nyquist samples in the current segment. The effect of interference intro- duced from adjacent segments is theoretically analyzed, and it is revealed that the interference consists of two interference levels having different impacts to the signal reconstruction performance. With these observations, a two-step orthogonal matching pursuit (OMP) procedure is proposed for segment reconstruction, which takes into account different interference levels and partially known support of the previous segment. The proposed SegSR achieves nearly optimal reconstruction performance with a signi- ficant reduction of computational loads and storage requirements. Theoretical analyses and simulations verify its effectiveness.
Utility-Theoretic Ranking for Semi-Automated Text Classification
Venue: arXiv cs.LG 2015
Year: 2015

\emph{Semi-Automated Text Classification} (SATC) may be defined as the task of ranking a set $\mathcal{D}$ of automatically labelled textual documents in such a way that, if a human annotator validates (i.e., inspects and corrects where appropriate) the documents in a top-ranked portion of $\mathcal{D}$ with the goal of increasing the overall labelling accuracy of $\mathcal{D}$, the expected increase is maximized. An obvious SATC strategy is to rank $\mathcal{D}$ so that the documents that the classifier has labelled with the lowest confidence are top-ranked. In this work we show that this strategy is suboptimal. We develop new utility-theoretic ranking methods based on the notion of \emph{validation gain}, defined as the improvement in classification effectiveness that would derive by validating a given automatically labelled document. We also propose a new effectiveness measure for SATC-oriented ranking methods, based on the expected reduction in classification error brought about by partially validating a list generated by a given ranking method. We report the results of experiments showing that, with respect to the baseline method above, and according to the proposed measure, our utility-theoretic ranking methods can achieve substantially higher expected reductions in classification error.
Router deployment of Streetside Parking Sensor Networks in Urban Areas
Venue: arXiv cs.NI 2015
Year: 2015

The deployment of urban infrastructure is very important for urban sensor applications. In this paper, we studied and introduced the deployment strategy of wireless on-street parking sensor networks. We defined a multiple-objective problem with four objectives, and solved them with real street parking map. The results show two sets of Pareto Front with the minimum energy consumption, sensing information delay and the amount of deployed routers and gateways. The result can be considered to provide urban service roadside unit or be taken into account while designing a deployment algorithm.
CAPTCHaStar! A novel CAPTCHA based on interactive shape discovery
Venue: arXiv cs.HC 2015
Year: 2015

Over the last years, most websites on which users can register (e.g., email providers and social networks) adopted CAPTCHAs (Completely Automated Public Turing test to tell Computers and Humans Apart) as a countermeasure against automated attacks. The battle of wits between designers and attackers of CAPTCHAs led to current ones being annoying and hard to solve for users, while still being vulnerable to automated attacks. In this paper, we propose CAPTCHaStar, a new image-based CAPTCHA that relies on user interaction. This novel CAPTCHA leverages the innate human ability to recognize shapes in a confused environment. We assess the effectiveness of our proposal for the two key aspects for CAPTCHAs, i.e., usability, and resiliency to automated attacks. In particular, we evaluated the usability, carrying out a thorough user study, and we tested the resiliency of our proposal against several types of automated attacks: traditional ones; designed ad-hoc for our proposal; and based on machine learning. Compared to the state of the art, our proposal is more user friendly (e.g., only some 35% of the users prefer current solutions, such as text-based CAPTCHAs) and more resilient to automated attacks.