OpenRaiser/Intern-Atlas huggingface dataset:
Automated Synthesis of Divide and Conquer Parallelism
Venue: arXiv cs.PL 2017
Year: 2017

This paper focuses on automated synthesis of divide-and-conquer parallelism, which is a common parallel programming skeleton supported by many cross-platform multithreaded libraries. The challenges of producing (manually or automatically) a correct divide-and-conquer parallel program from a given sequential code are two-fold: (1) assuming that individual worker threads execute a code identical to the sequential code, the programmer has to provide the extra code for dividing the tasks and combining the computation results, and (2) sometimes, the sequential code may not be usable as is, and may need to be modified by the programmer. We address both challenges in this paper. We present an automated synthesis technique for the case where no modifications to the sequential code are required, and we propose an algorithm for modifying the sequential code to make it suitable for parallelization when some modification is necessary. The paper presents theoretical results for when this {\em modification} is efficiently possible, and experimental evaluation of the technique and the quality of the produced parallel programs.
Channel Resolvability Theorems for General Sources and Channels
Venue: arXiv cs.IT 2017
Year: 2017

In the problem of channel resolvability, where a given output probability distribution via a channel is approximated by transforming the uniform random numbers, characterizing the asymptotically minimum rate of the size of the random numbers, called the channel resolvability, has been open. This paper derives formulas for the channel resolvability for a given general source and channel pair. We also investigate the channel resolvability in an optimistic sense. It is demonstrated that the derived general formulas recapture a single-letter formula for the stationary memoryless source and channel. When the channel is the identity mapping, the established formulas reduce to an alternative form of the spectral sup-entropy rates, which play a key role in information spectrum methods. The analysis is also extended to the second-order channel resolvability.
Faceness-Net: Face Detection through Deep Facial Part Responses
Venue: arXiv cs.CV 2017
Year: 2017

We propose a deep convolutional neural network (CNN) for face detection leveraging on facial attributes based supervision. We observe a phenomenon that part detectors emerge within CNN trained to classify attributes from uncropped face images, without any explicit part supervision. The observation motivates a new method for finding faces through scoring facial parts responses by their spatial structure and arrangement. The scoring mechanism is data-driven, and carefully formulated considering challenging cases where faces are only partially visible. This consideration allows our network to detect faces under severe occlusion and unconstrained pose variations. Our method achieves promising performance on popular benchmarks including FDDB, PASCAL Faces, AFW, and WIDER FACE.
When Slepian Meets Fiedler: Putting a Focus on the Graph Spectrum
Venue: arXiv cs.LG 2017
Year: 2017

The study of complex systems benefits from graph models and their analysis. In particular, the eigendecomposition of the graph Laplacian lets emerge properties of global organization from local interactions; e.g., the Fiedler vector has the smallest non-zero eigenvalue and plays a key role for graph clustering. Graph signal processing focusses on the analysis of signals that are attributed to the graph nodes. The eigendecomposition of the graph Laplacian allows to define the graph Fourier transform and extend conventional signal-processing operations to graphs. Here, we introduce the design of Slepian graph signals, by maximizing energy concentration in a predefined subgraph for a graph spectral bandlimit. We establish a novel link with classical Laplacian embedding and graph clustering, which provides a meaning to localized graph frequencies.
On the Local Structure of Stable Clustering Instances
Venue: arXiv cs.DS 2017
Year: 2017

We study the classic $k$-median and $k$-means clustering objectives in the beyond-worst-case scenario. We consider three well-studied notions of structured data that aim at characterizing real-world inputs: Distribution Stability (introduced by Awasthi, Blum, and Sheffet, FOCS 2010), Spectral Separability (introduced by Kumar and Kannan, FOCS 2010), Perturbation Resilience (introduced by Bilu and Linial, ICS 2010). We prove structural results showing that inputs satisfying at least one of the conditions are inherently "local". Namely, for any such input, any local optimum is close both in term of structure and in term of objective value to the global optima. As a corollary we obtain that the widely-used Local Search algorithm has strong performance guarantees for both the tasks of recovering the underlying optimal clustering and obtaining a clustering of small cost. This is a significant step toward understanding the success of local search heuristics in clustering applications.
SafeDrive: A Robust Lane Tracking System for Autonomous and Assisted Driving Under Limited Visibility
Venue: arXiv cs.RO 2017
Year: 2017

