OpenRaiser/Intern-Atlas huggingface dataset:
The Primal-Dual Greedy Algorithm for Weighted Covering Problems
Venue: arXiv cs.DM 2017
Year: 2017

We present a general approximation framework for weighted integer covering problems. In a weighted integer covering problem, the goal is to determine a non-negative integer solution $x$ to system $\{ Ax \geq r \}$ minimizing a non-negative cost function $c^T x$ (of appropriate dimensions). All coefficients in matrix $A$ are assumed to be non-negative. We analyze the performance of a very simple primal-dual greedy algorithm and discuss conditions of system $(A,r)$ that guarantee feasibility of the constructed solutions, and a bounded approximation factor. We call system $(A,r)$ a \emph{greedy system} if it satisfies certain properties introduced in this work. These properties highly rely on monotonicity and supermodularity conditions on $A$ and $r$, and can thus be seen as a far reaching generalization of contra-polymatroids. Given a greedy system $(A,r)$, we carefully construct a truncated system $(A',r)$ containing the same integer feasible points. We show that our primal-dual greedy algorithm when applied to the truncated system $(A',r)$ obtains a feasible solution to $(A,r)$ with approximation factor at most $2δ+ 1$, or $2δ$ if $r$ is non-negative. Here, $δ$ is some characteristic of the truncated matrix $A'$ which is small in many applications. The analysis is shown to be tight up to constant factors. We also provide an approximation factor of $k (δ+ 1)$ if the greedy algorithm is applied to the intersection of multiple greedy systems. The parameter $k$ is always bounded by the number of greedy systems but may be much smaller. Again, we show that the dependency on $k$ is tight. We conclude this paper with an exposition of classical approximation results based on primal-dual algorithms that are covered by our framework. We match all of the known results. Additionally, we provide some new insight in a generalization of the flow cover on a line problem.
Crowdsensing in Opportunistic Mobile Social Networks: A Context-aware and Human-centric Approach
Venue: arXiv cs.SI 2017
Year: 2017

In recent years, there have been efforts to collect human contact traces during social events (e.g., conferences) using Bluetooth devices (e.g., mobile phones, iMotes). The results of these studies have enabled the ability to do the crowd-sourcing task from within the crowd, in order to answer questions, such as: what is the current density of the crowd, or how many people are attending the event? However, in those studies, the sensing devices are usually distributed and configured in a certain manner. For example, the number of devices is fixed, people register for the devices on a volunteering basis. In this paper, we treat the above problem as an optimization problem and draw the connection to the vertex cover problem in graph theory. Since finding the optimal solution for minimum vertex cover problem is NP-complete, approximation algorithms have to be used. However, we will show that the well-known approximation algorithms do not perform well with the crowd-sensing task. In this paper, we propose the notions of node observability and coverage utility score and design a new context-aware approximation algorithm to find vertex cover that is tailored for crowd-sensing task. In addition, we design human-centric bootstrapping strategies to make initial assignment of sensing devices based on meta information about the participants (e.g., interests, friendship). The motivation is to assign the sensing task to a more "socialized" device to obtain better sensing coverage. We perform comprehensive experiments on real-world data traces obtained from previous experimental studies in conference and academic social context. The results show that our proposed approach significantly outperforms the baseline approximation algorithms in terms of sensing coverage.
Semi-Automated & Collaborative Online Training Module For Improving Communication Skills
Venue: arXiv cs.HC 2017
Year: 2017

This paper presents a description and evaluation of the ROC Speak system, a platform that allows ubiquitous access to communication skills training. ROC Speak (available at rocspeak.com) enables anyone to go to a website, record a video, and receive feedback on smile intensity, body movement, volume modulation, filler word usage, unique word usage, word cloud of the spoken words, in addition to overall assessment and subjective comments by peers. Peer comments are automatically ranked and sorted for usefulness and sentiment (i.e., positive vs. negative). We evaluated the system with a diverse group of 56 online participants for a 10-day period. Participants submitted responses to career oriented prompts every other day. The participants were randomly split into two groups: 1) treatment - full feedback from the ROC Speak system; 2) control - written feedback from online peers. When judged by peers (p<.001) and independent raters (p<.05), participants from the treatment group demonstrated statistically significant improvement in overall speaking skills rating while the control group did not. Furthermore, in terms of speaking attributes, treatment group showed an improvement in friendliness (p<.001), vocal variety (p<.05) and articulation (p<.01).
GazeDirector: Fully Articulated Eye Gaze Redirection in Video
Venue: arXiv cs.CV 2017
Year: 2017

