OpenRaiser/Intern-Atlas huggingface dataset:
HDIdx: High-Dimensional Indexing for Efficient Approximate Nearest Neighbor Search
Venue: arXiv cs.IR 2015
Year: 2015

Fast Nearest Neighbor (NN) search is a fundamental challenge in large-scale data processing and analytics, particularly for analyzing multimedia contents which are often of high dimensionality. Instead of using exact NN search, extensive research efforts have been focusing on approximate NN search algorithms. In this work, we present "HDIdx", an efficient high-dimensional indexing library for fast approximate NN search, which is open-source and written in Python. It offers a family of state-of-the-art algorithms that convert input high-dimensional vectors into compact binary codes, making them very efficient and scalable for NN search with very low space complexity.
Diverse Large-Scale ITS Dataset Created from Continuous Learning for Real-Time Vehicle Detection
Venue: arXiv cs.CV 2015
Year: 2015

In traffic engineering, vehicle detectors are trained on limited datasets resulting in poor accuracy when deployed in real world applications. Annotating large-scale high quality datasets is challenging. Typically, these datasets have limited diversity; they do not reflect the real-world operating environment. There is a need for a large-scale, cloud based positive and negative mining (PNM) process and a large-scale learning and evaluation system for the application of traffic event detection. The proposed positive and negative mining process addresses the quality of crowd sourced ground truth data through machine learning review and human feedback mechanisms. The proposed learning and evaluation system uses a distributed cloud computing framework to handle data-scaling issues associated with large numbers of samples and a high-dimensional feature space. The system is trained using AdaBoost on $1,000,000$ Haar-like features extracted from $70,000$ annotated video frames. The trained real-time vehicle detector achieves an accuracy of at least $95\%$ for $1/2$ and about $78\%$ for $19/20$ of the time when tested on approximately $7,500,000$ video frames. At the end of 2015, the dataset is expect to have over one billion annotated video frames.
Augmenting Bag-of-Words: Data-Driven Discovery of Temporal and Structural Information for Activity Recognition
Venue: arXiv cs.CV 2015
Year: 2015

We present data-driven techniques to augment Bag of Words (BoW) models, which allow for more robust modeling and recognition of complex long-term activities, especially when the structure and topology of the activities are not known a priori. Our approach specifically addresses the limitations of standard BoW approaches, which fail to represent the underlying temporal and causal information that is inherent in activity streams. In addition, we also propose the use of randomly sampled regular expressions to discover and encode patterns in activities. We demonstrate the effectiveness of our approach in experimental evaluations where we successfully recognize activities and detect anomalies in four complex datasets.
Algorithm and Related Application for Smart Wearable Devices to Reduce the Risk of Death and Brain Damage in Diabetic Coma
Venue: arXiv cs.HC 2015
Year: 2015

Diabetes is an epidemic disease of the 21st century and is growing globally. Although, final diabetes treatments and cure are still on research phase, related complications of diabetes endanger life of diabetic patients. Diabetic coma which happens with extreme high or low blood glucose is one of the risk factor for diabetic patients and if it remains unattended will lead to patient death or permanent brain damage. To reduce the risk of such deaths or damages, a novel algorithm for wearable devices application, especially for smart watches are proposed. Such application can inform the patients relatives or emergency centers, if the person falls in coma or irresponsive condition based on readouts from smart watches sensors including mobility, heart rate and skin moisture. However; such an application is not a final solution to detect all types of coma, but it potentially could save lives of many patients, if widely used among the diabetic patients around the world.
Small-Area Orthogonal Drawings of 3-Connected Graphs
Venue: arXiv cs.CG 2015
Year: 2015

It is well-known that every graph with maximum degree 4 has an orthogonal drawing with area at most $\frac{49}{64} n^2+O(n) \approx 0.76n^2$. In this paper, we show that if the graph is 3-connected, then the area can be reduced even further to $\frac{9}{16}n^2+O(n) \approx 0.56n^2$. The drawing uses the 3-canonical order for (not necessarily planar) 3-connected graphs, which is a special Mondshein sequence and can hence be computed in linear time. To our knowledge, this is the first application of a Mondshein sequence in graph drawing.
Value Automata with Filters
Venue: arXiv cs.FL 2015
Year: 2015

