OpenRaiser/Intern-Atlas huggingface dataset:
Heuristic for Maximizing Grouping Efficiency in the Cell Formation Problem
Venue: arXiv cs.DM 2017
Year: 2017

In our paper we consider the Cell Formation Problem in Group Technology with grouping efficiency as an objective function. We present a heuristic approach for obtaining high-quality solutions of the CFP. The suggested heuristic applies an improvement procedure to obtain solutions with high grouping efficiency. This procedure is repeated many times for randomly generated cell configurations. Our computational experiments are performed for popular benchmark instances taken from the literature with sizes from 10x20 to 50x150. Better solutions unknown before are found for 23 instances of the 24 considered.
Two-Moment Inequalities for Rényi Entropy and Mutual Information
Venue: arXiv cs.IT 2017
Year: 2017

This paper explores some applications of a two-moment inequality for the integral of the $r$-th power of a function, where $0 < r< 1$. The first contribution is an upper bound on the Rényi entropy of a random vector in terms of the two different moments. When one of the moments is the zeroth moment, these bounds recover previous results based on maximum entropy distributions under a single moment constraint. More generally, evaluation of the bound with two carefully chosen nonzero moments can lead to significant improvements with a modest increase in complexity. The second contribution is a method for upper bounding mutual information in terms of certain integrals with respect to the variance of the conditional density. The bounds have a number of useful properties arising from the connection with variance decompositions.
Self-synchronization and Self-stabilization of 3D Bipedal Walking Gaits
Venue: arXiv cs.RO 2017
Year: 2017

This paper seeks insight into stabilization mechanisms for periodic walking gaits in 3D bipedal robots. Based on this insight, a control strategy based on virtual constraints, which imposes coordination between joints rather than a temporal evolution, will be proposed for achieving asymptotic convergence toward a periodic motion. For planar bipeds with one degree of underactuation, it is known that a vertical displacement of the center of mass---with downward velocity at the step transition---induces stability of a walking gait. This paper concerns the qualitative extension of this type of property to 3D walking with two degrees of underactuation. It is shown that a condition on the position of the center of mass in the horizontal plane at the transition between steps induces synchronization between the motions in the sagittal and frontal planes. A combination of the conditions for self-synchronization and vertical oscillations leads to stable gaits. The algorithm for self-stabilization of 3D walking gaits is first developed for a simplified model of a walking robot (an inverted pendulum with variable length legs), and then it is extended to a complex model of the humanoid robot Romeo using the notion of Hybrid Zero Dynamics. Simulations of the model of the robot illustrate the efficacy of the method and its robustness.
Simulation of detecting contact nonlinearity in carbon fibre polymer using ultrasonic nonlinear delayed time reversal
Venue: arXiv cs.CE 2017
Year: 2017

A finite element method simulation of a carbon fibre reinforced polymer block is used to analyse the nonlinearities arising from a contacting delamination gap inside the material. The ultrasonic signal is amplified and nonlinearities are analysed by delayed Time Reversal -- Nonlinear Elastic Wave Spectroscopy signal processing method. This signal processing method allows to focus the wave energy onto the receiving transducer and to modify the focused wave shape, allowing to use several different methods, including pulse inversion, for detecting the nonlinear signature of the damage. It is found that the small crack with contacting acoustic nonlinearity produces a noticeable nonlinear signature when using pulse inversion signal processing, and even higher signature with delayed time reversal, without requiring any baseline information from an undamaged medium.
Building Usage Profiles Using Deep Neural Nets
Venue: arXiv cs.SE 2017
Year: 2017

To improve software quality, one needs to build test scenarios resembling the usage of a software product in the field. This task is rendered challenging when a product's customer base is large and diverse. In this scenario, existing profiling approaches, such as operational profiling, are difficult to apply. In this work, we consider publicly available video tutorials of a product to profile usage. Our goal is to construct an automatic approach to extract information about user actions from instructional videos. To achieve this goal, we use a Deep Convolutional Neural Network (DCNN) to recognize user actions. Our pilot study shows that a DCNN trained to recognize user actions in video can classify five different actions in a collection of 236 publicly available Microsoft Word tutorial videos (published on YouTube). In our empirical evaluation we report a mean average precision of 94.42% across all actions. This study demonstrates the efficacy of DCNN-based methods for extracting software usage information from videos. Moreover, this approach may aid in other software engineering activities that require information about customer usage of a product.
How Gamification Affects Physical Activity: Large-scale Analysis of Walking Challenges in a Mobile Application
Venue: arXiv cs.CY 2017
Year: 2017