We present GazeDirector, a new approach for eye gaze redirection that uses model-fitting. Our method first tracks the eyes by fitting a multi-part eye region model to video frames using analysis-by-synthesis, thereby recovering eye region shape, texture, pose, and gaze simultaneously. It then redirects gaze by 1) warping the eyelids from the original image using a model-derived flow field, and 2) rendering and compositing synthesized 3D eyeballs onto the output image in a photorealistic manner. GazeDirector allows us to change where people are looking without person-specific training data, and with full articulation, i.e. we can precisely specify new gaze directions in 3D. Quantitatively, we evaluate both model-fitting and gaze synthesis, with experiments for gaze estimation and redirection on the Columbia gaze dataset. Qualitatively, we compare GazeDirector against recent work on gaze redirection, showing better results especially for large redirection angles. Finally, we demonstrate gaze redirection on YouTube videos by introducing new 3D gaze targets and by manipulating visual behavior.
Partially Occluded Leaf Recognition via Subgraph Matching and Energy Optimization
Venue: arXiv cs.CV 2017
Year: 2017

We present an approach to match partially occluded plant leaves with databases of full plant leaves. Although contour based 2D shape matching has been studied extensively in the last couple of decades, matching occluded leaves with full leaf databases is an open and little worked on problem. Classifying occluded plant leaves is even more challenging than full leaf matching because of large variations and complexity of leaf structures. Matching an occluded contour with all the full contours in a database is an NP-hard problem [Su et al. ICCV2015], so our algorithm is necessarily suboptimal.
On weight initialization in deep neural networks
Venue: arXiv cs.LG 2017
Year: 2017

A proper initialization of the weights in a neural network is critical to its convergence. Current insights into weight initialization come primarily from linear activation functions. In this paper, I develop a theory for weight initializations with non-linear activations. First, I derive a general weight initialization strategy for any neural network using activation functions differentiable at 0. Next, I derive the weight initialization strategy for the Rectified Linear Unit (RELU), and provide theoretical insights into why the Xavier initialization is a poor choice with RELU activations. My analysis provides a clear demonstration of the role of non-linearities in determining the proper weight initializations.
A Case Study on the Parametric Occurrence of Multiple Steady States
Venue: arXiv cs.SC 2017
Year: 2017

We consider the problem of determining multiple steady states for positive real values in models of biological networks. Investigating the potential for these in models of the mitogen-activated protein kinases (MAPK) network has consumed considerable effort using special insights into the structure of corresponding models. Here we apply combinations of symbolic computation methods for mixed equality/inequality systems, specifically virtual substitution, lazy real triangularization and cylindrical algebraic decomposition. We determine multistationarity of an 11-dimensional MAPK network when numeric values are known for all but potentially one parameter. More precisely, our considered model has 11 equations in 11 variables and 19 parameters, 3 of which are of interest for symbolic treatment, and furthermore positivity conditions on all variables and parameters.
Random Forest Ensemble of Support Vector Regression Models for Solar Power Forecasting
Venue: arXiv cs.LG 2017
Year: 2017

To mitigate the uncertainty of variable renewable resources, two off-the-shelf machine learning tools are deployed to forecast the solar power output of a solar photovoltaic system. The support vector machines generate the forecasts and the random forest acts as an ensemble learning method to combine the forecasts. The common ensemble technique in wind and solar power forecasting is the blending of meteorological data from several sources. In this study though, the present and the past solar power forecasts from several models, as well as the associated meteorological data, are incorporated into the random forest to combine and improve the accuracy of the day-ahead solar power forecasts. The performance of the combined model is evaluated over the entire year and compared with other combining techniques.
Hardware Accelerated SDR Platform for Adaptive Air Interfaces
Venue: arXiv cs.NI 2017
Year: 2017

The future 5G wireless infrastructure will support any-to-any connectivity between densely deployed smart objects that form the emerging paradigm known as the Internet of Everything (IoE). Compared to traditional wireless networks that enable communication between devices using a single technology, 5G networks will need to support seamless connectivity between heterogeneous wireless objects and IoE networks. To tackle the complexity and versatility of future IoE networks, 5G will need to guarantee optimal usage of both spectrum and energy resources and further support technology-agnostic connectivity between objects. One way to realize this is to combine intelligent network control with adaptive software defined air interfaces. In this paper, a flexible and compact platform is proposed for on-the-fly composition of low-power adaptive air interfaces, based on hardware/software co-processing. Compared to traditional Software Defined Radio (SDR) systems that perform computationally-intensive signal processing algorithms in software, consume significantly power and have a large form factor, the proposed platform uses modern hybrid FPGA technology combined with novel ideas such as RF Network-on-Chip (RFNoC) and partial reconfiguration. The resulting system enables composition of reconfigurable air interfaces based on hardware/software co-processing on a single chip, allowing high processing throughput, at a smaller form factor and reduced power consumption.
Stability and Recovery for Independence Systems
Venue: arXiv cs.DS 2017
Year: 2017