We present an approach towards robust lane tracking for assisted and autonomous driving, particularly under poor visibility. Autonomous detection of lane markers improves road safety, and purely visual tracking is desirable for widespread vehicle compatibility and reducing sensor intrusion, cost, and energy consumption. However, visual approaches are often ineffective because of a number of factors, including but not limited to occlusion, poor weather conditions, and paint wear-off. Our method, named SafeDrive, attempts to improve visual lane detection approaches in drastically degraded visual conditions without relying on additional active sensors. In scenarios where visual lane detection algorithms are unable to detect lane markers, the proposed approach uses location information of the vehicle to locate and access alternate imagery of the road and attempts detection on this secondary image. Subsequently, by using a combination of feature-based and pixel-based alignment, an estimated location of the lane marker is found in the current scene. We demonstrate the effectiveness of our system on actual driving data from locations in the United States with Google Street View as the source of alternate imagery.
Predicting SMT Solver Performance for Software Verification
Venue: arXiv cs.SE 2017
Year: 2017

The Why3 IDE and verification system facilitates the use of a wide range of Satisfiability Modulo Theories (SMT) solvers through a driver-based architecture. We present Where4: a portfolio-based approach to discharge Why3 proof obligations. We use data analysis and machine learning techniques on static metrics derived from program source code. Our approach benefits software engineers by providing a single utility to delegate proof obligations to the solvers most likely to return a useful result. It does this in a time-efficient way using existing Why3 and solver installations - without requiring low-level knowledge about SMT solver operation from the user.
On Zero Error Capacity of Nearest Neighbor Error Channels with Multilevel Alphabet
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies the zero error capacity of the Nearest Neighbor Error (NNE) channels with a multilevel alphabet. In the NNE channels, a transmitted symbol is a $d$-tuple of elements in $\{0,1,2,\dots, n-1 \}$. It is assumed that only one element error to a nearest neighbor element in a transmitted symbol can occur. The NNE channels can be considered as a special type of limited magnitude error channels, and it is closely related to error models for flash memories. In this paper, we derive a lower bound of the zero error capacity of the NNE channels based on a result of the perfect Lee codes. An upper bound of the zero error capacity of the NNE channels is also derived from a feasible solution of a linear programming problem defined based on the confusion graphs of the NNE channels. As a result, a concise formula of the zero error capacity is obtained using the lower and upper bounds.
Graphs with Extremal Connected Forcing Numbers
Venue: arXiv cs.DM 2017
Year: 2017

Zero forcing is an iterative graph coloring process where at each discrete time step, a colored vertex with a single uncolored neighbor forces that neighbor to become colored. The zero forcing number of a graph is the cardinality of the smallest set of initially colored vertices which forces the entire graph to eventually become colored. Connected forcing is a variant of zero forcing in which the initially colored set of vertices induces a connected subgraph; the analogous parameter of interest is the connected forcing number. In this paper, we characterize the graphs with connected forcing numbers 2 and $n-2$. Our results extend existing characterizations of graphs with zero forcing numbers 2 and $n-2$; we use combinatorial and graph theoretic techniques, in contrast to the linear algebraic approach used to obtain the latter. We also present several other structural results about the connected forcing sets of a graph.
Graph-Based Semi-Supervised Conditional Random Fields For Spoken Language Understanding Using Unaligned Data
Venue: arXiv cs.CL 2017
Year: 2017

We experiment graph-based Semi-Supervised Learning (SSL) of Conditional Random Fields (CRF) for the application of Spoken Language Understanding (SLU) on unaligned data. The aligned labels for examples are obtained using IBM Model. We adapt a baseline semi-supervised CRF by defining new feature set and altering the label propagation algorithm. Our results demonstrate that our proposed approach significantly improves the performance of the supervised model by utilizing the knowledge gained from the graph.
Thin circulant matrices and lower bounds on the complexity of some Boolean operators
Venue: arXiv cs.CC 2017
Year: 2017

We prove a lower bound $Ω\left(\frac{k+l}{k^2l^2}N^{2-\frac{k+l+2}{kl}}\right)$ on the maximal possible weight of a $(k,l)$-free (that is, free of all-ones $k\times l$ submatrices) Boolean circulant $N \times N$ matrix. The bound is close to the known bound for the class of all $(k,l)$-free matrices. As a consequence, we obtain new bounds for several complexity measures of Boolean sums' systems and a lower bound $Ω(N^2\log^{-6} N)$ on the monotone complexity of the Boolean convolution of order $N$.
Innovative Approaches for efficiently Warehousing Complex Data from the Web
Venue: arXiv cs.DB 2017
Year: 2017

