OpenRaiser/Intern-Atlas huggingface dataset:
Algorithmic Stability for Adaptive Data Analysis
Venue: arXiv cs.LG 2015
Year: 2015

Adaptivity is an important feature of data analysis---the choice of questions to ask about a dataset often depends on previous interactions with the same dataset. However, statistical validity is typically studied in a nonadaptive model, where all questions are specified before the dataset is drawn. Recent work by Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014) initiated the formal study of this problem, and gave the first upper and lower bounds on the achievable generalization error for adaptive data analysis. Specifically, suppose there is an unknown distribution $\mathbf{P}$ and a set of $n$ independent samples $\mathbf{x}$ is drawn from $\mathbf{P}$. We seek an algorithm that, given $\mathbf{x}$ as input, accurately answers a sequence of adaptively chosen queries about the unknown distribution $\mathbf{P}$. How many samples $n$ must we draw from the distribution, as a function of the type of queries, the number of queries, and the desired level of accuracy? In this work we make two new contributions: (i) We give upper bounds on the number of samples $n$ that are needed to answer statistical queries. The bounds improve and simplify the work of Dwork et al. (STOC, 2015), and have been applied in subsequent work by those authors (Science, 2015, NIPS, 2015). (ii) We prove the first upper bounds on the number of samples required to answer more general families of queries. These include arbitrary low-sensitivity queries and an important class of optimization queries. As in Dwork et al., our algorithms are based on a connection with algorithmic stability in the form of differential privacy. We extend their work by giving a quantitatively optimal, more general, and simpler proof of their main theorem that stability implies low generalization error. We also study weaker stability guarantees such as bounded KL divergence and total variation distance.
Towards automated web application logic reconstruction for application level security
Venue: arXiv cs.CR 2015
Year: 2015

Modern overlay security mechanisms like Web Application Firewalls (WAF) suffer from inability to recognize custom high-level application logic and data objects, which results in low accuracy, high false positives rates, and overhelming manual effort for fine tuning. In this paper we propose an approach to web application modeling for security purposes that could help next-generation WAFs to adapt to specific web applications, and do it automatically whenever possible. We aim at creating multi-layer models that adequately simulate various aspects of web application functionality that are significant for intrusion detection and prevention, including request parsing and routing, reconstruction of actions and data objects, and action interdependencies.
Parkinson's disease patient rehabilitation using gaming platforms: lessons learnt
Venue: arXiv cs.CY 2015
Year: 2015

Parkinson's disease (PD) is a progressive neurodegenerative movement disorder where motor dysfunction gradually increases as the disease progress. In addition to administering dopaminergic PD-specific drugs, attending neurologists strongly recommend regular exercise combined with physiotherapy. However, because of the long-term nature of the disease, patients following traditional rehabilitation programs may get bored, lose interest and eventually drop out as a direct result of the repeatability and predictability of the prescribed exercises. Technology supported opportunities to liven up a daily exercise schedule have appeared in the form of character-based, virtual reality games which promote physical training in a non-linear and looser fashion and provide an experience that varies from one game loop the next. Such "exergames", a word that results from the amalgamation of the words "exercise" and "game" challenge patients into performing movements of varying complexity in a playful and immersive virtual environment. Today's game consoles such as Nintendo's Wii, Sony PlayStation Eye and Microsoft's Kinect sensor present new opportunities to infuse motivation and variety to an otherwise mundane physiotherapy routine. In this paper we present some of these approaches, discuss their suitability for these PD patients, mainly on the basis of demands made on balance, agility and gesture precision, and present design principles that exergame platforms must comply with in order to be suitable for PD patients.
A New Relaxation Approach to Normalized Hypergraph Cut
Venue: arXiv cs.LG 2015
Year: 2015

Normalized graph cut (NGC) has become a popular research topic due to its wide applications in a large variety of areas like machine learning and very large scale integration (VLSI) circuit design. Most of traditional NGC methods are based on pairwise relationships (similarities). However, in real-world applications relationships among the vertices (objects) may be more complex than pairwise, which are typically represented as hyperedges in hypergraphs. Thus, normalized hypergraph cut (NHC) has attracted more and more attention. Existing NHC methods cannot achieve satisfactory performance in real applications. In this paper, we propose a novel relaxation approach, which is called relaxed NHC (RNHC), to solve the NHC problem. Our model is defined as an optimization problem on the Stiefel manifold. To solve this problem, we resort to the Cayley transformation to devise a feasible learning algorithm. Experimental results on a set of large hypergraph benchmarks for clustering and partitioning in VLSI domain show that RNHC can outperform the state-of-the-art methods.
Abstraction-driven Concolic Testing
Venue: arXiv cs.LO 2015
Year: 2015

