OpenRaiser/Intern-Atlas huggingface dataset:
Human Strategic Steering Improves Performance of Interactive Optimization
Venue: arXiv cs.HC 2020
Year: 2020

A central concern in an interactive intelligent system is optimization of its actions, to be maximally helpful to its human user. In recommender systems for instance, the action is to choose what to recommend, and the optimization task is to recommend items the user prefers. The optimization is done based on earlier user's feedback (e.g. "likes" and "dislikes"), and the algorithms assume the feedback to be faithful. That is, when the user clicks "like," they actually prefer the item. We argue that this fundamental assumption can be extensively violated by human users, who are not passive feedback sources. Instead, they are in control, actively steering the system towards their goal. To verify this hypothesis, that humans steer and are able to improve performance by steering, we designed a function optimization task where a human and an optimization algorithm collaborate to find the maximum of a 1-dimensional function. At each iteration, the optimization algorithm queries the user for the value of a hidden function $f$ at a point $x$, and the user, who sees the hidden function, provides an answer about $f(x)$. Our study on 21 participants shows that users who understand how the optimization works, strategically provide biased answers (answers not equal to $f(x)$), which results in the algorithm finding the optimum significantly faster. Our work highlights that next-generation intelligent systems will need user models capable of helping users who steer systems to pursue their goals.
pyBART: Evidence-based Syntactic Transformations for IE
Venue: arXiv cs.CL 2020
Year: 2020

Syntactic dependencies can be predicted with high accuracy, and are useful for both machine-learned and pattern-based information extraction tasks. However, their utility can be improved. These syntactic dependencies are designed to accurately reflect syntactic relations, and they do not make semantic relations explicit. Therefore, these representations lack many explicit connections between content words, that would be useful for downstream applications. Proposals like English Enhanced UD improve the situation by extending universal dependency trees with additional explicit arcs. However, they are not available to Python users, and are also limited in coverage. We introduce a broad-coverage, data-driven and linguistically sound set of transformations, that makes event-structure and many lexical relations explicit. We present pyBART, an easy-to-use open-source Python library for converting English UD trees either to Enhanced UD graphs or to our representation. The library can work as a standalone package or be integrated within a spaCy NLP pipeline. When evaluated in a pattern-based relation extraction scenario, our representation results in higher extraction scores than Enhanced UD, while requiring fewer patterns.
Robust Non-Linear Matrix Factorization for Dictionary Learning, Denoising, and Clustering
Venue: arXiv cs.LG 2020
Year: 2020

Low dimensional nonlinear structure abounds in datasets across computer vision and machine learning. Kernelized matrix factorization techniques have recently been proposed to learn these nonlinear structures for denoising, classification, dictionary learning, and missing data imputation, by observing that the image of the matrix in a sufficiently large feature space is low-rank. However, these nonlinear methods fail in the presence of sparse noise or outliers. In this work, we propose a new robust nonlinear factorization method called Robust Non-Linear Matrix Factorization (RNLMF). RNLMF constructs a dictionary for the data space by factoring a kernelized feature space; a noisy matrix can then be decomposed as the sum of a sparse noise matrix and a clean data matrix that lies in a low dimensional nonlinear manifold. RNLMF is robust to sparse noise and outliers and scales to matrices with thousands of rows and columns. Empirically, RNLMF achieves noticeable improvements over baseline methods in denoising and clustering.
Stochastic phase-field modeling of brittle fracture: computing multiple crack patterns and their probabilities
Venue: arXiv cs.CE 2020
Year: 2020

In variational phase-field modeling of brittle fracture, the functional to be minimized is not convex, so that the necessary stationarity conditions of the functional may admit multiple solutions. The solution obtained in an actual computation is typically one out of several local minimizers. Evidence of multiple solutions induced by small perturbations of numerical or physical parameters was occasionally recorded but not explicitly investigated in the literature. In this work, we focus on this issue and advocate a paradigm shift, away from the search for one particular solution towards the simultaneous description of all possible solutions (local minimizers), along with the probabilities of their occurrence. Inspired by recent approaches advocating measure-valued solutions (Young measures as well as their generalization to statistical solutions) and their numerical approximations in fluid mechanics, we propose the stochastic relaxation of the variational brittle fracture problem through random perturbations of the functional. We introduce the concept of stochastic solution, with the main advantage that point-to-point correlations of the crack phase fields in the underlying domain can be captured. These stochastic solutions are represented by random fields or random variables with values in the classical deterministic solution spaces. In the numerical experiments, we use a simple Monte Carlo approach to compute approximations to such stochastic solutions. The final result of the computation is not a single crack pattern, but rather several possible crack patterns and their probabilities. The stochastic solution framework using evolving random fields allows additionally the interesting possibility of conditioning the probabilities of further crack paths on intermediate crack patterns.
Anchors Based Method for Fingertips Position Estimation from a Monocular RGB Image using Deep Neural Network
Venue: arXiv cs.CV 2020
Year: 2020

