OpenRaiser/Intern-Atlas huggingface dataset:
Fundamental Privacy Limits in Bipartite Networks under Active Attacks
Venue: arXiv cs.SI 2021
Year: 2021

This work considers active deanonymization of bipartite networks. The scenario arises naturally in evaluating privacy in various applications such as social networks, mobility networks, and medical databases. For instance, in active deanonymization of social networks, an anonymous victim is targeted by an attacker (e.g. the victim visits the attacker's website), and the attacker queries her group memberships (e.g. by querying the browser history) to deanonymize her. In this work, the fundamental limits of privacy, in terms of the minimum number of queries necessary for deanonymization, is investigated. A stochastic model is considered, where i) the bipartite network of group memberships is generated randomly, ii) the attacker has partial prior knowledge of the group memberships, and iii) it receives noisy responses to its real-time queries. The bipartite network is generated based on linear and sublinear preferential attachment, and the stochastic block model. The victim's identity is chosen randomly based on a distribution modeling the users' risk of being the victim (e.g. probability of visiting the website). An attack algorithm is proposed which builds upon techniques from communication with feedback, and its performance, in terms of expected number of queries, is analyzed. Simulation results are provided to verify the theoretical derivations.
Geospatial Reasoning with Shapefiles for Supporting Policy Decisions
Venue: arXiv cs.AI 2021
Year: 2021

Policies are authoritative assets that are present in multiple domains to support decision-making. They describe what actions are allowed or recommended when domain entities and their attributes satisfy certain criteria. It is common to find policies that contain geographical rules, including distance and containment relationships among named locations. These locations' polygons can often be found encoded in geospatial datasets. We present an approach to transform data from geospatial datasets into Linked Data using the OWL, PROV-O, and GeoSPARQL standards, and to leverage this representation to support automated ontology-based policy decisions. We applied our approach to location-sensitive radio spectrum policies to identify relationships between radio transmitters coordinates and policy-regulated regions in Census.gov datasets. Using a policy evaluation pipeline that mixes OWL reasoning and GeoSPARQL, our approach implements the relevant geospatial relationships, according to a set of requirements elicited by radio spectrum domain experts.
Uncovering Closed-form Governing Equations of Nonlinear Dynamics from Videos
Venue: arXiv cs.LG 2021
Year: 2021

Distilling analytical models from data has the potential to advance our understanding and prediction of nonlinear dynamics. Although discovery of governing equations based on observed system states (e.g., trajectory time series) has revealed success in a wide range of nonlinear dynamics, uncovering the closed-form equations directly from raw videos still remains an open challenge. To this end, we introduce a novel end-to-end unsupervised deep learning framework to uncover the mathematical structure of equations that governs the dynamics of moving objects in videos. Such an architecture consists of (1) an encoder-decoder network that learns low-dimensional spatial/pixel coordinates of the moving object, (2) a learnable Spatial-Physical Transformation component that creates mapping between the extracted spatial/pixel coordinates and the latent physical states of dynamics, and (3) a numerical integrator-based sparse regression module that uncovers the parsimonious closed-form governing equations of learned physical states and, meanwhile, serves as a constraint to the autoencoder. The efficacy of the proposed method is demonstrated by uncovering the governing equations of a variety of nonlinear dynamical systems depicted by moving objects in videos. The resulting computational framework enables discovery of parsimonious interpretable model in a flexible and accessible sensing environment where only videos are available.
A reversible system based on hybrid toggle radius-4 cellular automata and its application as a block cipher
Venue: arXiv cs.CR 2021
Year: 2021

The dynamical system described herein uses a hybrid cellular automata (CA) mechanism to attain reversibility, and this approach is adapted to create a novel block cipher algorithm called HCA. CA are widely used for modeling complex systems and employ an inherently parallel model. Therefore, applications derived from CA have a tendency to fit very well in the current computational paradigm where scalability and multi-threading potential are quite desirable characteristics. HCA model has recently received a patent by the Brazilian agency INPI. Several evaluations and analyses performed on the model are presented here, such as theoretical discussions related to its reversibility and an analysis based on graph theory, which reduces HCA security to the well-known Hamiltonian cycle problem that belongs to the NP-complete class. Finally, the cryptographic robustness of HCA is empirically evaluated through several tests, including avalanche property compliance and the NIST randomness suite.
AutoFT: Automatic Fine-Tune for Parameters Transfer Learning in Click-Through Rate Prediction
Venue: arXiv cs.IR 2021
Year: 2021

Recommender systems are often asked to serve multiple recommendation scenarios or domains. Fine-tuning a pre-trained CTR model from source domains and adapting it to a target domain allows knowledge transferring. However, optimizing all the parameters of the pre-trained network may result in over-fitting if the target dataset is small and the number of parameters is large. This leads us to think of directly reusing parameters in the pre-trained model which represent more general features learned from multiple domains. However, the design of freezing or fine-tuning layers of parameters requires much manual effort since the decision highly depends on the pre-trained model and target instances. In this work, we propose an end-to-end transfer learning framework, called Automatic Fine-Tuning (AutoFT), for CTR prediction. AutoFT consists of a field-wise transfer policy and a layer-wise transfer policy. The field-wise transfer policy decides how the pre-trained embedding representations are frozen or fine-tuned based on the given instance from the target domain. The layer-wise transfer policy decides how the high?order feature representations are transferred layer by layer. Extensive experiments on two public benchmark datasets and one private industrial dataset demonstrate that AutoFT can significantly improve the performance of CTR prediction compared with state-of-the-art transferring approaches.
Fragmented and Valuable: Following Sentiment Changes in Food Tweets
Venue: arXiv cs.CL 2021
Year: 2021

We analysed sentiment and frequencies related to smell, taste and temperature expressed by food tweets in the Latvian language. To get a better understanding of the role of smell, taste and temperature in the mental map of food associations, we looked at such categories as 'tasty' and 'healthy', which turned out to be mutually exclusive. By analysing the occurrence frequency of words associated with these categories, we discovered that food discourse overall was permeated by `tasty' while the category of 'healthy' was relatively small. Finally, we used the analysis of temporal dynamics to see if we can trace seasonality or other temporal aspects in smell, taste and temperature as reflected in food tweets. Understanding the composition of social media content with relation to smell, taste and temperature in food tweets allows us to develop our work further - on food culture/seasonality and its relation to temperature, on our limited capacity to express smell-related sentiments, and the lack of the paradigm of taste in discussing food healthiness.
Phraseformer: Multimodal Key-phrase Extraction using Transformer and Graph Embedding
Venue: arXiv cs.CL 2021
Year: 2021

Background: Keyword extraction is a popular research topic in the field of natural language processing. Keywords are terms that describe the most relevant information in a document. The main problem that researchers are facing is how to efficiently and accurately extract the core keywords from a document. However, previous keyword extraction approaches have utilized the text and graph features, there is the lack of models that can properly learn and combine these features in a best way. Methods: In this paper, we develop a multimodal Key-phrase extraction approach, namely Phraseformer, using transformer and graph embedding techniques. In Phraseformer, each keyword candidate is presented by a vector which is the concatenation of the text and structure learning representations. Phraseformer takes the advantages of recent researches such as BERT and ExEm to preserve both representations. Also, the Phraseformer treats the key-phrase extraction task as a sequence labeling problem solved using classification task. Results: We analyze the performance of Phraseformer on three datasets including Inspec, SemEval2010 and SemEval 2017 by F1-score. Also, we investigate the performance of different classifiers on Phraseformer method over Inspec dataset. Experimental results demonstrate the effectiveness of Phraseformer method over the three datasets used. Additionally, the Random Forest classifier gain the highest F1-score among all classifiers. Conclusions: Due to the fact that the combination of BERT and ExEm is more meaningful and can better represent the semantic of words. Hence, Phraseformer significantly outperforms single-modality methods.
Understanding Softmax Confidence and Uncertainty
Venue: arXiv cs.LG 2021
Year: 2021

It is often remarked that neural networks fail to increase their uncertainty when predicting on data far from the training distribution. Yet naively using softmax confidence as a proxy for uncertainty achieves modest success in tasks exclusively testing for this, e.g., out-of-distribution (OOD) detection. This paper investigates this contradiction, identifying two implicit biases that do encourage softmax confidence to correlate with epistemic uncertainty: 1) Approximately optimal decision boundary structure, and 2) Filtering effects of deep networks. It describes why low-dimensional intuitions about softmax confidence are misleading. Diagnostic experiments quantify reasons softmax confidence can fail, finding that extrapolations are less to blame than overlap between training and OOD data in final-layer representations. Pre-trained/fine-tuned networks reduce this overlap.
Crosslingual Embeddings are Essential in UNMT for Distant Languages: An English to IndoAryan Case Study
Venue: arXiv cs.CL 2021
Year: 2021

Recent advances in Unsupervised Neural Machine Translation (UNMT) have minimized the gap between supervised and unsupervised machine translation performance for closely related language pairs. However, the situation is very different for distant language pairs. Lack of lexical overlap and low syntactic similarities such as between English and Indo-Aryan languages leads to poor translation quality in existing UNMT systems. In this paper, we show that initializing the embedding layer of UNMT models with cross-lingual embeddings shows significant improvements in BLEU score over existing approaches with embeddings randomly initialized. Further, static embeddings (freezing the embedding layer weights) lead to better gains compared to updating the embedding layer weights during training (non-static). We experimented using Masked Sequence to Sequence (MASS) and Denoising Autoencoder (DAE) UNMT approaches for three distant language pairs. The proposed cross-lingual embedding initialization yields BLEU score improvement of as much as ten times over the baseline for English-Hindi, English-Bengali, and English-Gujarati. Our analysis shows the importance of cross-lingual embedding, comparisons between approaches, and the scope of improvements in these systems.
Quickest change detection with unknown parameters: Constant complexity and near optimality
Venue: arXiv cs.LG 2021
Year: 2021

We consider the quickest change detection problem where both the parameters of pre- and post- change distributions are unknown, which prevents the use of classical simple hypothesis testing. Without additional assumptions, optimal solutions are not tractable as they rely on some minimax and robust variant of the objective. As a consequence, change points might be detected too late for practical applications (in economics, health care or maintenance for instance). Available constant complexity techniques typically solve a relaxed version of the problem, deeply relying on very specific probability distributions and/or some very precise additional knowledge. We consider a totally different approach that leverages the theoretical asymptotic properties of optimal solutions to derive a new scalable approximate algorithm with near optimal performance that runs~in~$\mathcal{O}(1)$, adapted to even more complex Markovian settings.
Multiple simultaneous solution representations in a population based evolutionary algorithm
Venue: arXiv cs.NE 2021
Year: 2021

The representation used for solutions in optimization can have a significant impact on the performance of the optimization method. Traditional population based evolutionary methods have homogeneous populations where all solutions use the same representation. If different representations are to be considered, different runs are required to investigate the relative performance. In this paper, we illustrate the use of a population based evolutionary method, Fresa, inspired by the propagation of Strawberry plants, which allows for multiple representations to co-exist in the population. Fresa is implemented in the Julia language. Julia provides dynamic typing and multiple dispatch. In multiple dispatch, the function invoked is determined, dynamically at run time, by the types of the arguments passed to it. This enables a generic implementation of key steps in the plant propagation algorithm which allows for a heterogeneous population. The search procedure then leads to a competition between representations automatically. A simple case study from the design of operating conditions for a batch reactor system is used to illustrate heterogeneous population based search.
IoT Solution for Winter Survival of Indoor Plants
Venue: arXiv cs.OH 2021
Year: 2021

Not only does cold climate pose a problem for outdoor plants during winter in the northern hemisphere, but for indoor plants as well: low sunlight, low humidity, and simultaneous cold breezes from windows and heat from radiators all cause problems for indoor plants. People often treat their indoor plants like mere decoration, which can often lead to health issues for the plant or even death of the plant, especially during winter. A plant monitoring system was developed to solve this problem, collecting information on plants' indoor environmental conditions (light, humidity, and temperature) and providing this information in an accessible format for the user. Preliminary functional tests were conducted in similar settings where the system would be used. In addition, the concept was evaluated by interviewing an expert in the field of horticulture. The evaluation results indicate that this kind of system could prove useful; however, the tests indicated that the system requires further development to achieve more practical value and wider usage.
A Hybrid APM-CPGSO Approach for Constraint Satisfaction Problem Solving: Application to Remote Sensing
Venue: arXiv cs.AI 2021
Year: 2021

Constraint satisfaction problem (CSP) has been actively used for modeling and solving a wide range of complex real-world problems. However, it has been proven that developing efficient methods for solving CSP, especially for large problems, is very difficult and challenging. Existing complete methods for problem-solving are in most cases unsuitable. Therefore, proposing hybrid CSP-based methods for problem-solving has been of increasing interest in the last decades. This paper aims at proposing a novel approach that combines incomplete and complete CSP methods for problem-solving. The proposed approach takes advantage of the group search algorithm (GSO) and the constraint propagation (CP) methods to solve problems related to the remote sensing field. To the best of our knowledge, this paper represents the first study that proposes a hybridization between an improved version of GSO and CP in the resolution of complex constraint-based problems. Experiments have been conducted for the resolution of object recognition problems in satellite images. Results show good performances in terms of convergence and running time of the proposed CSP-based method compared to existing state-of-the-art methods.
NeRF in detail: Learning to sample for view synthesis
Venue: arXiv cs.CV 2021
Year: 2021

Neural radiance fields (NeRF) methods have demonstrated impressive novel view synthesis performance. The core approach is to render individual rays by querying a neural network at points sampled along the ray to obtain the density and colour of the sampled points, and integrating this information using the rendering equation. Since dense sampling is computationally prohibitive, a common solution is to perform coarse-to-fine sampling. In this work we address a clear limitation of the vanilla coarse-to-fine approach -- that it is based on a heuristic and not trained end-to-end for the task at hand. We introduce a differentiable module that learns to propose samples and their importance for the fine network, and consider and compare multiple alternatives for its neural architecture. Training the proposal module from scratch can be unstable due to lack of supervision, so an effective pre-training strategy is also put forward. The approach, named `NeRF in detail' (NeRF-ID), achieves superior view synthesis quality over NeRF and the state-of-the-art on the synthetic Blender benchmark and on par or better performance on the real LLFF-NeRF scenes. Furthermore, by leveraging the predicted sample importance, a 25% saving in computation can be achieved without significantly sacrificing the rendering quality.
Online Learning for Stochastic Shortest Path Model via Posterior Sampling
Venue: arXiv cs.LG 2021
Year: 2021

We consider the problem of online reinforcement learning for the Stochastic Shortest Path (SSP) problem modeled as an unknown MDP with an absorbing state. We propose PSRL-SSP, a simple posterior sampling-based reinforcement learning algorithm for the SSP problem. The algorithm operates in epochs. At the beginning of each epoch, a sample is drawn from the posterior distribution on the unknown model dynamics, and the optimal policy with respect to the drawn sample is followed during that epoch. An epoch completes if either the number of visits to the goal state in the current epoch exceeds that of the previous epoch, or the number of visits to any of the state-action pairs is doubled. We establish a Bayesian regret bound of $O(B_\star S\sqrt{AK})$, where $B_\star$ is an upper bound on the expected cost of the optimal policy, $S$ is the size of the state space, $A$ is the size of the action space, and $K$ is the number of episodes. The algorithm only requires the knowledge of the prior distribution, and has no hyper-parameters to tune. It is the first such posterior sampling algorithm and outperforms numerically previously proposed optimism-based algorithms.
An Upper Bound on the State-Space Complexity of Brandubh
Venue: arXiv cs.GT 2021
Year: 2021

Before chess came to Northern Europe there was Tafl, a family of asymmetric strategy board games associated strongly with the Vikings. The purpose of this paper is to study the combinatorial state-space complexity of an Irish variation of Tafl called Brandubh. Brandubh was chosen because of its asymmetric goals for the two players, but also its overall complexity well below that of chess, which should make it tractable for strong solving. Brandubh's rules and characteristics are used to gain an understanding of the overall state-space complexity of the game. State-spaces will consider valid piece positions, a generalized rule set, and accepted final state conditions. From these states the upper bound for the complexity of strongly solving Brandubh is derived. Great effort has been placed on thoroughly accounting for all potential states and excluding invalid ones for the game. Overall, the upper bound complexity for solving the game is around 10^14 states, between that of connect four and draughts (checkers).
An Extensible Dashboard Architecture For Visualizing Base And Analyzed Data
Venue: arXiv cs.HC 2021
Year: 2021

Any data analysis, especially the data sets that may be changing often or in real-time, consists of at least three important synchronized components: i) figuring out what to infer (objectives), ii) analysis or computation of objectives, and iii) understanding of the results which may require drill-down and/or visualization. There is a lot of attention paid to the first two of the above components as part of research whereas the understanding as well as deriving actionable decisions is quite tricky. Visualization is an important step towards both understanding (even by non-experts) and inferring the actions that need to be taken. As an example, for Covid-19, knowing regions (say, at the county or state level) that have seen a spike or prone to a spike in cases in the near future may warrant additional actions with respect to gatherings, business opening hours, etc. This paper focuses on an extensible architecture for visualization of base as well as analyzed data. This paper proposes a modular architecture of a dashboard for user-interaction, visualization management, and complex analysis of base data. The contributions of this paper are: i) extensibility of the architecture providing flexibility to add additional analysis, visualizations, and user interactions without changing the workflow, ii) decoupling of the functional modules to ease and speedup development by different groups, and iii) address efficiency issues for display response time. This paper uses Multilayer Networks (or MLNs) for analysis. To showcase the above, we present the implementation of a visualization dashboard, termed CoWiz++ (for Covid Wizard), and elaborate on how web-based user interaction and display components are interfaced seamlessly with the back end modules.
DESCGEN: A Distantly Supervised Dataset for Generating Abstractive Entity Descriptions
Venue: arXiv cs.CL 2021
Year: 2021

Short textual descriptions of entities provide summaries of their key attributes and have been shown to be useful sources of background knowledge for tasks such as entity linking and question answering. However, generating entity descriptions, especially for new and long-tail entities, can be challenging since relevant information is often scattered across multiple sources with varied content and style. We introduce DESCGEN: given mentions spread over multiple documents, the goal is to generate an entity summary description. DESCGEN consists of 37K entity descriptions from Wikipedia and Fandom, each paired with nine evidence documents on average. The documents were collected using a combination of entity linking and hyperlinks to the Wikipedia and Fandom entity pages, which together provide high-quality distant supervision. The resulting summaries are more abstractive than those found in existing datasets and provide a better proxy for the challenge of describing new and emerging entities. We also propose a two-stage extract-then-generate baseline and show that there exists a large gap (19.9% in ROUGE-L) between state-of-the-art models and human performance, suggesting that the data will support significant future work.