Concolic testing is a promising method for generating test suites for large programs. However, it suffers from the path-explosion problem and often fails to find tests that cover difficult-to-reach parts of programs. In contrast, model checkers based on counterexample-guided abstraction refinement explore programs exhaustively, while failing to scale on large programs with precision. In this paper, we present a novel method that iteratively combines concolic testing and model checking to find a test suite for a given coverage criterion. If concolic testing fails to cover some test goals, then the model checker refines its program abstraction to prove more paths infeasible, which reduces the search space for concolic testing. We have implemented our method on top of the concolic-testing tool CREST and the model checker CpaChecker. We evaluated our tool on a collection of programs and a category of SvComp benchmarks. In our experiments, we observed an improvement in branch coverage compared to CREST from 48% to 63% in the best case, and from 66% to 71% on average.
Two Flow-Based Approaches for the Static Relocation Problem in Carsharing Systems
Venue: arXiv cs.DS 2015
Year: 2015

In a carsharing system, a fleet of cars is distributed at stations in an urban area, customers can take and return cars at any time and station. For operating such a system in a satisfactory way, the stations have to keep a good ratio between the numbers of free places and cars in each station. This leads to the problem of relocating cars between stations, which can be modeled within the framework of a metric task system. In this paper, we focus on the Static Relocation Problem, where the system has to be set into a certain state, outgoing from the current state. We present two approaches to solve this problem, a fast heuristic approach and an exact integer programming based method using flows in time-expanded networks, and provide some computational results.
Genomics and Biological Big Data: Facing Current and Future Challenges around Data and Software Sharing and Reproducibility
Venue: arXiv cs.DC 2015
Year: 2015

Novel technologies in genomics allow creating data in exascale dimension with relatively minor effort of human and laboratory and thus monetary resources compared to capabilities only a decade ago. While the availability of this data salvage to find answers for research questions, which would not have been feasible before, maybe even not feasible to ask before, the amount of data creates new challenges, which obviously need new software and data management systems. Such new solutions have to consider integrative approaches, which are not only considering the effectiveness and efficiency of data processing but improve reusability, reproducibility and usability especially tailored to the target user communities of genomic big data. In our opinion, current solutions tackle part of the challenges and have each their strengths but lack to provide a complete solution. We present in this paper the key challenges and the characteristics cutting-edge developments should possess for fulfilling the needs of the user communities to allow for seamless sharing and data analysis on a large scale.
Parameterized complexity of length-bounded cuts and multi-cuts
Venue: arXiv cs.DS 2015
Year: 2015

We show that the Minimal Length-Bounded L-But problem can be computed in linear time with respect to L and the tree-width of the input graph as parameters. In this problem the task is to find a set of edges of a graph such that after removal of this set, the shortest path between two prescribed vertices is at least L long. We derive an FPT algorithm for a more general multi-commodity length bounded cut problem when parameterized by the number of terminals also. For the former problem we show a W[1]-hardness result when the parameterization is done by the path-width only (instead of the tree-width) and that this problem does not admit polynomial kernel when parameterized by tree-width and L. We also derive an FPT algorithm for the Minimal Length-Bounded Cut problem when parameterized by the tree-depth. Thus showing an interesting paradigm for this problem and parameters tree-depth and path-width.
Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions
Venue: arXiv cs.GT 2015
Year: 2015

We study the communication complexity of combinatorial auctions via interpolation mechanisms that interpolate between non-truthful and truthful protocols. Specifically, an interpolation mechanism has two phases. In the first phase, the bidders participate in some non-truthful protocol whose output is itself a truthful protocol. In the second phase, the bidders participate in the truthful protocol selected during phase one. Note that virtually all existing auctions have either a non-existent first phase (and are therefore truthful mechanisms), or a non-existent second phase (and are therefore just traditional protocols, analyzed via the Price of Anarchy/Stability). The goal of this paper is to understand the benefits of interpolation mechanisms versus truthful mechanisms or traditional protocols, and develop the necessary tools to formally study them. Interestingly, we exhibit settings where interpolation mechanisms greatly outperform the optimal traditional and truthful protocols. Yet, we also exhibit settings where interpolation mechanisms are provably no better than truthful ones. Finally, we apply our new machinery to prove that the recent single-bid mechanism of Devanur et. al.~\cite{DevanurMSW15} (the only pre-existing interpolation mechanism in the literature) achieves the optimal price of anarchy among a wide class of protocols, a claim that simply can't be addressed by appealing just to machinery from communication complexity or the study of truthful mechanisms.
Spatially Coherent Random Forests
Venue: arXiv cs.CV 2015
Year: 2015