In Virtual, augmented, and mixed reality, the use of hand gestures is increasingly becoming popular to reduce the difference between the virtual and real world. The precise location of the fingertip is essential/crucial for a seamless experience. Much of the research work is based on using depth information for the estimation of the fingertips position. However, most of the work using RGB images for fingertips detection is limited to a single finger. The detection of multiple fingertips from a single RGB image is very challenging due to various factors. In this paper, we propose a deep neural network (DNN) based methodology to estimate the fingertips position. We christened this methodology as an Anchor based Fingertips Position Estimation (ABFPE), and it is a two-step process. The fingertips location is estimated using regression by computing the difference in the location of a fingertip from the nearest anchor point. The proposed framework performs the best with limited dependence on hand detection results. In our experiments on the SCUT-Ego-Gesture dataset, we achieved the fingertips detection error of 2.3552 pixels on a video frame with a resolution of $640 \times 480$ and about $92.98\%$ of test images have average pixel errors of five pixels.
Synchronization of Deterministic Visibly Push-Down Automata
Venue: arXiv cs.FL 2020
Year: 2020

We generalize the concept of synchronizing words for finite automata, which map all states of the automata to the same state, to deterministic visibly push-down automata. Here, a synchronizing word w does not only map all states to the same state but also fulfills some conditions on the stack content of each run after reading w. We consider three types of these stack constraints: after reading w, the stack (1) is empty in each run, (2) contains the same sequence of stack symbols in each run, or (3) contains an arbitrary sequence which is independent of the other runs. We show that in contrast to general deterministic push-down automata, it is decidable for deterministic visibly push-down automata whether there exists a synchronizing word with each of these stack constraints, i.e., the problems are in EXPTIME. Under the constraint (1) the problem is even in P. For the sub-classes of deterministic very visibly push-down automata the problem is in P for all three types of constraints. We further study variants of the synchronization problem where the number of turns in the stack height behavior caused by a synchronizing word is restricted, as well as the problem of synchronizing a variant of a sequential transducer, which shows some visibly behavior, by a word that synchronizes the states and produces the same output on all runs.
A class of examples demonstrating that P is different from NP in the "P vs NP" problem
Venue: arXiv cs.CC 2020
Year: 2020

The CMI Millennium "P vs NP Problem" can be resolved e.g. if one shows at least one counterexample to the conjecture "P is equal to NP". A certain class of problems being such counterexamples is formulated. This implies the rejection of the hypothesis "P is equal to NP" for any conditions satisfying the formulation of the problem. Thus, the solution "P is different from NP" of the problem is proved. The class of counterexamples can be interpreted as any quantum superposition of any finite set of quantum states. The Kochen-Specker theorem is involved. Any fundamentally random choice among a finite set of alternatives belong to NP, but not to P. The conjecture that the set complement of P to NP can be described by that kind of choice is formulated exhaustively.
Evacuação de Dados em Nuvens Ópticas com base no SLA sob Cenário de Desastre
Venue: arXiv cs.DC 2020
Year: 2020

The popularization of cloud computing has provided the emergence of large volumes of data that are stored in Data Centers (DCs). These locations store data of different types, origins, and priorities for their owners. The DCs are subject to natural or man-made attacks. The attacks are diverse and happen quickly after their detection. Therefore, this paper proposes two techniques to evacuate data from threatened DCs to those who are outside the risk zone of the attack. The first technique is based on the Service Level Agreement (SLA) of the data and the second one is based on the order that they arrive at the DC, using the algorithm LIFO. Both techniques performed similarly on the amount of evacuated data and at the time for evacuation. However, the SLA policy distributes the data on a priority scale according to the SLA, while the LIFO policy ranks data on the same scale's priority.
A Dynamical Mean-Field Theory for Learning in Restricted Boltzmann Machines
Venue: arXiv cs.LG 2020
Year: 2020

We define a message-passing algorithm for computing magnetizations in Restricted Boltzmann machines, which are Ising models on bipartite graphs introduced as neural network models for probability distributions over spin configurations. To model nontrivial statistical dependencies between the spins' couplings, we assume that the rectangular coupling matrix is drawn from an arbitrary bi-rotation invariant random matrix ensemble. Using the dynamical functional method of statistical mechanics we exactly analyze the dynamics of the algorithm in the large system limit. We prove the global convergence of the algorithm under a stability criterion and compute asymptotic convergence rates showing excellent agreement with numerical simulations.
Lecture notes: Efficient approximation of kernel functions
Venue: arXiv cs.LG 2020
Year: 2020