Research in data warehousing and OLAP has produced important technologies for the design, management and use of information systems for decision support. With the development of Internet, the availability of various types of data has increased. Thus, users require applications to help them obtaining knowledge from the Web. One possible solution to facilitate this task is to extract information from the Web, transform and load it to a Web Warehouse, which provides uniform access methods for automatic processing of the data. In this chapter, we present three innovative researches recently introduced to extend the capabilities of decision support systems, namely (1) the use of XML as a logical and physical model for complex data warehouses, (2) associating data mining to OLAP to allow elaborated analysis tasks for complex data and (3) schema evolution in complex data warehouses for personalized analyses. Our contributions cover the main phases of the data warehouse design process: data integration and modeling and user driven-OLAP analysis.
Redefinition of the concept of fuzzy set based on vague partition from the perspective of axiomatization
Venue: arXiv cs.AI 2017
Year: 2017

Based on the in-depth analysis of the essence and features of vague phenomena, this paper focuses on establishing the axiomatical foundation of membership degree theory for vague phenomena, presents an axiomatic system to govern membership degrees and their interconnections. On this basis, the concept of vague partition is introduced, further, the concept of fuzzy set introduced by Zadeh in 1965 is redefined based on vague partition from the perspective of axiomatization. The thesis defended in this paper is that the relationship among vague attribute values should be the starting point to recognize and model vague phenomena from a quantitative view.
Alignment of dynamic networks
Venue: arXiv cs.SI 2017
Year: 2017

Networks can model real-world systems in a variety of domains. Network alignment (NA) aims to find a node mapping that conserves similar regions between compared networks. NA is applicable to many fields, including computational biology, where NA can guide the transfer of biological knowledge from well- to poorly-studied species across aligned network regions. Existing NA methods can only align static networks. However, most complex real-world systems evolve over time and should thus be modeled as dynamic networks. We hypothesize that aligning dynamic network representations of evolving systems will produce superior alignments compared to aligning the systems' static network representations, as is currently done. For this purpose, we introduce the first ever dynamic NA method, DynaMAGNA++. This proof-of-concept dynamic NA method is an extension of a state-of-the-art static NA method, MAGNA++. Even though both MAGNA++ and DynaMAGNA++ optimize edge as well as node conservation across the aligned networks, MAGNA++ conserves static edges and similarity between static node neighborhoods, while DynaMAGNA++ conserves dynamic edges (events) and similarity between evolving node neighborhoods. For this purpose, we introduce the first ever measure of dynamic edge conservation and rely on our recent measure of dynamic node conservation. Importantly, the two dynamic conservation measures can be optimized using any state-of-the-art NA method and not just MAGNA++. We confirm our hypothesis that dynamic NA is superior to static NA, under fair comparison conditions, on synthetic and real-world networks, in computational biology and social network domains. DynaMAGNA++ is parallelized and it includes a user-friendly graphical interface.
Accurate Measurement of Power Consumption Overhead During FPGA Dynamic Partial Reconfiguration
Venue: arXiv cs.AR 2017
Year: 2017

In the context of embedded systems design, two important challenges are still under investigation. First, improve real-time data processing, reconfigurability, scalability, and self-adjusting capabilities of hardware components. Second, reduce power consumption through low-power design techniques as clock gating, logic gating, and dynamic partial reconfiguration (DPR) capabilities. Today, several application, e.g., cryptography, Software-defined radio or aerospace missions exploit the benefits of DPR of programmable logic devices. The DPR allows well defined reconfigurable FPGA region to be modified during runtime. However, it introduces an overhead in term of power consumption and time during the reconfiguration phase. In this paper, we present an investigation of power consumption overhead of the DPR process using a high-speed digital oscilloscope and the shunt resistor method. Results in terms of reconfiguration time and power consumption overhead for Virtex 5 FPGAs are shown.
Robotic Haptic Proxies for Collaborative Virtual Reality
Venue: arXiv cs.HC 2017
Year: 2017

We propose a new approach for interaction in Virtual Reality (VR) using mobile robots as proxies for haptic feedback. This approach allows VR users to have the experience of sharing and manipulating tangible physical objects with remote collaborators. Because participants do not directly observe the robotic proxies, the mapping between them and the virtual objects is not required to be direct. In this paper, we describe our implementation, various scenarios for interaction, and a preliminary user study.
Accelerated Evaluation of Automated Vehicles Using Piecewise Mixture Models
Venue: arXiv cs.SY 2017
Year: 2017

