OpenRaiser/Intern-Atlas huggingface dataset:
Differentially Private Algorithms for Empirical Machine Learning
Venue: arXiv cs.LG 2014
Year: 2014

An important use of private data is to build machine learning classifiers. While there is a burgeoning literature on differentially private classification algorithms, we find that they are not practical in real applications due to two reasons. First, existing differentially private classifiers provide poor accuracy on real world datasets. Second, there is no known differentially private algorithm for empirically evaluating the private classifier on a private test dataset. In this paper, we develop differentially private algorithms that mirror real world empirical machine learning workflows. We consider the private classifier training algorithm as a blackbox. We present private algorithms for selecting features that are input to the classifier. Though adding a preprocessing step takes away some of the privacy budget from the actual classification process (thus potentially making it noisier and less accurate), we show that our novel preprocessing techniques significantly increase classifier accuracy on three real-world datasets. We also present the first private algorithms for empirically constructing receiver operating characteristic (ROC) curves on a private test set.
Generalized $β$-skeletons
Venue: arXiv cs.CG 2014
Year: 2014

$β$-skeletons, a prominent member of the neighborhood graph family, have interesting geometric properties and various applications ranging from geographic networks to archeology. This paper focuses on developing a new, more general than the present one, definition of $β$-skeletons based only on the distance criterion. It allows us to consider them in many different cases, e.g. for weighted graphs or objects other than points. Two types of $β$-skeletons are especially well-known: the Gabriel Graph (for $β= 1$) and the Relative Neighborhood Graph (for $β= 2$). The new definition retains relations between those graphs and the other well-known ones (minimum spanning tree and Delaunay triangulation). We also show several new algorithms finding $β$-skeletons.
Multidimensional $β$-skeletons in $L_1$ and $L_{\infty}$ metric
Venue: arXiv cs.CG 2014
Year: 2014

The $β$-skeleton $\{G_β(V)\}$ for a point set V is a family of geometric graphs, defined by the notion of neighborhoods parameterized by real number $0 < β< \infty$. By using the distance-based version definition of $β$-skeletons we study those graphs for a set of points in $\mathbb{R}^d$ space with $l_1$ and $l_{\infty}$ metrics. We present algorithms for the entire spectrum of $β$ values and we discuss properties of lens-based and circle-based $β$-skeletons in those metrics. Let $V \in \mathbb{R}^d$ in $L_{\infty}$ metric be a set of $n$ points in general position. Then, for $β<2$ lens-based $β$-skeleton $G_β(V)$ can be computed in $O(n^2 \log^d n)$ time. For $β\geq 2$ there exists an $O(n \log^{d-1} n)$ time algorithm that constructs $β$-skeleton for the set $V$. We show that in $\mathbb{R}^d$ with $L_{\infty}$ metric, for $β<2$ $β$-skeleton $G_β(V)$ for $n$ points can be computed in $O(n^2 \log^d n)$ time. For $β\geq 2$ there exists an $O(n \log^{d-1} n)$ time algorithm. In $\mathbb{R}^d$ with $L_1$ metric for a set of $n$ points in arbitrary position $β$-skeleton $G_β(V)$ can be computed in $O(n^2 \log^{d+2} n)$ time.
Maximum Likelihood Directed Enumeration Method in Piecewise-Regular Object Recognition
Venue: arXiv cs.CV 2014
Year: 2014

We explore the problems of classification of composite object (images, speech signals) with low number of models per class. We study the question of improving recognition performance for medium-sized database (thousands of classes). The key issue of fast approximate nearest-neighbor methods widely applied in this task is their heuristic nature. It is possible to strongly prove their efficiency by using the theory of algorithms only for simple similarity measures and artificially generated tasks. On the contrary, in this paper we propose an alternative, statistically optimal greedy algorithm. At each step of this algorithm joint density (likelihood) of distances to previously checked models is estimated for each class. The next model to check is selected from the class with the maximal likelihood. The latter is estimated based on the asymptotic properties of the Kullback-Leibler information discrimination and mathematical model of piecewise-regular object with distribution of each regular segment of exponential type. Experimental results in face recognition for FERET dataset prove that the proposed method is much more effective than not only brute force and the baseline (directed enumeration method) but also approximate nearest neighbor methods from FLANN and NonMetricSpaceLib libraries (randomized kd-tree, composite index, perm-sort).
Visual Sentiment Prediction with Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2014
Year: 2014

