OpenRaiser/Intern-Atlas huggingface dataset:
Better $s$-$t$-Tours by Gao Trees
Venue: arXiv cs.DM 2015
Year: 2015

We consider the $s$-$t$-path TSP: given a finite metric space with two elements $s$ and $t$, we look for a path from $s$ to $t$ that contains all the elements and has minimum total distance. We improve the approximation ratio for this problem from 1.599 to 1.566. Like previous algorithms, we solve the natural LP relaxation and represent an optimum solution $x^*$ as a convex combination of spanning trees. Gao showed that there exists a spanning tree in the support of $x^*$ that has only one edge in each narrow cut (i.e., each cut $C$ with $x^*(C)<2$). Our main theorem says that the spanning trees in the convex combination can be chosen such that many of them are such "Gao trees''.
Return of Frustratingly Easy Domain Adaptation
Venue: arXiv cs.CV 2015
Year: 2015

Unlike human learning, machine learning often fails to handle changes between training (source) and test (target) input distributions. Such domain shifts, common in practical scenarios, severely damage the performance of conventional machine learning methods. Supervised domain adaptation methods have been proposed for the case when the target data have labels, including some that perform very well despite being "frustratingly easy" to implement. However, in practice, the target domain is often unlabeled, requiring unsupervised adaptation. We propose a simple, effective, and efficient method for unsupervised domain adaptation called CORrelation ALignment (CORAL). CORAL minimizes domain shift by aligning the second-order statistics of source and target distributions, without requiring any target labels. Even though it is extraordinarily simple--it can be implemented in four lines of Matlab code--CORAL performs remarkably well in extensive evaluations on standard benchmark datasets.
A New Smooth Approximation to the Zero One Loss with a Probabilistic Interpretation
Venue: arXiv cs.CV 2015
Year: 2015

We examine a new form of smooth approximation to the zero one loss in which learning is performed using a reformulation of the widely used logistic function. Our approach is based on using the posterior mean of a novel generalized Beta-Bernoulli formulation. This leads to a generalized logistic function that approximates the zero one loss, but retains a probabilistic formulation conferring a number of useful properties. The approach is easily generalized to kernel logistic regression and easily integrated into methods for structured prediction. We present experiments in which we learn such models using an optimization method consisting of a combination of gradient descent and coordinate descent using localized grid search so as to escape from local minima. Our experiments indicate that optimization quality is improved when learning meta-parameters are themselves optimized using a validation set. Our experiments show improved performance relative to widely used logistic and hinge loss methods on a wide variety of problems ranging from standard UC Irvine and libSVM evaluation datasets to product review predictions and a visual information extraction task. We observe that the approach: 1) is more robust to outliers compared to the logistic and hinge losses; 2) outperforms comparable logistic and max margin models on larger scale benchmark problems; 3) when combined with Gaussian- Laplacian mixture prior on parameters the kernelized version of our formulation yields sparser solutions than Support Vector Machine classifiers; and 4) when integrated into a probabilistic structured prediction technique our approach provides more accurate probabilities yielding improved inference and increasing information extraction performance.
Designing for Collaborative Sensemaking: Leveraging Human Cognition For Complex Tasks
Venue: arXiv cs.HC 2015
Year: 2015

My research aims to design systems for complex sensemaking by remotely located non-expert collaborators (crowds), to solve computationally hard problems like crimes.
Solution Repair/Recovery in Uncertain Optimization Environment
Venue: arXiv cs.AI 2015
Year: 2015

Operation management problems (such as Production Planning and Scheduling) are represented and formulated as optimization models. The resolution of such optimization models leads to solutions which have to be operated in an organization. However, the conditions under which the optimal solution is obtained rarely correspond exactly to the conditions under which the solution will be operated in the organization.Therefore, in most practical contexts, the computed optimal solution is not anymore optimal under the conditions in which it is operated. Indeed, it can be "far from optimal" or even not feasible. For different reasons, we hadn't the possibility to completely re-optimize the existing solution or plan. As a consequence, it is necessary to look for "repair solutions", i.e., solutions that have a good behavior with respect to possible scenarios, or with respect to uncertainty of the parameters of the model. To tackle the problem, the computed solution should be such that it is possible to "repair" it through a local re-optimization guided by the user or through a limited change aiming at minimizing the impact of taking into consideration the scenarios.
What Users See - Structures in Search Engine Results Pages
Venue: arXiv cs.IR 2015
Year: 2015