We propose to study value automata with filters, a natural generalization of regular cost automata to nondeterminism. Models such as weighted automata and Parikh automata appear naturally as specializations. Results on the expressiveness of this model offer a general understanding of the behavior of the models that arise as special cases. A landscape of such restrictions is drawn.
Technical Report of Participation in Higgs Boson Machine Learning Challenge
Venue: arXiv cs.LG 2015
Year: 2015

This report entails the detailed description of the approach and methodologies taken as part of competing in the Higgs Boson Machine Learning Competition hosted by Kaggle Inc. and organized by CERN et al. It briefly describes the theoretical background of the problem and the motivation for taking part in the competition. Furthermore, the various machine learning models and algorithms analyzed and implemented during the 4 month period of participation are discussed and compared. Special attention is paid to the Deep Learning techniques and architectures implemented from scratch using Python and NumPy for this competition.
Hamiltonian Properties of DCell Networks
Venue: arXiv cs.DC 2015
Year: 2015

DCell has been proposed for data centers as a server centric interconnection network structure. DCell can support millions of servers with high network capacity by only using commodity switches. With one exception, we prove that a $k$ level DCell built with $n$ port switches is Hamiltonian-connected for $k \geq 0$ and $n \geq 2$. Our proof extends to all generalized DCell connection rules for $n\ge 3$. Then, we propose an $O(t_k)$ algorithm for finding a Hamiltonian path in $DCell_{k}$, where $t_k$ is the number of servers in $DCell_{k}$. What's more, we prove that $DCell_{k}$ is $(n+k-4)$-fault Hamiltonian-connected and $(n+k-3)$-fault Hamiltonian. In addition, we show that a partial DCell is Hamiltonian connected if it conforms to a few practical restrictions.
Protein preliminaries and structure prediction fundamentals for computer scientists
Venue: arXiv cs.CE 2015
Year: 2015

Protein structure prediction is a challenging and unsolved problem in computer science. Proteins are the sequence of amino acids connected together by single peptide bond. The combinations of the twenty primary amino acids are the constituents of all proteins. In-vitro laboratory methods used in this problem are very time-consuming, cost-intensive, and failure-prone. Thus, alternative computational methods come into play. The protein structure prediction problem is to find the three-dimensional native structure of a protein, from its amino acid sequence. The native structure of a protein has the minimum free energy possible and arguably determines the function of the protein. In this study, we present the preliminaries of proteins and their structures, protein structure prediction problem, and protein models. We also give a brief overview on experimental and computational methods used in protein structure prediction. This study will provide a fundamental knowledge to the computer scientists who are intending to pursue their future research on protein structure prediction problem.
A novel code generation methodology for block diagram modeler and simulators Scicos and VSS
Venue: arXiv cs.MS 2015
Year: 2015

Block operations during simulation in Scicos and VSS environments can naturally be described as Nsp functions. But the direct use of Nsp functions for simulation leads to poor performance since the Nsp language is interpreted, not compiled. The methodology presented in this paper is used to develop a tool for generating efficient compilable code, such as C and ADA, for Scicos and VSS models from these block Nsp functions. Operator overloading and partial evaluation are the key elements of this novel approach. This methodology may be used in other simulation environments such as Matlab/Simulink.
NTCCRT: A concurrent constraint framework for real-time interaction (extended version)
Venue: arXiv cs.LO 2015
Year: 2015

Writing multimedia interaction systems is not easy. Their concurrent processes usually access shared resources in a non-deterministic order, often leading to unpredictable behavior. Using Pure Data (Pd) and Max/MSP is possible to program concurrency, however, it is difficult to synchronize processes based on multiple criteria. Process calculi such as the Non-deterministic Timed Concurrent Constraint (ntcc) calculus, overcome that problem by representing multiple criteria as constraints. We propose using our framework Ntccrt to manage concurrency in Pd and Max. Ntccrt is a real-time capable inter- preter for ntcc. Using Ntccrt externals (binary plugins) in Pd we ran models for machine improvisation and signal processing.
Survey on Feature Selection
Venue: arXiv cs.LG 2015
Year: 2015