Images have become one of the most popular types of media through which users convey their emotions within online social networks. Although vast amount of research is devoted to sentiment analysis of textual data, there has been very limited work that focuses on analyzing sentiment of image data. In this work, we propose a novel visual sentiment prediction framework that performs image understanding with Deep Convolutional Neural Networks (CNN). Specifically, the proposed sentiment prediction framework performs transfer learning from a CNN with millions of parameters, which is pre-trained on large-scale data for object recognition. Experiments conducted on two real-world datasets from Twitter and Tumblr demonstrate the effectiveness of the proposed visual sentiment analysis framework.
A Joint Probabilistic Classification Model of Relevant and Irrelevant Sentences in Mathematical Word Problems
Venue: arXiv cs.CL 2014
Year: 2014

Estimating the difficulty level of math word problems is an important task for many educational applications. Identification of relevant and irrelevant sentences in math word problems is an important step for calculating the difficulty levels of such problems. This paper addresses a novel application of text categorization to identify two types of sentences in mathematical word problems, namely relevant and irrelevant sentences. A novel joint probabilistic classification model is proposed to estimate the joint probability of classification decisions for all sentences of a math word problem by utilizing the correlation among all sentences along with the correlation between the question sentence and other sentences, and sentence text. The proposed model is compared with i) a SVM classifier which makes independent classification decisions for individual sentences by only using the sentence text and ii) a novel SVM classifier that considers the correlation between the question sentence and other sentences along with the sentence text. An extensive set of experiments demonstrates the effectiveness of the joint probabilistic classification model for identifying relevant and irrelevant sentences as well as the novel SVM classifier that utilizes the correlation between the question sentence and other sentences. Furthermore, empirical results and analysis show that i) it is highly beneficial not to remove stopwords and ii) utilizing part of speech tagging does not make a significant improvement although it has been shown to be effective for the related task of math word problem type classification.
Towards Scene Understanding with Detailed 3D Object Representations
Venue: arXiv cs.CV 2014
Year: 2014

Current approaches to semantic image and scene understanding typically employ rather simple object representations such as 2D or 3D bounding boxes. While such coarse models are robust and allow for reliable object detection, they discard much of the information about objects' 3D shape and pose, and thus do not lend themselves well to higher-level reasoning. Here, we propose to base scene understanding on a high-resolution object representation. An object class - in our case cars - is modeled as a deformable 3D wireframe, which enables fine-grained modeling at the level of individual vertices and faces. We augment that model to explicitly include vertex-level occlusion, and embed all instances in a common coordinate frame, in order to infer and exploit object-object interactions. Specifically, from a single view we jointly estimate the shapes and poses of multiple objects in a common 3D frame. A ground plane in that frame is estimated by consensus among different objects, which significantly stabilizes monocular 3D pose estimation. The fine-grained model, in conjunction with the explicit 3D scene model, further allows one to infer part-level occlusions between the modeled objects, as well as occlusions by other, unmodeled scene elements. To demonstrate the benefits of such detailed object class models in the context of scene understanding we systematically evaluate our approach on the challenging KITTI street scene dataset. The experiments show that the model's ability to utilize image evidence at the level of individual parts improves monocular 3D pose estimation w.r.t. both location and (continuous) viewpoint.
Clustering evolving data using kernel-based methods
Venue: arXiv cs.SI 2014
Year: 2014

In this thesis, we propose several modelling strategies to tackle evolving data in different contexts. In the framework of static clustering, we start by introducing a soft kernel spectral clustering (SKSC) algorithm, which can better deal with overlapping clusters with respect to kernel spectral clustering (KSC) and provides more interpretable outcomes. Afterwards, a whole strategy based upon KSC for community detection of static networks is proposed, where the extraction of a high quality training sub-graph, the choice of the kernel function, the model selection and the applicability to large-scale data are key aspects. This paves the way for the development of a novel clustering algorithm for the analysis of evolving networks called kernel spectral clustering with memory effect (MKSC), where the temporal smoothness between clustering results in successive time steps is incorporated at the level of the primal optimization problem, by properly modifying the KSC formulation. Later on, an application of KSC to fault detection of an industrial machine is presented. Here, a smart pre-processing of the data by means of a proper windowing operation is necessary to catch the ongoing degradation process affecting the machine. In this way, in a genuinely unsupervised manner, it is possible to raise an early warning when necessary, in an online fashion. Finally, we propose a new algorithm called incremental kernel spectral clustering (IKSC) for online learning of non-stationary data. This ambitious challenge is faced by taking advantage of the out-of-sample property of kernel spectral clustering (KSC) to adapt the initial model, in order to tackle merging, splitting or drifting of clusters across time. Real-world applications considered in this thesis include image segmentation, time-series clustering, community detection of static and evolving networks.
Virtual View Networks for Object Reconstruction
Venue: arXiv cs.CV 2014
Year: 2014