Gamification represents an effective way to incentivize user behavior across a number of computing applications. However, despite the fact that physical activity is essential for a healthy lifestyle, surprisingly little is known about how gamification and in particular competitions shape human physical activity. Here we study how competitions affect physical activity. We focus on walking challenges in a mobile activity tracking application where multiple users compete over who takes the most steps over a predefined number of days. We synthesize our findings in a series of game and app design implications. In particular, we analyze nearly 2,500 physical activity competitions over a period of one year capturing more than 800,000 person days of activity tracking. We observe that during walking competitions, the average user increases physical activity by 23%. Furthermore, there are large increases in activity for both men and women across all ages, and weight status, and even for users that were previously fairly inactive. We also find that the composition of participants greatly affects the dynamics of the game. In particular, if highly unequal participants get matched to each other, then competition suffers and the overall effect on the physical activity drops significantly. Furthermore, competitions with an equal mix of both men and women are more effective in increasing the level of activities. We leverage these insights to develop a statistical model to predict whether or not a competition will be particularly engaging with significant accuracy. Our models can serve as a guideline to help design more engaging competitions that lead to most beneficial behavioral changes.
Efficient Hidden Vector Encryptions and Its Applications
Venue: arXiv cs.CR 2017
Year: 2017

Predicate encryption is a new paradigm of public key encryption that enables searches on encrypted data. Using the predicate encryption, we can search keywords or attributes on encrypted data without decrypting the ciphertexts. In predicate encryption, a ciphertext is associated with attributes and a token corresponds to a predicate. The token that corresponds to a predicate $f$ can decrypt the ciphertext associated with attributes $x$ if and only if $f(x)=1$. Hidden vector encryption (HVE) is a special kind of predicate encryption. In this thesis, we consider the efficiency, the generality, and the security of HVE schemes. The results of this thesis are described as follows. The first results of this thesis are efficient HVE schemes where the token consists of just four group elements and the decryption only requires four bilinear map computations, independent of the number of attributes in the ciphertext. The construction uses composite order bilinear groups and is selectively secure under the well-known assumptions. The second results are efficient HVE schemes that are secure under any kind of pairing types. To achieve our goals, we proposed a general framework that converts HVE schemes from composite order bilinear groups to prime order bilinear groups. Using the framework, we convert the previous HVE schemes from composite order bilinear groups to prime order bilinear groups. The third results are fully secure HVE schemes with short tokens. Previous HVE schemes were proven to be secure only in the selective security model where the capabilities of the adversaries are severely restricted. Using the dual system encryption techniques, we construct fully secure HVE schemes with match revealing property in composite order groups.
Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning
Venue: arXiv cs.CR 2017
Year: 2017

Deep Learning has recently become hugely popular in machine learning, providing significant improvements in classification accuracy in the presence of highly-structured and large databases. Researchers have also considered privacy implications of deep learning. Models are typically trained in a centralized manner with all the data being processed by the same training algorithm. If the data is a collection of users' private data, including habits, personal pictures, geographical positions, interests, and more, the centralized server will have access to sensitive information that could potentially be mishandled. To tackle this problem, collaborative deep learning models have recently been proposed where parties locally train their deep learning structures and only share a subset of the parameters in the attempt to keep their respective training sets private. Parameters can also be obfuscated via differential privacy (DP) to make information extraction even more challenging, as proposed by Shokri and Shmatikov at CCS'15. Unfortunately, we show that any privacy-preserving collaborative deep learning is susceptible to a powerful attack that we devise in this paper. In particular, we show that a distributed, federated, or decentralized deep learning approach is fundamentally broken and does not protect the training sets of honest participants. The attack we developed exploits the real-time nature of the learning process that allows the adversary to train a Generative Adversarial Network (GAN) that generates prototypical samples of the targeted training set that was meant to be private (the samples generated by the GAN are intended to come from the same distribution as the training data). Interestingly, we show that record-level DP applied to the shared parameters of the model, as suggested in previous work, is ineffective (i.e., record-level DP is not designed to address our attack).
Generalization of Schnyder woods to orientable surfaces and applications
Venue: arXiv cs.DM 2017
Year: 2017

Schnyder woods are particularly elegant combinatorial structures with numerous applications concerning planar triangulations and more generally 3-connected planar maps. We propose a simple generalization of Schnyder woods from the plane to maps on orientable surfaces of any genus with a special emphasis on the toroidal case. We provide a natural partition of the set of Schnyder woods of a given map into distributive lattices depending on the surface homology. In the toroidal case we show the existence of particular Schnyder woods with some global properties that are useful for optimal encoding or graph drawing purpose.
Understanding Performance of Edge Content Caching for Mobile Video Streaming
Venue: arXiv cs.MM 2017
Year: 2017