This paper investigates the composition of search engine results pages. We define what elements the most popular web search engines use on their results pages (e.g., organic results, advertisements, shortcuts) and to which degree they are used for popular vs. rare queries. Therefore, we send 500 queries of both types to the major search engines Google, Yahoo, Live.com and Ask. We count how often the different elements are used by the individual engines. In total, our study is based on 42,758 elements. Findings include that search engines use quite different approaches to results pages composition and therefore, the user gets to see quite different results sets depending on the search engine and search query used. Organic results still play the major role in the results pages, but different shortcuts are of some importance, too. Regarding the frequency of certain host within the results sets, we find that all search engines show Wikipedia results quite often, while other hosts shown depend on the search engine used. Both Google and Yahoo prefer results from their own offerings (such as YouTube or Yahoo Answers). Since we used the .com interfaces of the search engines, results may not be valid for other country-specific interfaces.
Google Scholar as a tool for discovering journal articles in library and information science
Venue: arXiv cs.DL 2015
Year: 2015

Purpose: The purpose of this paper is to measure the coverage of Google Scholar for the Library and Information Science (LIS) journal literature as identified by a list of core LIS journals from a study by Schloegl and Petschnig (2005). Methods: We checked every article from 35 major LIS journals from the years 2004 to 2006 for availability in Google Scholar (GS). We also collected information on the type of availability-i.e., whether a certain article was available as a PDF for a fee, as a free PDF, or as a preprint. Results: We found that only some journals are completely indexed by Google Scholar, that the ratio of versions available depends on the type of publisher, and that availability varies a lot from journal to journal. Google Scholar cannot substitute for abstracting and indexing services in that it does not cover the complete literature of the field. However, it can be used in many cases to easily find available full texts of articles already found using another tool. Originality/value: This study differs from other Google Scholar coverage studies in that it takes into account not only whether an article is indexed in GS at all, but also the type of availability.
The retrieval effectiveness of search engines on navigational queries
Venue: arXiv cs.IR 2015
Year: 2015

Purpose - To test major Web search engines on their performance on navigational queries, i.e. searches for homepages. Design/methodology/approach - 100 real user queries are posed to six search engines (Google, Yahoo, MSN, Ask, Seekport, and Exalead). Users described the desired pages, and the results position of these is recorded. Measured success N and mean reciprocal rank are calculated. Findings - Performance of the major search engines Google, Yahoo, and MSN is best, with around 90 percent of queries answered correctly. Ask and Exalead perform worse but receive good scores as well. Research limitations/implications - All queries were in German, and the German-language interfaces of the search engines were used. Therefore, the results are only valid for German queries. Practical implications - When designing a search engine to compete with the major search engines, care should be taken on the performance on navigational queries. Users can be influenced easily in their quality ratings of search engines based on this performance. Originality/value - This study systematically compares the major search engines on navigational queries and compares the findings with studies on the retrieval effectiveness of the engines on informational queries. Paper type - research paper
Scampi: a robust approximate message-passing framework for compressive imaging
Venue: arXiv cs.IT 2015
Year: 2015

Reconstruction of images from noisy linear measurements is a core problem in image processing, for which convex optimization methods based on total variation (TV) minimization have been the long-standing state-of-the-art. We present an alternative probabilistic reconstruction procedure based on approximate message-passing, Scampi, which operates in the compressive regime, where the inverse imaging problem is underdetermined. While the proposed method is related to the recently proposed GrAMPA algorithm of Borgerding, Schniter, and Rangan, we further develop the probabilistic approach to compressive imaging by introducing an expectation-maximizaiton learning of model parameters, making the Scampi robust to model uncertainties. Additionally, our numerical experiments indicate that Scampi can provide reconstruction performance superior to both GrAMPA as well as convex approaches to TV reconstruction. Finally, through exhaustive best-case experiments, we show that in many cases the maximal performance of both Scampi and convex TV can be quite close, even though the approaches are a prori distinct. The theoretical reasons for this correspondence remain an open question. Nevertheless, the proposed algorithm remains more practical, as it requires far less parameter tuning to perform optimally.
Bisimulation of Labelled State-to-Function Transition Systems Coalgebraically
Venue: arXiv cs.LO 2015
Year: 2015

Labeled state-to-function transition systems, FuTS for short, are characterized by transitions which relate states to functions of states over general semirings, equipped with a rich set of higher-order operators. As such, FuTS constitute a convenient modeling instrument to deal with process languages and their quantitative extensions in particular. In this paper, the notion of bisimulation induced by a FuTS is addressed from a coalgebraic point of view. A correspondence result is established stating that FuTS-bisimilarity coincides with behavioural equivalence of the associated functor. As generic examples, the equivalences underlying substantial fragments of major examples of quantitative process algebras are related to the bisimilarity of specific FuTS. The examples range from a stochastic process language, PEPA, to a language for Interactive Markov Chains, IML, a (discrete) timed process language, TPC, and a language for Markov Automata, MAL. The equivalences underlying these languages are related to the bisimilarity of their specific FuTS. By the correspondence result coalgebraic justification of the equivalences of these calculi is obtained. The specific selection of languages, besides covering a large variety of process interaction models and modelling choices involving quantities, allows us to show different classes of FuTS, namely so-called simple FuTS, combined FuTS, nested FuTS, and general FuTS.
Analysis and Optimization of Sparse Random Linear Network Coding for Reliable Multicast Services
Venue: arXiv cs.IT 2015
Year: 2015