Feature selection plays an important role in the data mining process. It is needed to deal with the excessive number of features, which can become a computational burden on the learning algorithms. It is also necessary, even when computational resources are not scarce, since it improves the accuracy of the machine learning tasks, as we will see in the upcoming sections. In this review, we discuss the different feature selection approaches, and the relation between them and the various machine learning algorithms.
Printed Perforated Lampshades for Continuous Projective Images
Venue: arXiv cs.GR 2015
Year: 2015

We present a technique for designing 3D-printed perforated lampshades, which project continuous grayscale images onto the surrounding walls. Given the geometry of the lampshade and a target grayscale image, our method computes a distribution of tiny holes over the shell, such that the combined footprints of the light emanating through the holes form the target image on a nearby diffuse surface. Our objective is to approximate the continuous tones and the spatial detail of the target image, to the extent possible within the constraints of the fabrication process. To ensure structural integrity, there are lower bounds on the thickness of the shell, the radii of the holes, and the minimal distances between adjacent holes. Thus, the holes are realized as thin tubes distributed over the lampshade surface. The amount of light passing through a single tube may be controlled by the tube's radius and by its direction (tilt angle). The core of our technique thus consists of determining a suitable configuration of the tubes: their distribution across the relevant portion of the lampshade, as well as the parameters (radius, tilt angle) of each tube. This is achieved by computing a capacity-constrained Voronoi tessellation over a suitably defined density function, and embedding a tube inside the maximal inscribed circle of each tessellation cell. The density function for a particular target image is derived from a series of simulated images, each corresponding to a different uniform density tube pattern on the lampshade.
On Correcting Inputs: Inverse Optimization for Online Structured Prediction
Venue: arXiv cs.LG 2015
Year: 2015

Algorithm designers typically assume that the input data is correct, and then proceed to find "optimal" or "sub-optimal" solutions using this input data. However this assumption of correct data does not always hold in practice, especially in the context of online learning systems where the objective is to learn appropriate feature weights given some training samples. Such scenarios necessitate the study of inverse optimization problems where one is given an input instance as well as a desired output and the task is to adjust the input data so that the given output is indeed optimal. Motivated by learning structured prediction models, in this paper we consider inverse optimization with a margin, i.e., we require the given output to be better than all other feasible outputs by a desired margin. We consider such inverse optimization problems for maximum weight matroid basis, matroid intersection, perfect matchings, minimum cost maximum flows, and shortest paths and derive the first known results for such problems with a non-zero margin. The effectiveness of these algorithmic approaches to online learning for structured prediction is also discussed.
IoT enabled Insurance Ecosystem - Possibilities Challenges and Risks
Venue: arXiv cs.CY 2015
Year: 2015

Internet of Thing (IoT) is looking over to overhaul the business processes of many industries including insurance domain. The current line of business such as Property and Casualty, Health, and Life Insurance can avail tremendous benefits from the contextual and relevant data being generated from billions of connected devices; Smartphone's, wearable gadget and other electronic smart sensors. For P&C insurer's the biggest challenges is not the rapidly changing environment but tackling these challenges with strategies linked to the past. This paper presents the key opportunities, challenges, potential applications and risks of IoT in Insurance domain. It crystallomancy on the efficient use of data analytics from data generated in IoT ecosystem and highlights business model changes that Insurance industries may face in near future.
Task Assignment on Multi-Skill Oriented Spatial Crowdsourcing
Venue: arXiv cs.DB 2015
Year: 2015