Today's Internet has witnessed an increase in the popularity of mobile video streaming, which is expected to exceed 3/4 of the global mobile data traffic by 2019. To satisfy the considerable amount of mobile video requests, video service providers have been pushing their content delivery infrastructure to edge networks--from regional CDN servers to peer CDN servers (e.g., smartrouters in users' homes)--to cache content and serve users with storage and network resources nearby. Among the edge network content caching paradigms, Wi-Fi access point caching and cellular base station caching have become two mainstream solutions. Thus, understanding the effectiveness and performance of these solutions for large-scale mobile video delivery is important. However, the characteristics and request patterns of mobile video streaming are unclear in practical wireless network. In this paper, we use real-world datasets containing 50 million trace items of nearly 2 million users viewing more than 0.3 million unique videos using mobile devices in a metropolis in China over 2 weeks, not only to understand the request patterns and user behaviors in mobile video streaming, but also to evaluate the effectiveness of Wi-Fi and cellular-based edge content caching solutions. To understand performance of edge content caching for mobile video streaming, we first present temporal and spatial video request patterns, and we analyze their impacts on caching performance using frequency-domain and entropy analysis approaches. We then study the behaviors of mobile video users, including their mobility and geographical migration behaviors. Using trace-driven experiments, we compare strategies for edge content caching including LRU and LFU, in terms of supporting mobile video requests. Moreover, we design an efficient caching strategy based on the measurement insights and experimentally evaluate its performance.
Social Data Analysis: A Study on Friend Rating Influence
Venue: arXiv cs.SI 2017
Year: 2017