All that structure from motion algorithms "see" are sets of 2D points. We show that these impoverished views of the world can be faked for the purpose of reconstructing objects in challenging settings, such as from a single image, or from a few ones far apart, by recognizing the object and getting help from a collection of images of other objects from the same class. We synthesize virtual views by computing geodesics on novel networks connecting objects with similar viewpoints, and introduce techniques to increase the specificity and robustness of factorization-based object reconstruction in this setting. We report accurate object shape reconstruction from a single image on challenging PASCAL VOC data, which suggests that the current domain of applications of rigid structure-from-motion techniques may be significantly extended.
Morphing Planar Graph Drawings with Unidirectional Moves
Venue: arXiv cs.CG 2014
Year: 2014

Alamdari et al. showed that given two straight-line planar drawings of a graph, there is a morph between them that preserves planarity and consists of a polynomial number of steps where each step is a \emph{linear morph} that moves each vertex at constant speed along a straight line. An important step in their proof consists of converting a \emph{pseudo-morph} (in which contractions are allowed) to a true morph. Here we introduce the notion of \emph{unidirectional morphing} step, where the vertices move along lines that all have the same direction. Our main result is to show that any planarity preserving pseudo-morph consisting of unidirectional steps and contraction of low degree vertices can be turned into a true morph without increasing the number of steps. Using this, we strengthen Alamdari et al.'s result to use only unidirectional morphs, and in the process we simplify the proof.
Morphing Schnyder drawings of planar triangulations
Venue: arXiv cs.CG 2014
Year: 2014

We consider the problem of morphing between two planar drawings of the same triangulated graph, maintaining straight-line planarity. A paper in SODA 2013 gave a morph that consists of $O(n^2)$ steps where each step is a linear morph that moves each of the $n$ vertices in a straight line at uniform speed. However, their method imitates edge contractions so the grid size of the intermediate drawings is not bounded and the morphs are not good for visualization purposes. Using Schnyder embeddings, we are able to morph in $O(n^2)$ linear morphing steps and improve the grid size to $O(n)\times O(n)$ for a significant class of drawings of triangulations, namely the class of weighted Schnyder drawings. The morphs are visually attractive. Our method involves implementing the basic "flip" operations of Schnyder woods as linear morphs.
Cross-Layer Software-Defined 5G Network
Venue: arXiv cs.NI 2014
Year: 2014

In the past few decades, the world has witnessed a rapid growth in mobile communication and reaped great benefits from it. Even though the fourth generation (4G) mobile communication system is just being deployed worldwide, proliferating mobile demands call for newer wireless communication technologies with even better performance. Consequently, the fifth generation (5G) system is already emerging in the research field. However, simply evolving the current mobile networks can hardly meet such great expectations, because over the years the infrastructures have generally become ossified, closed, and vertically constructed. Aiming to establish a new paradigm for 5G mobile networks, in this article, we propose a cross-layer software-defined 5G network architecture. By jointly considering both the network layer and the physical layer together, we establish the two software-defined programmable components, the control plane and the cloud computing pool, which enable an effective control of the mobile network from the global perspective and benefit technological innovations. Specifically, by the cross-layer design for software-defining, the logically centralized and programmable control plane abstracts the control functions from the network layer down to the physical layer, through which we achieve the fine-grained controlling of mobile network, while the cloud computing pool provides powerful computing capability to implement the baseband data processing of multiple heterogeneous networks. We discuss the main challenges of our architecture, including the fine-grained control strategies, network virtualization, and programmability. The architecture significantly benefits the convergence towards heterogeneous networks and it enables much more controllable, programmable and evolvable mobile networks.
An Empirical Analysis of Task Allocation in Scrum-based Agile Programming
Venue: arXiv cs.SE 2014
Year: 2014

Agile Software Development (ASD) methodology has become widely used in the industry. Understanding the challenges facing software engineering students is important to designing effective training methods to equip students with proper skills required for effectively using the ASD techniques. Existing empirical research mostly focused on eXtreme Programming (XP) based ASD methodologies. There is a lack of empirical studies about Scrum-based ASD programming which has become the most popular agile methodology among industry practitioners. In this paper, we present empirical findings regarding the aspects of task allocation decision-making, collaboration, and team morale related to the Scrum ASD process which have not yet been well studied by existing research. We draw our findings from a 12 week long course work project in 2014 involving 125 undergraduate software engineering students from a renowned university working in 21 Scrum teams. Instead of the traditional survey or interview based methods, which suffer from limitations in scale and level of details, we obtain fine grained data through logging students' activities in our online agile project management (APM) platform - HASE. During this study, the platform logged over 10,000 ASD activities. Deviating from existing preconceptions, our results suggest negative correlations between collaboration and team performance as well as team morale.
Approximating Matrices with Multiple Symmetries
Venue: arXiv cs.NA 2014
Year: 2014