Point-to-multipoint communications are expected to play a pivotal role in next-generation networks. This paper refers to a cellular system transmitting layered multicast services to a multicast group of users. Reliability of communications is ensured via different Random Linear Network Coding (RLNC) techniques. We deal with a fundamental problem: the computational complexity of the RLNC decoder. The higher the number of decoding operations is, the more the user's computational overhead grows and, consequently, the faster the battery of mobile devices drains. By referring to several sparse RLNC techniques, and without any assumption on the implementation of the RLNC decoder in use, we provide an efficient way to characterize the performance of users targeted by ultra-reliable layered multicast services. The proposed modeling allows to efficiently derive the average number of coded packet transmissions needed to recover one or more service layers. We design a convex resource allocation framework that allows to minimize the complexity of the RLNC decoder by jointly optimizing the transmission parameters and the sparsity of the code. The designed optimization framework also ensures service guarantees to predetermined fractions of users. The performance of the proposed optimization framework is then investigated in a LTE-A eMBMS network multicasting H.264/SVC video services.
Structured Depth Prediction in Challenging Monocular Video Sequences
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we tackle the problem of estimating the depth of a scene from a monocular video sequence. In particular, we handle challenging scenarios, such as non-translational camera motion and dynamic scenes, where traditional structure from motion and motion stereo methods do not apply. To this end, we first study the problem of depth estimation from a single image. In this context, we exploit the availability of a pool of images for which the depth is known, and formulate monocular depth estimation as a discrete-continuous optimization problem, where the continuous variables encode the depth of the superpixels in the input image, and the discrete ones represent relationships between neighboring superpixels. The solution to this discrete-continuous optimization problem is obtained by performing inference in a graphical model using particle belief propagation. To handle video sequences, we then extend our single image model to a two-frame one that naturally encodes short-range temporal consistency and inherently handles dynamic objects. Based on the prediction of this model, we then introduce a fully-connected pairwise CRF that accounts for longer range spatio-temporal interactions throughout a video. We demonstrate the effectiveness of our model in both the indoor and outdoor scenarios.
Master of Puppets: Analyzing And Attacking A Botnet For Fun And Profit
Venue: arXiv cs.CR 2015
Year: 2015

A botnet is a network of compromised machines (bots), under the control of an attacker. Many of these machines are infected without their owners' knowledge, and botnets are the driving force behind several misuses and criminal activities on the Internet (for example spam emails). Depending on its topology, a botnet can have zero or more command and control (C&C) servers, which are centralized machines controlled by the cybercriminal that issue commands and receive reports back from the co-opted bots. In this paper, we present a comprehensive analysis of the command and control infrastructure of one of the world's largest proprietary spamming botnets between 2007 and 2012: Cutwail/Pushdo. We identify the key functionalities needed by a spamming botnet to operate effectively. We then develop a number of attacks against the command and control logic of Cutwail that target those functionalities, and make the spamming operations of the botnet less effective. This analysis was made possible by having access to the source code of the C&C software, as well as setting up our own Cutwail C&C server, and by implementing a clone of the Cutwail bot. With the help of this tool, we were able to enumerate the number of bots currently registered with the C&C server, impersonate an existing bot to report false information to the C&C server, and manipulate spamming statistics of an arbitrary bot stored in the C&C database. Furthermore, we were able to make the control server inaccessible by conducting a distributed denial of service (DDoS) attack. Our results may be used by law enforcement and practitioners to develop better techniques to mitigate and cripple other botnets, since many of findings are generic and are due to the workflow of C&C communication in general.
RIP-like Properties in Subsampled Blind Deconvolution
Venue: arXiv cs.IT 2015
Year: 2015

We derive near optimal performance guarantees for subsampled blind deconvolution. Blind deconvolution is an ill-posed bilinear inverse problem and additional subsampling makes the problem even more challenging. Sparsity and spectral flatness priors on unknown signals are introduced to overcome these difficulties. While being crucial for deriving desired near optimal performance guarantees, unlike the sparsity prior with a nice union-of-subspaces structure, the spectral flatness prior corresponds to a nonconvex cone structure, which is not preserved by elementary set operations. This prohibits the operator arising in subsampled blind deconvolution from satisfying the standard restricted isometry property (RIP) at near optimal sample complexity, which motivated us to study other RIP-like properties. Combined with the performance guarantees derived using these RIP-like properties in a companion paper, we show that subsampled blind deconvolution is provably solved at near optimal sample complexity by a practical algorithm.
Coreset-Based Adaptive Tracking
Venue: arXiv cs.CV 2015
Year: 2015