Spatially Coherent Random Forest (SCRF) extends Random Forest to create spatially coherent labeling. Each split function in SCRF is evaluated based on a traditional information gain measure that is regularized by a spatial coherency term. This way, SCRF is encouraged to choose split functions that cluster pixels both in appearance space and in image space. In particular, we use SCRF to detect contours in images, where contours are taken to be the boundaries between different regions. Each tree in the forest produces a segmentation of the image plane and the boundaries of the segmentations of all trees are aggregated to produce a final hierarchical contour map. We show that this modification improves the performance of regular Random Forest by about 10% on the standard Berkeley Segmentation Datasets. We believe that SCRF can be used in other settings as well.
Interprocedural Type Specialization of JavaScript Programs Without Type Analysis
Venue: arXiv cs.PL 2015
Year: 2015

Dynamically typed programming languages such as Python and JavaScript defer type checking to run time. VM implementations can improve performance by eliminating redundant dynamic type checks. However, type inference analyses are often costly and involve tradeoffs between compilation time and resulting precision. This has lead to the creation of increasingly complex multi-tiered VM architectures. Lazy basic block versioning is a simple JIT compilation technique which effectively removes redundant type checks from critical code paths. This novel approach lazily generates type-specialized versions of basic blocks on-the-fly while propagating context-dependent type information. This approach does not require the use of costly program analyses, is not restricted by the precision limitations of traditional type analyses. This paper extends lazy basic block versioning to propagate type information interprocedurally, across function call boundaries. Our implementation in a JavaScript JIT compiler shows that across 26 benchmarks, interprocedural basic block versioning eliminates more type tag tests on average than what is achievable with static type analysis without resorting to code transformations. On average, 94.3% of type tag tests are eliminated, yielding speedups of up to 56%. We also show that our implementation is able to outperform Truffle/JS on several benchmarks, both in terms of execution time and compilation time.
Undecidable Cases of Model Checking Probabilistic Temporal-Epistemic Logic
Venue: arXiv cs.LO 2015
Year: 2015

We investigate the decidability of model-checking logics of time, knowledge and probability, with respect to two epistemic semantics: the clock and synchronous perfect recall semantics in partially observed discrete-time Markov chains. Decidability results are known for certain restricted logics with respect to these semantics, subject to a variety of restrictions that are either unexplained or involve a longstanding unsolved mathematical problem. We show that mild generalizations of the known decidable cases suffice to render the model checking problem definitively undecidable. In particular, for a synchronous perfect recall, a generalization from temporal operators with finite reach to operators with infinite reach renders model checking undecidable. The case of the clock semantics is closely related to a monadic second order logic of time and probability that is known to be decidable, except on a set of measure zero. We show that two distinct extensions of this logic make model checking undecidable. One of these involves polynomial combinations of probability terms, the other involves monadic second order quantification into the scope of probability operators. These results explain some of the restrictions in previous work.
Deep Representation of Facial Geometric and Photometric Attributes for Automatic 3D Facial Expression Recognition
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we present a novel approach to automatic 3D Facial Expression Recognition (FER) based on deep representation of facial 3D geometric and 2D photometric attributes. A 3D face is firstly represented by its geometric and photometric attributes, including the geometry map, normal maps, normalized curvature map and texture map. These maps are then fed into a pre-trained deep convolutional neural network to generate the deep representation. Then the facial expression prediction is simplyachieved by training linear SVMs over the deep representation for different maps and fusing these SVM scores. The visualizations show that the deep representation provides a complete and highly discriminative coding scheme for 3D faces. Comprehensive experiments on the BU-3DFE database demonstrate that the proposed deep representation can outperform the widely used hand-crafted descriptors (i.e., LBP, SIFT, HOG, Gabor) and the state-of-art approaches under the same experimental protocols.
Sliced Wasserstein Kernels for Probability Distributions
Venue: arXiv cs.LG 2015
Year: 2015

Optimal transport distances, otherwise known as Wasserstein distances, have recently drawn ample attention in computer vision and machine learning as a powerful discrepancy measure for probability distributions. The recent developments on alternative formulations of the optimal transport have allowed for faster solutions to the problem and has revamped its practical applications in machine learning. In this paper, we exploit the widely used kernel methods and provide a family of provably positive definite kernels based on the Sliced Wasserstein distance and demonstrate the benefits of these kernels in a variety of learning tasks. Our work provides a new perspective on the application of optimal transport flavored distances through kernel methods in machine learning tasks.
The Radon cumulative distribution transform and its application to image classification
Venue: arXiv cs.CV 2015
Year: 2015