Social Networking accounts for a significant chunk of interest among various online activities~\cite{smith2009social}. The proclivity of being social, online, has been ingrained in us so much that we are actively producing content for the rest of the world to see or take interest in our whereabouts, our meals, our opinions, photographs etc. Yelp (https://www.yelp.com/), seamlessly, integrates this very aspect of people in its portal. It engages people to write reviews about the businesses they have availed the services of, rate them, add photographs, tags, follow other people and their activities, etc. In this paper we examine and present the co-relation between a user's rating and the influence of the people, that the user follows, on the user for a particular business. The group of people that the user follows is commonly referred as friends of the user. We also analyze if a user can get influenced, if a business has a certain number of reviews already present or if the reviews have been written by elite reviewers (a reviewer who, according to Yelp, has contributed exceptionally in engaging the community in the form of consistency in writing reviews, as well as the quality of the reviews). Our analysis, through correlation and regression techniques, is able to prove that the user's rating remains unaffected by the number of people a user was friends with nor does the existing number of reviews and presence of elite reviewers helps in influencing a user. What shapes a user's rating is the overall experience, that the user had at the restaurant.
Insense: Incoherent Sensor Selection for Sparse Signals
Venue: arXiv cs.OH 2017
Year: 2017

Sensor selection refers to the problem of intelligently selecting a small subset of a collection of available sensors to reduce the sensing cost while preserving signal acquisition performance. The majority of sensor selection algorithms find the subset of sensors that best recovers an arbitrary signal from a number of linear measurements that is larger than the dimension of the signal. In this paper, we develop a new sensor selection algorithm for sparse (or near sparse) signals that finds a subset of sensors that best recovers such signals from a number of measurements that is much smaller than the dimension of the signal. Existing sensor selection algorithms cannot be applied in such situations. Our proposed Incoherent Sensor Selection (Insense) algorithm minimizes a coherence-based cost function that is adapted from recent results in sparse recovery theory. Using six datasets, including two real-world datasets on microbial diagnostics and structural health monitoring, we demonstrate the superior performance of Insense for sparse-signal sensor selection.
Consistent Alignment of Word Embedding Models
Venue: arXiv cs.CL 2017
Year: 2017

Word embedding models offer continuous vector representations that can capture rich contextual semantics based on their word co-occurrence patterns. While these word vectors can provide very effective features used in many NLP tasks such as clustering similar words and inferring learning relationships, many challenges and open research questions remain. In this paper, we propose a solution that aligns variations of the same model (or different models) in a joint low-dimensional latent space leveraging carefully generated synthetic data points. This generative process is inspired by the observation that a variety of linguistic relationships is captured by simple linear operations in embedded space. We demonstrate that our approach can lead to substantial improvements in recovering embeddings of local neighborhoods.
What Aspects of Mobile Ads Do Users Care About? An Empirical Study of Mobile In-app Ad Reviews
Venue: arXiv cs.CY 2017
Year: 2017

In the mobile app ecosystem, developers receive ad revenue by placing ads in their apps and releasing them for free. While there is evidence that users do not like ads, we do not know what are the aspects of ads that users dislike nor if they dislike certain aspects of ads more than others. Therefore, in this paper, we analyzed the different topics of ad related complaints from users. In order to do this, we investigated app reviews that users gave for apps in the app store that were about ads. We manually examined a random sample set of 400 ad reviews to identify ad complaint topics. We found that most ad complaints were about user interface (UI) related topics and three topics were brought up the most often: the frequency with which ads were displayed, the timing of when ads were displayed, and the location of the displayed ads. Our results provide actionable information to software developers regarding the aspects of ads that are most likely to be complained about by users in their reviews.
Bounds on the reliability of typewriter channels
Venue: arXiv cs.IT 2017
Year: 2017

New lower and upper bounds on the reliability function of typewriter channels are given. Our lower bounds improve upon the (multiletter) expurgated bound of Gallager, furnishing a new and simple counterexample to a conjecture made in 1967 by Shannon, Gallager and Berlekamp on its tightness. The only other known counterexample is due to Katsman, Tsfasman and Vlăduţ who used algebraic-geometric codes on a $q$-ary symmetric channels, $q\geq 49$. Here we prove, by introducing dependence between codewords of a random ensemble, that the conjecture is false even for a typewriter channel with $q=4$ inputs. In the process, we also demonstrate that Lovász's proof of the capacity of the pentagon was implicitly contained (but unnoticed!) in the works of Jelinek and Gallager on the expurgated bound done at least ten years before Lovász. In the opposite direction, new upper bounds on the reliability function are derived for channels with an odd number of inputs by using an adaptation of Delsarte's linear programming bound. First we derive a bound based on the minimum distance, which combines Lovász's construction for bounding the graph capacity with the McEliece-Rodemich-Rumsey-Welch construction for bounding the minimum distance of codes in the Hamming space. Then, for the particular case of cross-over probability $1/2$, we derive an improved bound by also using the method of Kalai and Linial to study the spectrum distribution of codes.
A Methodology for Oracle Selection of Monitors and Knobs for Configuring an HPC System running a Flood Management Application
Venue: arXiv cs.DC 2017
Year: 2017

This paper defines a methodology for the oracle selection of the monitors and knobs to use to configure an HPC system running a scientific application while satisfying the application's requirements and not violating any system constraints. This methodology relies on a heuristic correlation analysis between requirements, monitors and knobs to determine the minimum subset of monitors to observe and knobs to explore, to determine the optimal system configuration for the HPC application. At the end of this analysis, we reduce an 11-dimensional space to a 3-dimensional space for monitors and a 6-dimensional space to a 3-dimensional space for knobs. This reduction shows the potential and highlights the need for a realistic methodology to help identify such minimum set of monitors and knobs.
A supervised approach to time scale detection in dynamic networks
Venue: arXiv cs.SI 2017
Year: 2017

For any stream of time-stamped edges that form a dynamic network, an important choice is the aggregation granularity that an analyst uses to bin the data. Picking such a windowing of the data is often done by hand, or left up to the technology that is collecting the data. However, the choice can make a big difference in the properties of the dynamic network. This is the time scale detection problem. In previous work, this problem is often solved with a heuristic as an unsupervised task. As an unsupervised problem, it is difficult to measure how well a given algorithm performs. In addition, we show that the quality of the windowing is dependent on which task an analyst wants to perform on the network after windowing. Therefore the time scale detection problem should not be handled independently from the rest of the analysis of the network. We introduce a framework that tackles both of these issues: By measuring the performance of the time scale detection algorithm based on how well a given task is accomplished on the resulting network, we are for the first time able to directly compare different time scale detection algorithms to each other. Using this framework, we introduce time scale detection algorithms that take a supervised approach: they leverage ground truth on training data to find a good windowing of the test data. We compare the supervised approach to previous approaches and several baselines on real data.
An EM Based Probabilistic Two-Dimensional CCA with Application to Face Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Recently, two-dimensional canonical correlation analysis (2DCCA) has been successfully applied for image feature extraction. The method instead of concatenating the columns of the images to the one-dimensional vectors, directly works with two-dimensional image matrices. Although 2DCCA works well in different recognition tasks, it lacks a probabilistic interpretation. In this paper, we present a probabilistic framework for 2DCCA called probabilistic 2DCCA (P2DCCA) and an iterative EM based algorithm for optimizing the parameters. Experimental results on synthetic and real data demonstrate superior performance in loading factor estimation for P2DCCA compared to 2DCCA. For real data, three subsets of AR face database and also the UMIST face database confirm the robustness of the proposed algorithm in face recognition tasks with different illumination conditions, facial expressions, poses and occlusions.