These lecture notes endeavour to collect in one place the mathematical background required to understand the properties of kernels in general and the Random Fourier Features approximation of Rahimi and Recht (NIPS 2007) in particular. We briefly motivate the use of kernels in Machine Learning with the example of the support vector machine. We discuss positive definite and conditionally negative definite kernels in some detail. After a brief discussion of Hilbert spaces, including the Reproducing Kernel Hilbert Space construction, we present Mercer's theorem. We discuss the Random Fourier Features technique and then present, with proofs, scalar and matrix concentration results that help us estimate the error incurred by the technique. These notes are the transcription of 10 lectures given at IIT Delhi between January and April 2020.
Workshops on Extreme Scale Design Automation (ESDA) Challenges and Opportunities for 2025 and Beyond
Venue: arXiv cs.CY 2020
Year: 2020

Integrated circuits and electronic systems, as well as design technologies, are evolving at a great rate -- both quantitatively and qualitatively. Major developments include new interconnects and switching devices with atomic-scale uncertainty, the depth and scale of on-chip integration, electronic system-level integration, the increasing significance of software, as well as more effective means of design entry, compilation, algorithmic optimization, numerical simulation, pre- and post-silicon design validation, and chip test. Application targets and key markets are also shifting substantially from desktop CPUs to mobile platforms to an Internet-of-Things infrastructure. In light of these changes in electronic design contexts and given EDA's significant dependence on such context, the EDA community must adapt to these changes and focus on the opportunities for research and commercial success. The CCC workshop series on Extreme-Scale Design Automation, organized with the support of ACM SIGDA, studied challenges faced by the EDA community as well as new and exciting opportunities currently available. This document represents a summary of the findings from these meetings.
MorphoCluster: Efficient Annotation of Plankton images by Clustering
Venue: arXiv cs.CV 2020
Year: 2020

In this work, we present MorphoCluster, a software tool for data-driven, fast and accurate annotation of large image data sets. While already having surpassed the annotation rate of human experts, volume and complexity of marine data will continue to increase in the coming years. Still, this data requires interpretation. MorphoCluster augments the human ability to discover patterns and perform object classification in large amounts of data by embedding unsupervised clustering in an interactive process. By aggregating similar images into clusters, our novel approach to image annotation increases consistency, multiplies the throughput of an annotator and allows experts to adapt the granularity of their sorting scheme to the structure in the data. By sorting a set of 1.2M objects into 280 data-driven classes in 71 hours (16k objects per hour), with 90% of these classes having a precision of 0.889 or higher. This shows that MorphoCluster is at the same time fast, accurate and consistent, provides a fine-grained and data-driven classification and enables novelty detection. MorphoCluster is available as open-source software at https://github.com/morphocluster.
EngMeta -- Metadata for Computational Engineering
Venue: arXiv cs.IR 2020
Year: 2020

Computational engineering generates knowledge through the analysis and interpretation of research data, which is produced by computer simulation. Supercomputers produce huge amounts of research data. To address a research question, a lot of simulations are run over a large parameter space. Therefore, handling this data and keeping an overview becomes a challenge. Data documentation is mostly handled by file and folder names in inflexible file systems, making it almost impossible for data to be findable, accessible, interopable and hence reusable. To enable and improve a structured documentation of research data from computational engineering, we developed EngMeta as a metadata model. We built this model by incorporating existing standards for general descriptive and technical information and adding metadata fields for disciplinespecific information like the components and parameters of the simulated target system and information about the research process like the used methods, software and computational environment. EngMeta functions, in practical use, as the descriptive core for an institutional repository. In order to reduce the burden of description on scientists, we have developed an approach for automatically extracting metadata information from the output and log files of computer simulations. Through a qualitative analysis, we show that EngMeta fulfills the criteria of a good metadata model. Through a quantitative survey, we can show that it meets the needs of engineering scientists.
Effect of Correlation between Information and Energy Links in Secure Wireless Powered Communications
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we investigate the impact of correlation between the energy and information links in wireless power transfer systems, from a physical layer security perspective. With that aim, we first determine how correlation can affect system capacity in practical energy harvesting set-ups in the absence of eavesdroppers. We quantify that even though link correlation improves the average signal-to-noise ratio (SNR) for a fixed transmit power, it also increases its variance, which ultimately degrades capacity. Based on this observation, we show that correlation between the energy and information links may be detrimental/beneficial for the secrecy capacity in the high/low legitimate SNR regime, whenever such correlation affects the legitimate user. Conversely, we also point out that when link correlation for the wiretap link is rigorously accounted for, it barely affects secrecy performance, causing only a minor degradation in some instances.
Equal Area Breaks: A Classification Scheme for Data to Obtain an Evenly-colored Choropleth Map
Venue: arXiv cs.HC 2020
Year: 2020