If a tensor with various symmetries is properly unfolded, then the resulting matrix inherits those symmetries. As tensor computations become increasingly important it is imperative that we develop efficient structure preserving methods for matrices with multiple symmetries. In this paper we consider how to exploit and preserve structure in the pivoted Cholesky factorization when approximating a matrix $A$ that is both symmetric ($A=A^T$) and what we call {\em perfect shuffle symmetric}, or {\em perf-symmetric}. The latter property means that $A = ΠAΠ$ where $Π$ is a permutation with the property that $Πv = v$ if $v$ is the vec of a symmetric matrix and $Πv = -v$ if $v$ is the vec of a skew-symmetric matrix. Matrices with this structure can arise when an order-4 tensor $\cal A$ is unfolded and its elements satisfy ${\cal A}(i_{1},i_{2},i_{3},i_{4}) = {\cal A}(i_{2},i_{1},i_{3},i_{4}) ={\cal A}(i_{1},i_{2},i_{4},i_{3}) ={\cal A}(i_{3},i_{4},i_{1},i_{2}).$ This is the case in certain quantum chemistry applications where the tensor entries are electronic repulsion integrals. Our technique involves a closed-form block diagonalization followed by one or two half-sized pivoted Cholesky factorizations. This framework allows for a lazy evaluation feature that is important if the entries in $\cal A$ are expensive to compute. In addition to being a structure preserving rank reduction technique, we find that this approach for obtaining the Cholesky factorization reduces the work by up to a factor of 4.
Explicit MDS Codes for Optimal Repair Bandwidth
Venue: arXiv cs.IT 2014
Year: 2014

MDS codes are erasure-correcting codes that can correct the maximum number of erasures for a given number of redundancy or parity symbols. If an MDS code has $r$ parities and no more than $r$ erasures occur, then by transmitting all the remaining data in the code, the original information can be recovered. However, it was shown that in order to recover a single symbol erasure, only a fraction of $1/r$ of the information needs to be transmitted. This fraction is called the repair bandwidth (fraction). Explicit code constructions were given in previous works. If we view each symbol in the code as a vector or a column over some field, then the code forms a 2D array and such codes are especially widely used in storage systems. In this paper, we address the following question: given the length of the column $l$, number of parities $r$, can we construct high-rate MDS array codes with optimal repair bandwidth of $1/r$, whose code length is as long as possible? In this paper, we give code constructions such that the code length is $(r+1)\log_r l$.
Automatic Summarization of Soccer Highlights Using Audio-visual Descriptors
Venue: arXiv cs.IR 2014
Year: 2014

Automatic summarization generation of sports video content has been object of great interest for many years. Although semantic descriptions techniques have been proposed, many of the approaches still rely on low-level video descriptors that render quite limited results due to the complexity of the problem and to the low capability of the descriptors to represent semantic content. In this paper, a new approach for automatic highlights summarization generation of soccer videos using audio-visual descriptors is presented. The approach is based on the segmentation of the video sequence into shots that will be further analyzed to determine its relevance and interest. Of special interest in the approach is the use of the audio information that provides additional robustness to the overall performance of the summarization system. For every video shot a set of low and mid level audio-visual descriptors are computed and lately adequately combined in order to obtain different relevance measures based on empirical knowledge rules. The final summary is generated by selecting those shots with highest interest according to the specifications of the user and the results of relevance measures. A variety of results are presented with real soccer video sequences that prove the validity of the approach.
The Optimal Arbitrary-Proportional Finite-Set-Partitioning
Venue: arXiv cs.NA 2014
Year: 2014

This paper considers the arbitrary-proportional finite-set-partitioning problem which involves partitioning a finite set into multiple subsets with respect to arbitrary nonnegative proportions. This is the core art of many fundamental problems such as determining quotas for different individuals of different weights or sampling from a discrete-valued weighted sample set to get a new identically distributed but non-weighted sample set (e.g. the resampling needed in the particle filter). The challenge raises as the size of each subset must be an integer while its unbiased expectation is often not. To solve this problem, a metric (cost function) is defined on their discrepancies and correspondingly a solution is proposed to determine the sizes of each subsets, gaining the minimal bias. Theoretical proof and simulation demonstrations are provided to demonstrate the optimality of the scheme in the sense of the proposed metric.
Evaluating the Crowd with Confidence
Venue: arXiv cs.DB 2014
Year: 2014

Worker quality control is a crucial aspect of crowdsourcing systems; typically occupying a large fraction of the time and money invested on crowdsourcing. In this work, we devise techniques to generate confidence intervals for worker error rate estimates, thereby enabling a better evaluation of worker quality. We show that our techniques generate correct confidence intervals on a range of real-world datasets, and demonstrate wide applicability by using them to evict poorly performing workers, and provide confidence intervals on the accuracy of the answers.