With the rapid development of mobile devices and crowdsourcing platforms, the spatial crowdsourcing has attracted much attention from the database community. Specifically, the spatial crowdsourcing refers to sending location-based requests to workers, based on their current positions. In this paper, we consider a spatial crowdsourcing scenario, in which each worker has a set of qualified skills, whereas each spatial task (e.g., repairing a house, decorating a room, and performing entertainment shows for a ceremony) is time-constrained, under the budget constraint, and required a set of skills. Under this scenario, we will study an important problem, namely multi-skill spatial crowdsourcing (MS-SC), which finds an optimal worker-and-task assignment strategy, such that skills between workers and tasks match with each other, and workers' benefits are maximized under the budget constraint. We prove that the MS-SC problem is NP-hard and intractable. Therefore, we propose three effective heuristic approaches, including greedy, g-divide-and-conquer and cost-model-based adaptive algorithms to get worker-and-task assignments. Through extensive experiments, we demonstrate the efficiency and effectiveness of our MS-SC processing approaches on both real and synthetic data sets.
The Inductive Constraint Programming Loop
Venue: arXiv cs.AI 2015
Year: 2015

Constraint programming is used for a variety of real-world optimisation problems, such as planning, scheduling and resource allocation problems. At the same time, one continuously gathers vast amounts of data about these problems. Current constraint programming software does not exploit such data to update schedules, resources and plans. We propose a new framework, that we call the Inductive Constraint Programming loop. In this approach data is gathered and analyzed systematically, in order to dynamically revise and adapt constraints and optimization criteria. Inductive Constraint Programming aims at bridging the gap between the areas of data mining and machine learning on the one hand, and constraint programming on the other hand.
Privacy Constrained Information Processing
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies communication scenarios where the transmitter and the receiver have different objectives due to privacy concerns, in the context of a variation of the strategic information transfer (SIT) model of Sobel and Crawford. We first formulate the problem as the minimization of a common distortion by the transmitter and the receiver subject to a privacy constrained transmitter. We show the equivalence of this formulation to a Stackelberg equilibrium of the SIT problem. Assuming an entropy based privacy measure, a quadratic distortion measure and jointly Gaussian variables, we characterize the Stackelberg equilibrium. Next, we consider asymptotically optimal compression at the transmitter which inherently provides some level of privacy, and study equilibrium conditions. We finally analyze the impact of the presence of an average power constrained Gaussian communication channel between the transmitter and the receiver on the equilibrium conditions.
$\ell_1$-regularized Neural Networks are Improperly Learnable in Polynomial Time
Venue: arXiv cs.LG 2015
Year: 2015

We study the improper learning of multi-layer neural networks. Suppose that the neural network to be learned has $k$ hidden layers and that the $\ell_1$-norm of the incoming weights of any neuron is bounded by $L$. We present a kernel-based method, such that with probability at least $1 - δ$, it learns a predictor whose generalization error is at most $ε$ worse than that of the neural network. The sample complexity and the time complexity of the presented method are polynomial in the input dimension and in $(1/ε,\log(1/δ),F(k,L))$, where $F(k,L)$ is a function depending on $(k,L)$ and on the activation function, independent of the number of neurons. The algorithm applies to both sigmoid-like activation functions and ReLU-like activation functions. It implies that any sufficiently sparse neural network is learnable in polynomial time.
Universal Packet Scheduling
Venue: arXiv cs.NI 2015
Year: 2015

In this paper we address a seemingly simple question: Is there a universal packet scheduling algorithm? More precisely, we analyze (both theoretically and empirically) whether there is a single packet scheduling algorithm that, at a network-wide level, can match the results of any given scheduling algorithm. We find that in general the answer is "no". However, we show theoretically that the classical Least Slack Time First (LSTF) scheduling algorithm comes closest to being universal and demonstrate empirically that LSTF can closely, though not perfectly, replay a wide range of scheduling algorithms in realistic network settings. We then evaluate whether LSTF can be used {\em in practice} to meet various network-wide objectives by looking at three popular performance metrics (mean FCT, tail packet delays, and fairness); we find that LSTF performs comparable to the state-of-the-art for each of them.
Linear-Vertex Kernel for the Problem of Packing $r$-Stars into a Graph without Long Induced Paths
Venue: arXiv cs.DS 2015
Year: 2015