Two genres of heuristics that are frequently reported to perform much better on "real-world" instances than in the worst case are greedy algorithms and local search algorithms. In this paper, we systematically study these two types of algorithms for the problem of maximizing a monotone submodular set function subject to downward-closed feasibility constraints. We consider perturbation-stable instances, in the sense of Bilu and Linial, and precisely identify the stability threshold beyond which these algorithms are guaranteed to recover the optimal solution. Byproducts of our work include the first definition of perturbation-stability for non-additive objective functions, and a resolution of the worst-case approximation guarantee of local search in p-extendible systems.
Evaluating Security and Availability of Multiple Redundancy Designs when Applying Security Patches
Venue: arXiv cs.CR 2017
Year: 2017

In most of modern enterprise systems, redundancy configuration is often considered to provide availability during the part of such systems is being patched. However, the redundancy may increase the attack surface of the system. In this paper, we model and assess the security and capacity oriented availability of multiple server redundancy designs when applying security patches to the servers. We construct (1) a graphical security model to evaluate the security under potential attacks before and after applying patches, (2) a stochastic reward net model to assess the capacity oriented availability of the system with a patch schedule. We present our approach based on case study and model-based evaluation for multiple design choices. The results show redundancy designs increase capacity oriented availability but decrease security when applying security patches. We define functions that compare values of security metrics and capacity oriented availability with the chosen upper/lower bounds to find design choices that satisfy both security and availability requirements.
Towards a foundation for holistic power system validation and testing
Venue: arXiv cs.SY 2017
Year: 2017

Renewable energy sources and further electrificationof energy consumption are key enablers for decreasing green-house gas emissions, but also introduce increased complexitywithin the electric power system. The increased availability ofautomation, information and communication technology, andintelligent solutions for system operation have transformed thepower system into a smart grid. In order to support thedevelopment process of smart grid solutions on the system level,testing has to be done in a holistic manner, covering the multi-domain aspect of such complex systems. This paper introducesthe concept of holistic power system testing and discuss first stepstowards a corresponding methodology that is being developed inthe European ERIGrid research infrastructure project.
Parameter reduction in nonlinear state-space identification of hysteresis
Venue: arXiv cs.SY 2017
Year: 2017

Hysteresis is a highly nonlinear phenomenon, showing up in a wide variety of science and engineering problems. The identification of hysteretic systems from input-output data is a challenging task. Recent work on black-box polynomial nonlinear state-space modeling for hysteresis identification has provided promising results, but struggles with a large number of parameters due to the use of multivariate polynomials. This drawback is tackled in the current paper by applying a decoupling approach that results in a more parsimonious representation involving univariate polynomials. This work is carried out numerically on input-output data generated by a Bouc-Wen hysteretic model and follows up on earlier work of the authors. The current article discusses the polynomial decoupling approach and explores the selection of the number of univariate polynomials with the polynomial degree, as well as the connections with neural network modeling. We have found that the presented decoupling approach is able to reduce the number of parameters of the full nonlinear model up to about 50\%, while maintaining a comparable output error level.
Application-Level Resilience Modeling for HPC Fault Tolerance
Venue: arXiv cs.DC 2017
Year: 2017

Understanding the application resilience in the presence of faults is critical to address the HPC resilience challenge. Currently, we largely rely on random fault injection (RFI) to quantify the application resilience. However, RFI provides little information on how fault tolerance happens, and RFI results are often not deterministic due to its random nature. In this paper, we introduce a new methodology to quantify the application resilience. Our methodology is based on the observation that at the application level, the application resilience to faults is due to the application-level fault masking. The application-level fault masking happens because of application-inherent semantics and program constructs. Based on this observation, we analyze application execution information and use a data-oriented approach to model the application resilience. We use our model to study how and why HPC applications can (or cannot) tolerate faults. We demonstrate tangible benefits of using the model to direct fault tolerance mechanisms.
Tales of Emotion and Stock in China: Volatility, Causality and Prediction
Venue: arXiv cs.CY 2017
Year: 2017

