OpenRaiser/Intern-Atlas huggingface dataset:
Gyroscope-Aided Motion Deblurring with Deep Networks
Venue: arXiv cs.CV 2018
Year: 2018

We propose a deblurring method that incorporates gyroscope measurements into a convolutional neural network (CNN). With the help of such measurements, it can handle extremely strong and spatially-variant motion blur. At the same time, the image data is used to overcome the limitations of gyro-based blur estimation. To train our network, we also introduce a novel way of generating realistic training data using the gyroscope. The evaluation shows a clear improvement in visual quality over the state-of-the-art while achieving real-time performance. Furthermore, the method is shown to improve the performance of existing feature detectors and descriptors against the motion blur.
How UX Practitioners Produce Findings in Usability Testing
Venue: arXiv cs.HC 2018
Year: 2018

Usability testing has long been a core interest of HCI research and forms a key element of industry practice. Yet our knowledge of it harbours striking absences. There are few, if any detailed accounts of the contingent, material ways in which usability testing is actually practiced. Further, it is rare that industry practitioners' testing work is treated as indigenous and particular (instead subordinated as a `compromised' version). To service these problems, this paper presents an ethnomethodological study of usability testing practices in a design consultancy. It unpacks how findings are produced in and as the work of observers analysing the test as it unfolds between moderators taking participants through relevant tasks. The study nuances conventional views of usability findings as straightforwardly `there to be found' or `read off' by competent evaluators. It explores how evaluators / observers collaboratively work to locate relevant troubles in the test's unfolding. However, in the course of doing this work, potential candidate troubles may also routinely be dissipated and effectively `ignored' in one way or another. The implications of the study suggest refinements to current understandings of usability evaluations, and affirm the value to HCI in studying industry practitioners more deeply.
A Unified Framework for Clustering Constrained Data without Locality Property
Venue: arXiv cs.CG 2018
Year: 2018

In this paper, we consider a class of constrained clustering problems of points in $\mathbb{R}^{d}$, where $d$ could be rather high. A common feature of these problems is that their optimal clusterings no longer have the locality property (due to the additional constraints), which is a key property required by many algorithms for their unconstrained counterparts. To overcome the difficulty caused by the loss of locality, we present in this paper a unified framework, called {\em Peeling-and-Enclosing (PnE)}, to iteratively solve two variants of the constrained clustering problems, {\em constrained $k$-means clustering} ($k$-CMeans) and {\em constrained $k$-median clustering} ($k$-CMedian). Our framework is based on two standalone geometric techniques, called {\em Simplex Lemma} and {\em Weaker Simplex Lemma}, for $k$-CMeans and $k$-CMedian, respectively. The simplex lemma (or weaker simplex lemma) enables us to efficiently approximate the mean (or median) point of an unknown set of points by searching a small-size grid, independent of the dimensionality of the space, in a simplex (or the surrounding region of a simplex), and thus can be used to handle high dimensional data. If $k$ and $\frac{1}ε$ are fixed numbers, our framework generates, in nearly linear time ({\em i.e.,} $O(n(\log n)^{k+1}d)$), $O((\log n)^{k})$ $k$-tuple candidates for the $k$ mean or median points, and one of them induces a $(1+ε)$-approximation for $k$-CMeans or $k$-CMedian, where $n$ is the number of points. Combining this unified framework with a problem-specific selection algorithm (which determines the best $k$-tuple candidate), we obtain a $(1+ε)$-approximation for each of the constrained clustering problems. We expect that our technique will be applicable to other constrained clustering problems without locality.
Fully dynamic $3/2$ approximate maximum cardinality matching in $O(\sqrt{n})$ update time
Venue: arXiv cs.DS 2018
Year: 2018

We present a randomized algorithm to maintain a maximal matching without 3 length augmenting paths in the fully dynamic setting. Consequently, we maintain a $3/2$ approximate maximum cardinality matching. Our algorithm takes expected amortized $O(\sqrt{n})$ time where $n$ is the number of vertices in the graph when the update sequence is generated by an oblivious adversary. Over any sequence of $t$ edge insertions and deletions presented by an oblivious adversary, the total update time of our algorithm is $O(t\sqrt{n})$ in expectation and $O(t\sqrt{n} + n \log n)$ with high probability. To the best of our knowledge, our algorithm is the first one to maintain an approximate matching in which all augmenting paths are of length at least $5$ in $o(\sqrt{m})$ update time.
Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learning
Venue: arXiv cs.LG 2018
Year: 2018

Random Matrix Theory (RMT) is applied to analyze weight matrices of Deep Neural Networks (DNNs), including both production quality, pre-trained models such as AlexNet and Inception, and smaller models trained from scratch, such as LeNet5 and a miniature-AlexNet. Empirical and theoretical results clearly indicate that the DNN training process itself implicitly implements a form of Self-Regularization. The empirical spectral density (ESD) of DNN layer matrices displays signatures of traditionally-regularized statistical models, even in the absence of exogenously specifying traditional forms of explicit regularization. Building on relatively recent results in RMT, most notably its extension to Universality classes of Heavy-Tailed matrices, we develop a theory to identify 5+1 Phases of Training, corresponding to increasing amounts of Implicit Self-Regularization. These phases can be observed during the training process as well as in the final learned DNNs. For smaller and/or older DNNs, this Implicit Self-Regularization is like traditional Tikhonov regularization, in that there is a "size scale" separating signal from noise. For state-of-the-art DNNs, however, we identify a novel form of Heavy-Tailed Self-Regularization, similar to the self-organization seen in the statistical physics of disordered systems. This results from correlations arising at all size scales, which arises implicitly due to the training process itself. This implicit Self-Regularization can depend strongly on the many knobs of the training process. By exploiting the generalization gap phenomena, we demonstrate that we can cause a small model to exhibit all 5+1 phases of training simply by changing the batch size. This demonstrates that---all else being equal---DNN optimization with larger batch sizes leads to less-well implicitly-regularized models, and it provides an explanation for the generalization gap phenomena.
Ancient Coin Classification Using Graph Transduction Games
Venue: arXiv cs.CV 2018
Year: 2018

Recognizing the type of an ancient coin requires theoretical expertise and years of experience in the field of numismatics. Our goal in this work is automatizing this time consuming and demanding task by a visual classification framework. Specifically, we propose to model ancient coin image classification using Graph Transduction Games (GTG). GTG casts the classification problem as a non-cooperative game where the players (the coin images) decide their strategies (class labels) according to the choices made by the others, which results with a global consensus at the final labeling. Experiments are conducted on the only publicly available dataset which is composed of 180 images of 60 types of Roman coins. We demonstrate that our approach outperforms the literature work on the same dataset with the classification accuracy of 73.6% and 87.3% when there are one and two images per class in the training set, respectively.
Relating Metric Distortion and Fairness of Social Choice Rules
Venue: arXiv cs.GT 2018
Year: 2018

One way of evaluating social choice (voting) rules is through a utilitarian distortion framework. In this model, we assume that agents submit full rankings over the alternatives, and these rankings are generated from underlying, but unknown, quantitative costs. The \emph{distortion} of a social choice rule is then the ratio of the total social cost of the chosen alternative to the optimal social cost of any alternative; since the true costs are unknown, we consider the worst-case distortion over all possible underlying costs. Analogously, we can consider the worst-case \emph{fairness ratio} of a social choice rule by comparing a useful notion of fairness (based on approximate majorization) for the chosen alternative to that of the optimal alternative. With an additional metric assumption -- that the costs equal the agent-alternative distances in some metric space -- it is known that the Copeland rule achieves both a distortion and fairness ratio of at most 5. For other rules, only bounds on the distortion are known, e.g., the popular Single Transferable Vote (STV) rule has distortion $O(\log m)$, where $m$ is the number of alternatives. We prove that the distinct notions of distortion and fairness ratio are in fact closely linked -- within an additive factor of 2 for any voting rule -- and thus STV also achieves an $O(\log m)$ fairness ratio. We further extend the notions of distortion and fairness ratio to social choice rules choosing a \emph{set} of alternatives. By relating the distortion of single-winner rules to multiple-winner rules, we establish that Recursive Copeland achieves a distortion of 5 and a fairness ratio of at most 7 for choosing a set of alternatives.
Future Architecture of the Interplanetary Internet
Venue: arXiv cs.NI 2018
Year: 2018

Fifty years after the Apollo program, space exploration has recently been regaining popularity thanks to missions with high media coverage. Future space exploration and space station missions will require specific networks to interconnect Earth with other objects and planets in the solar system. The interconnections of these networks form the core of an Interplanetary Internet (IPN). More specifically, we consider the IPN as the combination of physical infrastructure, network architecture, and technologies to provide communication and navigation services for missions and further applications. Compared to the current implementation of the Internet, nodes composing the core of the IPN are highly heterogeneous (base stations on planets, satellites etc.). Moreover, nodes are in constant motion over intersecting elliptical planes, which results in highly variable delays and even temporary unavailability of parts of the network. As such, an IPN has to overcome the challenges of conventional opportunistic networks, with much higher latency and jitter (from a couple of minutes to several days) and the additional constraint of long-term autonomous operations. In this paper, we highlight the challenges of IPN, demonstrate the elements to deploy within the areas of interest, and propose the technologies to handle deep space communication. We provide recommendations for an evolutionary IPN implementation, coherent with specific milestones of space exploration.
Performance Comparison of some Synchronous Adders
Venue: arXiv cs.AR 2018
Year: 2018

This technical note compares the performance of some synchronous adders which correspond to the following architectures: i) ripple carry adder (RCA), ii) recursive carry lookahead adder (RCLA), iii) hybrid RCLA-RCA with the RCA used in the least significant adder bit positions, iv) block carry lookahead adder (BCLA), v) hybrid BCLA-RCA with the RCA used in the least significant adder bit positions, and vi) non-uniform input partitioned carry select adders (CSLAs) without and with the binary to excess-1 code (BEC) converter. The 32-bit addition was considered as an example operation. The adder architectures mentioned were implemented by targeting a typical case PVT specification (high threshold voltage, supply voltage of 1.05V and operating temperature of 25 degrees Celsius) of the Synopsys 32/28nm CMOS technology. The comparison leads to the following observations: i) the hybrid CCLA-RCA is preferable to the other adders in terms of the speed, the power-delay product, and the energy-delay product, ii) the non-uniform input partitioned CSLA without the BEC converter is preferable to the other adders in terms of the area-delay product, and iii) the RCA incorporating the full adder present in the standard digital cell library is preferable to the other adders in terms of the power-delay-area product.
Training compact deep learning models for video classification using circulant matrices
Venue: arXiv cs.CV 2018
Year: 2018

In real world scenarios, model accuracy is hardly the only factor to consider. Large models consume more memory and are computationally more intensive, which makes them difficult to train and to deploy, especially on mobile devices. In this paper, we build on recent results at the crossroads of Linear Algebra and Deep Learning which demonstrate how imposing a structure on large weight matrices can be used to reduce the size of the model. We propose very compact models for video classification based on state-of-the-art network architectures such as Deep Bag-of-Frames, NetVLAD and NetFisherVectors. We then conduct thorough experiments using the large YouTube-8M video classification dataset. As we will show, the circulant DBoF embedding achieves an excellent trade-off between size and accuracy.
Sparse Gaussian Process Temporal Difference Learning for Marine Robot Navigation
Venue: arXiv cs.LG 2018
Year: 2018

We present a method for Temporal Difference (TD) learning that addresses several challenges faced by robots learning to navigate in a marine environment. For improved data efficiency, our method reduces TD updates to Gaussian Process regression. To make predictions amenable to online settings, we introduce a sparse approximation with improved quality over current rejection-based sparse methods. We derive the predictive value function posterior and use the moments to obtain a new algorithm for model-free policy evaluation, SPGP-SARSA. With simple changes, we show SPGP-SARSA can be reduced to a model-based equivalent, SPGP-TD. We perform comprehensive simulation studies and also conduct physical learning trials with an underwater robot. Our results show SPGP-SARSA can outperform the state-of-the-art sparse method, replicate the prediction quality of its exact counterpart, and be applied to solve underwater navigation tasks.
Efficient Seismic fragility curve estimation by Active Learning on Support Vector Machines
Venue: arXiv cs.LG 2018
Year: 2018

Fragility curves which express the failure probability of a structure, or critical components, as function of a loading intensity measure are nowadays widely used (i) in Seismic Probabilistic Risk Assessment studies, (ii) to evaluate impact of construction details on the structural performance of installations under seismic excitations or under other loading sources such as wind. To avoid the use of parametric models such as lognormal model to estimate fragility curves from a reduced number of numerical calculations, a methodology based on Support Vector Machines coupled with an active learning algorithm is proposed in this paper. In practice, input excitation is reduced to some relevant parameters and, given these parameters, SVMs are used for a binary classification of the structural responses relative to a limit threshold of exceedance. Since the output is not only binary, this is a score, a probabilistic interpretation of the output is exploited to estimate very efficiently fragility curves as score functions or as functions of classical seismic intensity measures.
An Exploration of Blockchain Enabled Decentralized Capability based Access Control Strategy for Space Situation Awareness
Venue: arXiv cs.CR 2018
Year: 2018

Space situation awareness (SSA) includes tracking of active and inactive resident space objects (RSOs) and assessing the space environment through sensor data collection and processing. To enhance SSA, the dynamic data-driven applications systems (DDDAS) framework couples on-line data with off-line models to enhance system performance. Using feedback control, sensor management, and communications reliability. For information management, there is a need for identity authentication and access control to ensure the integrity of exchanged data as well as to grant authorized entities access right to data and services. Due to decentralization and heterogeneity of SSA systems, it is challenging to build an efficient centralized access control system, which could either be a performance bottleneck or the single point of failure. Inspired by the blockchain and smart contract technology, this paper introduces BlendCAC, a decentralized authentication and capability-based access control mechanism to enable effective protection for devices, services and information in SSA networks. To achieve secure identity authentication, the BlendCAC leverages the blockchain to create virtual trust zones and a robust identity-based capability token management strategy is proposed. A proof-of-concept prototype has been implemented on both resources-constrained devices and more powerful computing devices, and is tested on a private Ethereum blockchain network. The experimental results demonstrate the feasibility of the BlendCAC scheme to offer a decentralized, scalable, lightweight and fine-grained access control solution for space system towards SSA.
NimbRo Rescue: Solving Disaster-Response Tasks through Mobile Manipulation Robot Momaro
Venue: arXiv cs.RO 2018
Year: 2018

Robots that solve complex tasks in environments too dangerous for humans to enter are desperately needed, e.g. for search and rescue applications. We describe our mobile manipulation robot Momaro, with which we participated successfully in the DARPA Robotics Challenge. It features a unique locomotion design with four legs ending in steerable wheels, which allows it both to drive omnidirectionally and to step over obstacles or climb. Furthermore, we present advanced communication and teleoperation approaches, which include immersive 3D visualization, and 6D tracking of operator head and arm motions. The proposed system is evaluated in the DARPA Robotics Challenge, the DLR SpaceBot Cup Qualification and lab experiments. We also discuss the lessons learned from the competitions.
Synthesis of Majority Expressions through Primitive Function Manipulation
Venue: arXiv cs.ET 2018
Year: 2018

Due to technology advancements and circuits miniaturization, the study of logic systems that can be applied to nanotechnology has been progressing steadily. Among the creation of nanoeletronic circuits reversible and majority logic stand out. This paper proposes the MPC (Majority Primitives Combination) algorithm, used for majority logic synthesis. The algorithm receives a truth table as input and returns a majority function that covers the same set of minterms. The formulation of a valid output function is made with the combination of previously optimized functions. As cost criteria the algorithm searches for a function with the least number of levels, followed by the least number of gates, inverters, and gate inputs. In this paper it's also presented a comparison between the MPC and the exact_mig, currently considered the best algorithm for majority synthesis. The exact_mig encode the exact synthesis of majority functions using the number of levels and gates as cost criteria. The MPC considers two additional cost criteria, the number of inverters and the number of gate inputs, with the goal to further improve exact_mig results. Tests have shown that both algorithms return optimal solutions for all functions with 3 input variables. For functions with 4 inputs, the MPC is able to further improve 42,987 (66%) functions and achieves equal results for 7,198 (11%). For functions with 5 input variables, out of a sample of 1,000 randomly generated functions, the MPC further improved 477 (48%) functions and achieved equal results for 112 (11%).
Opinion Formation Threshold Estimates from Different Combinations of Social Media Data-Types
Venue: arXiv cs.SI 2018
Year: 2018

Passive consumption of a quantifiable amount of social media information related to a topic can cause individuals to form opinions. If a substantial amount of these individuals are motivated to take action from their recently established opinions, a movement or public opinion shift can be induced independent of the information's veracity. Given that social media is ubiquitous in modern society, it is imperative that we understand the threshold at which social media data results in opinion formation. The present study estimates population opinion formation thresholds by querying 2222 participants about the number of various social media data-types (i.e., images, videos, and/or messages) that they would need to passively consume to form opinions. Opinion formation is assessed across three dimensions, 1) data-type(s), 2) context, and 3) source. This work provides a theoretical basis for estimating the amount of data needed to influence a population through social media information.
Dihedral Rigidity and Deformation
Venue: arXiv cs.CG 2018
Year: 2018

We consider defining the embedding of a triangle mesh into $R^3$, up to translation, rotation, and scale, by its vector of dihedral angles. Theoretically, we show that locally, almost everywhere, the map from realizable vectors of dihedrals to mesh embeddings is one-to-one. We experiment with a heuristic method for mapping straight-line interpolations in dihedral space to interpolations between mesh embeddings and produce smooth and intuitively appealing morphs between three-dimensional shapes.
GI-OHMS: Graphical Inference to Detect Overlapping Communities
Venue: arXiv cs.SI 2018
Year: 2018

Discovery of communities in complex networks is a topic of considerable recent interest within the complex systems community. Due to the dynamic and rapidly evolving nature of large-scale networks, like online social networks, the notion of stronger local and global interactions among the nodes in communities has become harder to capture. In this paper, we present a novel graphical inference method - GI-OHMS (Graphical Inference in Observed-Hidden variable Merged Seeded network) to solve the problem of overlapping community detection. The novelty of our approach is in transforming the complex and dense network of interest into an observed-hidden merged seeded(OHMS) network, which preserves the important community properties of the network. We further utilize a graphical inference method (Bayesian Markov Random Field) to extract communities. The superiority of our approach lies in two main observations: 1) The extracted OHMS network excludes many weaker connections, thus leading to a higher accuracy of inference 2) The graphical inference step operates on a smaller network, thus having much lower execution time. We demonstrate that our method outperforms the accuracy of other baseline algorithms like OSLOM, DEMON, and LEMON. To further improve execution time, we have a multi-threaded implementation and demonstrate significant speed-up compared to state-of-the-art algorithms.
Towards WARSHIP: Combining Components of Brain-Inspired Computing of RSH for Image Super Resolution
Venue: arXiv cs.AI 2018
Year: 2018

Evolution of deep learning shows that some algorithmic tricks are more durable , while others are not. To the best of our knowledge, we firstly summarize 5 more durable and complete deep learning components for vision, that is, WARSHIP. Moreover, we give a biological overview of WARSHIP, emphasizing brain-inspired computing of WARSHIP. As a step towards WARSHIP, our case study of image super resolution combines 3 components of RSH to deploy a CNN model of WARSHIP-XZNet, which performs a happy medium between speed and performance.