An efficient algorithm for computing the choropleth map classification scheme known as equal area breaks or geographical quantiles is introduced. An equal area breaks classification aims to obtain a coloring for the map such that the area associated with each of the colors is approximately equal. This is meant to be an alternative to an approach that assigns an equal number of regions with a particular range of property values to each color, called quantiles, which could result in the mapped area being dominated by one or a few colors. Moreover, it is possible that the other colors are barely discernible. This is the case when some regions are much larger than others (e.g., compare Switzerland with Russia). A number of algorithms of varying computational complexity are presented to achieve an equal area assignment to regions. They include a pair of greedy algorithms, as well as an optimal algorithm that is based on dynamic programming. The classification obtained from the optimal equal area algorithm is compared with the quantiles and Jenks natural breaks algorithms and found to be superior from a visual standpoint by a user study. Finally, a modified approach is presented which enables users to vary the extent to which the coloring algorithm satisfies the conflicting goals of equal area for each color with that of assigning an equal number of regions to each color.
Categorized Bandits
Venue: arXiv cs.LG 2020
Year: 2020

We introduce a new stochastic multi-armed bandit setting where arms are grouped inside ``ordered'' categories. The motivating example comes from e-commerce, where a customer typically has a greater appetence for items of a specific well-identified but unknown category than any other one. We introduce three concepts of ordering between categories, inspired by stochastic dominance between random variables, which are gradually weaker so that more and more bandit scenarios satisfy at least one of them. We first prove instance-dependent lower bounds on the cumulative regret for each of these models, indicating how the complexity of the bandit problems increases with the generality of the ordering concept considered. We also provide algorithms that fully leverage the structure of the model with their associated theoretical guarantees. Finally, we have conducted an analysis on real data to highlight that those ordered categories actually exist in practice.
JaxNet: Scalable Blockchain Network
Venue: arXiv cs.DC 2020
Year: 2020

Today's world is organized based on merit and value. A single global currency that's decentralized is needed for a global economy. Bitcoin is a partial solution to this need, however it suffers from scalability problems which prevent it from being mass-adopted. Also, the deflationary nature of bitcoin motivates people to hoard and speculate on them instead of using them for day to day transactions. We propose a scalable, decentralized cryptocurrency that is based on Proof of Work. The solution involves having parallel chains in a closed network using a mechanism which rewards miners proportional to their effort in maintaining the network. The proposed design introduces a novel approach for solving the scalability problem in the blockchain network based on merged mining.
Time Dependence in Non-Autonomous Neural ODEs
Venue: arXiv cs.LG 2020
Year: 2020

Neural Ordinary Differential Equations (ODEs) are elegant reinterpretations of deep networks where continuous time can replace the discrete notion of depth, ODE solvers perform forward propagation, and the adjoint method enables efficient, constant memory backpropagation. Neural ODEs are universal approximators only when they are non-autonomous, that is, the dynamics depends explicitly on time. We propose a novel family of Neural ODEs with time-varying weights, where time-dependence is non-parametric, and the smoothness of weight trajectories can be explicitly controlled to allow a tradeoff between expressiveness and efficiency. Using this enhanced expressiveness, we outperform previous Neural ODE variants in both speed and representational capacity, ultimately outperforming standard ResNet and CNN models on select image classification and video prediction tasks.
Weak ties strengthen anger contagion in social media
Venue: arXiv cs.SI 2020
Year: 2020

Increasing evidence suggests that, similar to face-to-face communications, human emotions also spread in online social media. However, the mechanisms underlying this emotion contagion, for example, whether different feelings spread in unlikely ways or how the spread of emotions relates to the social network, is rarely investigated. Indeed, because of high costs and spatio-temporal limitations, explorations of this topic are challenging using conventional questionnaires or controlled experiments. Because they are collection points for natural affective responses of massive individuals, online social media sites offer an ideal proxy for tackling this issue from the perspective of computational social science. In this paper, based on the analysis of millions of tweets in Weibo, surprisingly, we find that anger travels easily along weaker ties than joy, meaning that it can infiltrate different communities and break free of local traps because strangers share such content more often. Through a simple diffusion model, we reveal that weaker ties speed up anger by applying both propagation velocity and coverage metrics. To the best of our knowledge, this is the first time that quantitative long-term evidence has been presented that reveals a difference in the mechanism by which joy and anger are disseminated. With the extensive proliferation of weak ties in booming social media, our results imply that the contagion of anger could be profoundly strengthened to globalize its negative impact.