The process to certify highly Automated Vehicles has not yet been defined by any country in the world. Currently, companies test Automated Vehicles on public roads, which is time-consuming and inefficient. We proposed the Accelerated Evaluation concept, which uses a modified statistics of the surrounding vehicles and the Importance Sampling theory to reduce the evaluation time by several orders of magnitude, while ensuring the evaluation results are statistically accurate. In this paper, we further improve the accelerated evaluation concept by using Piecewise Mixture Distribution models, instead of Single Parametric Distribution models. We developed and applied this idea to forward collision control system reacting to vehicles making cut-in lane changes. The behavior of the cut-in vehicles was modeled based on more than 403,581 lane changes collected by the University of Michigan Safety Pilot Model Deployment Program. Simulation results confirm that the accuracy and efficiency of the Piecewise Mixture Distribution method outperformed single parametric distribution methods in accuracy and efficiency, and accelerated the evaluation process by almost four orders of magnitude.
Sparse Optimization for Robust and Efficient Loop Closing
Venue: arXiv cs.RO 2017
Year: 2017

It is essential for a robot to be able to detect revisits or loop closures for long-term visual navigation.A key insight explored in this work is that the loop-closing event inherently occurs sparsely, that is, the image currently being taken matches with only a small subset (if any) of previous images. Based on this observation, we formulate the problem of loop-closure detection as a sparse, convex $\ell_1$-minimization problem. By leveraging fast convex optimization techniques, we are able to efficiently find loop closures, thus enabling real-time robot navigation. This novel formulation requires no offline dictionary learning, as required by most existing approaches, and thus allows online incremental operation. Our approach ensures a unique hypothesis by choosing only a single globally optimal match when making a loop-closure decision. Furthermore, the proposed formulation enjoys a flexible representation with no restriction imposed on how images should be represented, while requiring only that the representations are "close" to each other when the corresponding images are visually similar. The proposed algorithm is validated extensively using real-world datasets.
Lower Bounds on the Number of Writing Operations by ILIFC with Inversion Cells
Venue: arXiv cs.IT 2017
Year: 2017

Index-less Indexed Flash Code (ILIFC) is a coding scheme for flash memories, in which one bit of a data sequence is stored in a slice consisting of several cells but the index of the bit is stored implicitly. Although several modified ILIFC schemes have been proposed, in this research we consider an ILIFC with inversion cells(I-ILIFC). The I-ILIFC reduces the total number of cell level changes at each writing request. Computer simulation is used to show that the I-ILIFC improves the average performance of the ILIFC in many cases. This paper presents our derivation of the lower bounds on the number of writing operations by I-ILIFC and shows that the worst-case performance of the I-ILIFC is better than that of the ILIFC if the code length is sufficiently large. Additionally, we consider the tight lower bounds thereon. The results show that the threshold of the code length that determines whether the I-ILIFC improves the worst-case performance of the ILIFC is smaller than that in the first lower bounds.
Co-segmentation for Space-Time Co-located Collections
Venue: arXiv cs.CV 2017
Year: 2017

We present a co-segmentation technique for space-time co-located image collections. These prevalent collections capture various dynamic events, usually by multiple photographers, and may contain multiple co-occurring objects which are not necessarily part of the intended foreground object, resulting in ambiguities for traditional co-segmentation techniques. Thus, to disambiguate what the common foreground object is, we introduce a weakly-supervised technique, where we assume only a small seed, given in the form of a single segmented image. We take a distributed approach, where local belief models are propagated and reinforced with similar images. Our technique progressively expands the foreground and background belief models across the entire collection. The technique exploits the power of the entire set of image without building a global model, and thus successfully overcomes large variability in appearance of the common foreground object. We demonstrate that our method outperforms previous co-segmentation techniques on challenging space-time co-located collections, including dense benchmark datasets which were adapted for our novel problem setting.
Efficient Rank Aggregation via Lehmer Codes
Venue: arXiv cs.LG 2017
Year: 2017

We propose a novel rank aggregation method based on converting permutations into their corresponding Lehmer codes or other subdiagonal images. Lehmer codes, also known as inversion vectors, are vector representations of permutations in which each coordinate can take values not restricted by the values of other coordinates. This transformation allows for decoupling of the coordinates and for performing aggregation via simple scalar median or mode computations. We present simulation results illustrating the performance of this completely parallelizable approach and analytically prove that both the mode and median aggregation procedure recover the correct centroid aggregate with small sample complexity when the permutations are drawn according to the well-known Mallows models. The proposed Lehmer code approach may also be used on partial rankings, with similar performance guarantees.
From State Estimation to Network Reconstruction
Venue: arXiv cs.SY 2017
Year: 2017

We develop methods to efficiently reconstruct the topology and line parameters of a power grid from the measurement of nodal variables. We propose two compressed sensing algorithms that minimize the amount of necessary measurement resources by exploiting network sparsity, symmetry of connections and potential prior knowledge about the connectivity. The algorithms are reciprocal to established state estimation methods, where nodal variables are estimated from few measurements given the network structure. Hence, they enable an advanced grid monitoring where both state and structure of a grid are subject to uncertainties or missing information.