We propose a method for learning from streaming visual data using a compact, constant size representation of all the data that was seen until a given moment. Specifically, we construct a 'coreset' representation of streaming data using a parallelized algorithm, which is an approximation of a set with relation to the squared distances between this set and all other points in its ambient space. We learn an adaptive object appearance model from the coreset tree in constant time and logarithmic space and use it for object tracking by detection. Our method obtains excellent results for object tracking on three standard datasets over more than 100 videos. The ability to summarize data efficiently makes our method ideally suited for tracking in long videos in presence of space and time constraints. We demonstrate this ability by outperforming a variety of algorithms on the TLD dataset with 2685 frames on average. This coreset based learning approach can be applied for both real-time learning of small, varied data and fast learning of big data.
What Players do with the Ball: A Physically Constrained Interaction Modeling
Venue: arXiv cs.CV 2015
Year: 2015

Tracking the ball is critical for video-based analysis of team sports. However, it is difficult, especially in low-resolution images, due to the small size of the ball, its speed that creates motion blur, and its often being occluded by players. In this paper, we propose a generic and principled approach to modeling the interaction between the ball and the players while also imposing appropriate physical constraints on the ball's trajectory. We show that our approach, formulated in terms of a Mixed Integer Program, is more robust and more accurate than several state-of-the-art approaches on real-life volleyball, basketball, and soccer sequences.
Faster method for Deep Belief Network based Object classification using DWT
Venue: arXiv cs.CV 2015
Year: 2015

A Deep Belief Network (DBN) requires large, multiple hidden layers with high number of hidden units to learn good features from the raw pixels of large images. This implies more training time as well as computational complexity. By integrating DBN with Discrete Wavelet Transform (DWT), both training time and computational complexity can be reduced. The low resolution images obtained after application of DWT are used to train multiple DBNs. The results obtained from these DBNs are combined using a weighted voting algorithm. The performance of this method is found to be competent and faster in comparison with that of traditional DBNs.
Alternative structures for character-level RNNs
Venue: arXiv cs.LG 2015
Year: 2015

Recurrent neural networks are convenient and efficient models for language modeling. However, when applied on the level of characters instead of words, they suffer from several problems. In order to successfully model long-term dependencies, the hidden representation needs to be large. This in turn implies higher computational costs, which can become prohibitive in practice. We propose two alternative structural modifications to the classical RNN model. The first one consists on conditioning the character level representation on the previous word representation. The other one uses the character history to condition the output probability. We evaluate the performance of the two proposed modifications on challenging, multi-lingual real world data.
Dynamic Adaptive Network Intelligence
Venue: arXiv cs.CL 2015
Year: 2015

Accurate representational learning of both the explicit and implicit relationships within data is critical to the ability of machines to perform more complex and abstract reasoning tasks. We describe the efficient weakly supervised learning of such inferences by our Dynamic Adaptive Network Intelligence (DANI) model. We report state-of-the-art results for DANI over question answering tasks in the bAbI dataset that have proved difficult for contemporary approaches to learning representation (Weston et al., 2015).
A Unified Gradient Regularization Family for Adversarial Examples
Venue: arXiv cs.LG 2015
Year: 2015

Adversarial examples are augmented data points generated by imperceptible perturbation of input samples. They have recently drawn much attention with the machine learning and data mining community. Being difficult to distinguish from real examples, such adversarial examples could change the prediction of many of the best learning models including the state-of-the-art deep learning models. Recent attempts have been made to build robust models that take into account adversarial examples. However, these methods can either lead to performance drops or lack mathematical motivations. In this paper, we propose a unified framework to build robust machine learning models against adversarial examples. More specifically, using the unified framework, we develop a family of gradient regularization methods that effectively penalize the gradient of loss function w.r.t. inputs. Our proposed framework is appealing in that it offers a unified view to deal with adversarial examples. It incorporates another recently-proposed perturbation based approach as a special case. In addition, we present some visual effects that reveals semantic meaning in those perturbations, and thus support our regularization method and provide another explanation for generalizability of adversarial examples. By applying this technique to Maxout networks, we conduct a series of experiments and achieve encouraging results on two benchmark datasets. In particular,we attain the best accuracy on MNIST data (without data augmentation) and competitive performance on CIFAR-10 data.