Invertible image representation methods (transforms) are routinely employed as low-level image processing operations based on which feature extraction and recognition algorithms are developed. Most transforms in current use (e.g. Fourier, Wavelet, etc.) are linear transforms, and, by themselves, are unable to substantially simplify the representation of image classes for classification. Here we describe a nonlinear, invertible, low-level image processing transform based on combining the well known Radon transform for image data, and the 1D Cumulative Distribution Transform proposed earlier. We describe a few of the properties of this new transform, and with both theoretical and experimental results show that it can often render certain problems linearly separable in transform space.
Hybrid Analog-Digital Beamforming for Multiuser MIMO Millimeter Wave Relay Systems
Venue: arXiv cs.IT 2015
Year: 2015

This paper proposed new hybrid, analog-digital, beamforming for a multiuser millimeter wave (mm-wave) relay system. For this system, we consider a sum rate maximization problem. The proposed hybrid beamforming is designed indirectly by considering a sum mean square error (MSE) minimization problem while utilizing the solution of digital beamforming. To this end, we assume that the digital beamforming utilizes the well known block diagonalization (BD) approach. Under this assumption, we solve our problem as follows: First, we formulate the sum rate maximization problem as the minimization of the MSE between the received signal of the hybrid and digital beamforming designs. Then, we design the hybrid beamformings of the source, relay and each destination by leveraging compressive sensing techniques. Simulation results confirm that the proposed hybrid beamforming design achieves performance very close to that of the digital one. Furthermore, we have examined the effects of the number of radio frequency (RF) chains and paths together, and the accuracy of angle of arrival (AoA) and angle of departure (AoD) estimators on the sum rate of the hybrid beamforming designs. Computer simulations reveal that the total sum rate of the hybrid beamforming increases when the number of RF chains and paths increase (or the accuracy of the AoA (AoD) estimator improves).
Discovery Radiomics via StochasticNet Sequencers for Cancer Detection
Venue: arXiv cs.CV 2015
Year: 2015

Radiomics has proven to be a powerful prognostic tool for cancer detection, and has previously been applied in lung, breast, prostate, and head-and-neck cancer studies with great success. However, these radiomics-driven methods rely on pre-defined, hand-crafted radiomic feature sets that can limit their ability to characterize unique cancer traits. In this study, we introduce a novel discovery radiomics framework where we directly discover custom radiomic features from the wealth of available medical imaging data. In particular, we leverage novel StochasticNet radiomic sequencers for extracting custom radiomic features tailored for characterizing unique cancer tissue phenotype. Using StochasticNet radiomic sequencers discovered using a wealth of lung CT data, we perform binary classification on 42,340 lung lesions obtained from the CT scans of 93 patients in the LIDC-IDRI dataset. Preliminary results show significant improvement over previous state-of-the-art methods, indicating the potential of the proposed discovery radiomics framework for improving cancer screening and diagnosis.
Facial Expression Detection using Patch-based Eigen-face Isomap Networks
Venue: arXiv cs.CV 2015
Year: 2015

Automated facial expression detection problem pose two primary challenges that include variations in expression and facial occlusions (glasses, beard, mustache or face covers). In this paper we introduce a novel automated patch creation technique that masks a particular region of interest in the face, followed by Eigen-value decomposition of the patched faces and generation of Isomaps to detect underlying clustering patterns among faces. The proposed masked Eigen-face based Isomap clustering technique achieves 75% sensitivity and 66-73% accuracy in classification of faces with occlusions and smiling faces in around 1 second per image. Also, betweenness centrality, Eigen centrality and maximum information flow can be used as network-based measures to identify the most significant training faces for expression classification tasks. The proposed method can be used in combination with feature-based expression classification methods in large data sets for improving expression classification accuracies.
GEMMbench: a framework for reproducible and collaborative benchmarking of matrix multiplication
Venue: arXiv cs.MS 2015
Year: 2015

The generic matrix-matrix multiplication (GEMM) is arguably the most popular computational kernel of the 20th century. Yet, surprisingly, no common methodology for evaluating GEMM performance has been established over the many decades of using GEMM for comparing architectures, compilers and ninja-class programmers. We introduce GEMMbench, a framework and methodology for evaluating performance of GEMM implementations. GEMMbench is implemented on top of Collective Knowledge (CK), a lightweight framework for reproducible and collaborative R&D in computer systems. Using CK allows the R&D community to crowdsource hand-written and compiler-generated GEMM implementations and to study their performance across multiple platforms, data sizes and data types. Our initial implementation supports hand-written OpenCL kernels operating on matrices consisting of single- and double-precision floating-point values, and producing single or multiple output elements per work-item (via thread coarsening and vectorization).
Complexity of the Description Logic ALCM
Venue: arXiv cs.LO 2015
Year: 2015

In this paper we show that the problem of checking consistency of a knowledge base in the Description Logic ALCM is ExpTime-complete. The M stands for meta-modelling as defined by Motz, Rohrer and Severi. To show our main result, we define an ExpTime Tableau algorithm as an extension of an algorithm for checking consistency of a knowledge base in ALC by Nguyen and Szalas.