How the online social media, like Twitter or its variant Weibo, interacts with the stock market and whether it can be a convincing proxy to predict the stock market have been debated for years, especially for China. As the traditional theory in behavioral finance states, the individual emotions can influence decision-makings of investors, it is reasonable to further explore these controversial topics systematically from the perspective of online emotions, which are richly carried by massive tweets in social media. Through thorough studies on over 10 million stock-relevant tweets and 3 million investors from Weibo, it is revealed that inexperienced investors with high emotional volatility are more sensible to the market fluctuations than the experienced or institutional ones, and their dominant occupation also indicates that the Chinese market might be more emotional as compared to its western counterparts. Then both correlation analysis and causality test demonstrate that five attributes of the stock market in China can be competently predicted by various online emotions, like disgust, joy, sadness and fear. Specifically, the presented prediction model significantly outperforms the baseline model, including the one taking purely financial time series as input features, on predicting five attributes of the stock market under the $K$-means discretization. We also employ this prediction model in the scenario of realistic online application and its performance is further testified.
SurfCut: Surfaces of Minimal Paths From Topological Structures
Venue: arXiv cs.CV 2017
Year: 2017

We present SurfCut, an algorithm for extracting a smooth, simple surface with an unknown 3D curve boundary from a noisy 3D image and a seed point. Our method is built on the novel observation that certain ridge curves of a function defined on a front propagated using the Fast Marching algorithm lie on the surface. Our method extracts and cuts these ridges to form the surface boundary. Our surface extraction algorithm is built on the novel observation that the surface lies in a valley of the distance from Fast Marching. We show that the resulting surface is a collection of minimal paths. Using the framework of cubical complexes and Morse theory, we design algorithms to extract these critical structures robustly. Experiments on three 3D datasets show the robustness of our method, and that it achieves higher accuracy with lower computational cost than state-of-the-art.
Scheduling Parallel and Distributed Processing for Automotive Data Stream Management System
Venue: arXiv cs.DC 2017
Year: 2017

In this paper, to analyze end-to-end timing behavior in heterogeneous processor and network environments accurately, we adopt a heterogeneous selection value on communication contention (HSV_CC) algorithm, which can synchronize tasks and messages simultaneously, for stream processing distribution. In order to adapt HSV_CC to automotive data stream management system (DSMSs), one must address three issues: (i) previous task and message schedules might lead to less efficient resource usages; (ii) the conventional method to determine the task scheduling order may not be best suited to deal with stream processing graphs, and; (iii) there is a need to be able to schedule tasks with time-varying computational requirements efficiently. To address (i), we propose the heterogeneous value with load balancing and communication contention (HVLB_CC) (A) algorithm, which considers load balancing in addition to the parameters considered by the HSV_CC algorithm. We propose HVLB_CC (B) to address issue (ii). HVLB_CC (B) can deal with stream processing task graphs and more various directed acyclic graphs to prevent assigning a higher priority to successor tasks. In addition, to address issue (iii), we propose HVLB_CC_IC. To schedule tasks more efficiently with various computation times, HVLB_CC_IC utilizes schedule holes left in processors. These idle time slots can be used for the execution of an optional part to generate more precise data results by applying imprecise computation models. Experimental results demonstrate that the proposed algorithms improve minimum schedule length, accuracy, and load balancing significantly compared to the HSV_CC algorithm. In addition, the proposed HVLB_CC (B) algorithm can schedule more varied task graphs without reducing performance, and, using imprecise computation models, HVLB_CC_IC yields higher precision data than HVLB_CC without imprecise computation models.
Non-polynomial Worst-Case Analysis of Recursive Programs
Venue: arXiv cs.PL 2017
Year: 2017

We study the problem of developing efficient approaches for proving worst-case bounds of non-deterministic recursive programs. Ranking functions are sound and complete for proving termination and worst-case bounds of nonrecursive programs. First, we apply ranking functions to recursion, resulting in measure functions. We show that measure functions provide a sound and complete approach to prove worst-case bounds of non-deterministic recursive programs. Our second contribution is the synthesis of measure functions in nonpolynomial forms. We show that non-polynomial measure functions with logarithm and exponentiation can be synthesized through abstraction of logarithmic or exponentiation terms, Farkas' Lemma, and Handelman's Theorem using linear programming. While previous methods obtain worst-case polynomial bounds, our approach can synthesize bounds of the form $\mathcal{O}(n\log n)$ as well as $\mathcal{O}(n^r)$ where $r$ is not an integer. We present experimental results to demonstrate that our approach can obtain efficiently worst-case bounds of classical recursive algorithms such as (i) Merge-Sort, the divide-and-conquer algorithm for the Closest-Pair problem, where we obtain $\mathcal{O}(n \log n)$ worst-case bound, and (ii) Karatsuba's algorithm for polynomial multiplication and Strassen's algorithm for matrix multiplication, where we obtain $\mathcal{O}(n^r)$ bound such that $r$ is not an integer and close to the best-known bounds for the respective algorithms.