Let integers $r\ge 2$ and $d\ge 3$ be fixed. Let ${\cal G}_d$ be the set of graphs with no induced path on $d$ vertices. We study the problem of packing $k$ vertex-disjoint copies of $K_{1,r}$ ($k\ge 2$) into a graph $G$ from parameterized preprocessing, i.e., kernelization, point of view. We show that every graph $G\in {\cal G}_d$ can be reduced, in polynomial time, to a graph $G'\in {\cal G}_d$ with $O(k)$ vertices such that $G$ has at least $k$ vertex-disjoint copies of $K_{1,r}$ if and only if $G'$ has. Such a result is known for arbitrary graphs $G$ when $r=2$ and we conjecture that it holds for every $r\ge 2$.
A language model based approach towards large scale and lightweight language identification systems
Venue: arXiv cs.SD 2015
Year: 2015

Multilingual spoken dialogue systems have gained prominence in the recent past necessitating the requirement for a front-end Language Identification (LID) system. Most of the existing LID systems rely on modeling the language discriminative information from low-level acoustic features. Due to the variabilities of speech (speaker and emotional variabilities, etc.), large-scale LID systems developed using low-level acoustic features suffer from a degradation in the performance. In this approach, we have attempted to model the higher level language discriminative phonotactic information for developing an LID system. In this paper, the input speech signal is tokenized to phone sequences by using a language independent phone recognizer. The language discriminative phonotactic information in the obtained phone sequences are modeled using statistical and recurrent neural network based language modeling approaches. As this approach, relies on higher level phonotactical information it is more robust to variabilities of speech. Proposed approach is computationally light weight, highly scalable and it can be used in complement with the existing LID systems.
Decoding Network Codes using the Sum-Product Algorithm
Venue: arXiv cs.IT 2015
Year: 2015

While feasibility and obtaining a solution of a given network coding problem are well studied, the decoding procedure and complexity have not garnered much attention. We consider the decoding problem in a network wherein the sources generate multiple messages and the sink nodes demand some or all of the source messages. We consider both linear and non-linear network codes over a finite field and propose to use the sum-product (SP) algorithm over Boolean semiring for decoding at the sink nodes in order to reduce the computational complexity. We use traceback to further lower the computational complexity incurred by SP decoding. We also define and identify a sufficient condition for fast decodability of a network code at a sink that demands all the source messages.
Trust as indicator of robot functional and social acceptance. An experimental study on user conformation to the iCub's answers
Venue: arXiv cs.RO 2015
Year: 2015

To investigate the functional and social acceptance of a humanoid robot, we carried out an experimental study with 56 adult participants and the iCub robot. Trust in the robot has been considered as a main indicator of acceptance in decision-making tasks characterized by perceptual uncertainty (e.g., evaluating the weight of two objects) and socio-cognitive uncertainty (e.g., evaluating which is the most suitable item in a specific context), and measured by the participants' conformation to the iCub's answers to specific questions. In particular, we were interested in understanding whether specific (i) user-related features (i.e. desire for control), (ii) robot-related features (i.e., attitude towards social influence of robots), and (iii) context-related features (i.e., collaborative vs. competitive scenario), may influence their trust towards the iCub robot. We found that participants conformed more to the iCub's answers when their decisions were about functional issues than when they were about social issues. Moreover, the few participants conforming to the iCub's answers for social issues also conformed less for functional issues. Trust in the robot's functional savvy does not thus seem to be a pre-requisite for trust in its social savvy. Finally, desire for control, attitude towards social influence of robots and type of interaction scenario did not influence the trust in iCub. Results are discussed with relation to methodology of HRI research.
Frame Coalescing in Dual-Mode EEE
Venue: arXiv cs.NI 2015
Year: 2015

The IEEE has recently released the 802.3bj standard that defines two different low power operating modes for high speed Energy Efficient Ethernet physical interfaces (PHYs) working at 40 and 100 Gb/s. In this paper, we propose the use of the well-known frame coalescing algorithm to manage them and provide an analytical model to evaluate the influence of coalescing parameters and PHY characteristics on their power consumption.