OpenRaiser/Intern-Atlas huggingface dataset:
Greedy Approaches to Online Stochastic Matching
Venue: arXiv cs.DS 2021
Year: 2021

Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one-sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching (if possible). We consider the competitiveness of online algorithms in both the adversarial order model (AOM) and the random order model (ROM). More specifically, we consider a bipartite stochastic graph $G = (U,V,E)$ where $U$ is the set of offline vertices, $V$ is the set of online vertices and $G$ has edge probabilities $(p_{e})_{e \in E}$ and edge weights $(w_{e})_{e \in E}$. Additionally, $G$ has probing constraints $(\scr{C}_{v})_{v \in V}$, where $\scr{C}_v$ indicates which sequences of edges adjacent to an online vertex $v$ can be probed. We assume that $U$ is known in advance, and that $\scr{C}_v$, together with the edge probabilities and weights adjacent to an online vertex are only revealed when the online vertex arrives. This model generalizes the various settings of the classical bipartite matching problem, and so our main contribution is in making progress towards understanding which classical results extend to the stochastic probing model.
Revisiting Process versus Product Metrics: a Large Scale Analysis
Venue: arXiv cs.SE 2021
Year: 2021

Numerous methods can build predictive models from software data. However, what methods and conclusions should we endorse as we move from analytics in-the-small (dealing with a handful of projects) to analytics in-the-large (dealing with hundreds of projects)? To answer this question, we recheck prior small-scale results (about process versus product metrics for defect prediction and the granularity of metrics) using 722,471 commits from 700 Github projects. We find that some analytics in-the-small conclusions still hold when scaling up to analytics in-the-large. For example, like prior work, we see that process metrics are better predictors for defects than product metrics (best process/product-based learners respectively achieve recalls of 98\%/44\% and AUCs of 95\%/54\%, median values). That said, we warn that it is unwise to trust metric importance results from analytics in-the-small studies since those change dramatically when moving to analytics in-the-large. Also, when reasoning in-the-large about hundreds of projects, it is better to use predictions from multiple models (since single model predictions can become confused and exhibit a high variance).
A Efficient Multimodal Framework for Large Scale Emotion Recognition by Fusing Music and Electrodermal Activity Signals
Venue: arXiv cs.SD 2021
Year: 2021

Considerable attention has been paid for physiological signal-based emotion recognition in field of affective computing. For the reliability and user friendly acquisition, Electrodermal Activity (EDA) has great advantage in practical applications. However, the EDA-based emotion recognition with hundreds of subjects still lacks effective solution. In this paper, our work makes an attempt to fuse the subject individual EDA features and the external evoked music features. And we propose an end-to-end multimodal framework, the 1-dimensional residual temporal and channel attention network (RTCAN-1D). For EDA features, the novel convex optimization-based EDA (CvxEDA) method is applied to decompose EDA signals into pahsic and tonic signals for mining the dynamic and steady features. The channel-temporal attention mechanism for EDA-based emotion recognition is firstly involved to improve the temporal- and channel-wise representation. For music features, we process the music signal with the open source toolkit openSMILE to obtain external feature vectors. The individual emotion features from EDA signals and external emotion benchmarks from music are fused in the classifing layers. We have conducted systematic comparisons on three multimodal datasets (PMEmo, DEAP, AMIGOS) for 2-classes valance/arousal emotion recognition. Our proposed RTCAN-1D outperforms the existing state-of-the-art models, which also validate that our work provides an reliable and efficient solution for large scale emotion recognition. Our code has been released at https://github.com/guanghaoyin/RTCAN-1D.
Unsupervised Hyperspectral Mixed Noise Removal Via Spatial-Spectral Constrained Deep Image Prior
Venue: arXiv cs.CV 2021
Year: 2021

Recently, convolutional neural network (CNN)-based methods are proposed for hyperspectral images (HSIs) denoising. Among them, unsupervised methods such as the deep image prior (DIP) have received much attention because these methods do not require any training data. However, DIP suffers from the semi-convergence behavior, i.e., the iteration of DIP needs to terminate by referring to the ground-truth image at the optimal iteration point. In this paper, we propose the spatial-spectral constrained deep image prior (S2DIP) for HSI mixed noise removal. Specifically, we incorporate DIP with a spatial-spectral total variation (SSTV) term to fully preserve the spatial-spectral local smoothness of the HSI and an $\ell_1$-norm term to capture the complex sparse noise. The proposed S2DIP jointly leverages the expressive power brought from the deep CNN without any training data and exploits the HSI and noise structures via hand-crafted priors. Thus, our method avoids the semi-convergence behavior, showing higher stabilities than DIP. Meanwhile, our method largely enhances the HSI denoising ability of DIP. To tackle the proposed denoising model, we develop an alternating direction multiplier method algorithm. Extensive experiments demonstrate that the proposed S2DIP outperforms optimization-based and supervised CNN-based state-of-the-art HSI denoising methods.
DNN2LR: Interpretation-inspired Feature Crossing for Real-world Tabular Data
Venue: arXiv cs.LG 2021
Year: 2021

For sake of reliability, it is necessary for models in real-world applications to be both powerful and globally interpretable. Simple classifiers, e.g., Logistic Regression (LR), are globally interpretable, but not powerful enough to model complex nonlinear interactions among features in tabular data. Meanwhile, Deep Neural Networks (DNNs) have shown great effectiveness for modeling tabular data, but is not globally interpretable. In this work, we find local piece-wise interpretations in DNN of a specific feature are usually inconsistent in different samples, which is caused by feature interactions in the hidden layers. Accordingly, we can design an automatic feature crossing method to find feature interactions in DNN, and use them as cross features in LR. We give definition of the interpretation inconsistency in DNN, based on which a novel feature crossing method called DNN2LR is proposed. Extensive experiments have been conducted on four public datasets and two real-world datasets. The final model, i.e., a LR model empowered with cross features, generated by DNN2LR can outperform the complex DNN model, as well as several state-of-the-art feature crossing methods. The experimental results strongly verify the effectiveness and efficiency of DNN2LR, especially on real-world datasets with large numbers of feature fields.
Improved Weighted Additive Spanners
Venue: arXiv cs.DS 2021
Year: 2021

Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanners, so far little attention was given to weighted graphs. Only very recently [ABSKS20] extended the classical +2 (respectively, +4) spanners for unweighted graphs of size $O(n^{3/2})$ (resp., $O(n^{7/5})$) to the weighted setting, where the additive error is $+2W$ (resp., $+4W$). This means that for every pair $u,v$, the additive stretch is at most $+2W_{u,v}$, where $W_{u,v}$ is the maximal edge weight on the shortest $u-v$ path. In addition, [ABSKS20] showed an algorithm yielding a $+8W_{max}$ spanner of size $O(n^{4/3})$, here $W_{max}$ is the maximum edge weight in the entire graph. In this work we improve the latter result by devising a simple deterministic algorithm for a $+(6+\varepsilon)W$ spanner for weighted graphs with size $O(n^{4/3})$ (for any constant $\varepsilon>0$), thus nearly matching the classical +6 spanner of size $O(n^{4/3})$ for unweighted graphs. Furthermore, we show a $+(2+\varepsilon)W$ subsetwise spanner of size $O(n\cdot\sqrt{|S|})$, improving the $+4W_{max}$ result of [ABSKS20] (that had the same size). We also show a simple randomized algorithm for a $+4W$ emulator of size $\tilde{O}(n^{4/3})$. In addition, we show that our technique is applicable for very sparse additive spanners, that have linear size. For weighted graphs, we use a variant of our simple deterministic algorithm that yields a linear size $+\tilde{O}(\sqrt{n}\cdot W)$ spanner, and we also obtain a tradeoff between size and stretch. Finally, generalizing the technique of [DHZ00] for unweighted graphs, we devise an efficient randomized algorithm producing a $+2W$ spanner for weighted graphs of size $\tilde{O}(n^{3/2})$ in $\tilde{O}(n^2)$ time.
A Review of Critical Features and General Issues of Freely Available mHealth Apps For Dietary Assessment
Venue: arXiv cs.CY 2021
Year: 2021

Obesity is known to lower the quality of life substantially. It is often associated with increased chances of non-communicable diseases such as diabetes, cardiovascular problems, various cancers, etc. Evidence suggests that diet-related mobile applications play a vital role in assisting individuals in making healthier choices and keeping track of food intake. However, due to an abundance of similar applications, it becomes pertinent to evaluate each of them in terms of functionality, usability, and possible design issues to truly determine state-of-the-art solutions for the future. Since these applications involve implementing multiple user requirements and recommendations from different dietitians, the evaluation becomes quite complex. Therefore, this study aims to review existing dietary applications at length to highlight key features and problems that enhance or undermine an application's usability. For this purpose, we have examined the published literature from various scientific databases of the PUBMED, CINAHL (January 2010-December 2019) and Science Direct (2010-2019). We followed PRISMA guidelines, and out of our findings, fifty-six primary studies met our inclusion criteria after identification, screening, eligibility and full-text evaluation. We analyzed 35 apps from the selected studies and extracted the data of each of the identified apps.Following our detailed analysis on the comprehensiveness of freely available mHealth applications, we specified potential future research challenges and stated recommendations to help grow clinically accurate diet-related applications.
Reimagining City Configuration: Automated Urban Planning via Adversarial Learning
Venue: arXiv cs.AI 2021
Year: 2021

Urban planning refers to the efforts of designing land-use configurations. Effective urban planning can help to mitigate the operational and social vulnerability of a urban system, such as high tax, crimes, traffic congestion and accidents, pollution, depression, and anxiety. Due to the high complexity of urban systems, such tasks are mostly completed by professional planners. But, human planners take longer time. The recent advance of deep learning motivates us to ask: can machines learn at a human capability to automatically and quickly calculate land-use configuration, so human planners can finally adjust machine-generated plans for specific needs? To this end, we formulate the automated urban planning problem into a task of learning to configure land-uses, given the surrounding spatial contexts. To set up the task, we define a land-use configuration as a longitude-latitude-channel tensor, where each channel is a category of POIs and the value of an entry is the number of POIs. The objective is then to propose an adversarial learning framework that can automatically generate such tensor for an unplanned area. In particular, we first characterize the contexts of surrounding areas of an unplanned area by learning representations from spatial graphs using geographic and human mobility data. Second, we combine each unplanned area and its surrounding context representation as a tuple, and categorize all the tuples into positive (well-planned areas) and negative samples (poorly-planned areas). Third, we develop an adversarial land-use configuration approach, where the surrounding context representation is fed into a generator to generate a land-use configuration, and a discriminator learns to distinguish among positive and negative samples.
Contrastive learning, multi-view redundancy, and linear models
Venue: arXiv cs.LG 2021
Year: 2021

Self-supervised learning is an empirically successful approach to unsupervised learning based on creating artificial supervised learning problems. A popular self-supervised approach to representation learning is contrastive learning, which leverages naturally occurring pairs of similar and dissimilar data points, or multiple views of the same data. This work provides a theoretical analysis of contrastive learning in the multi-view setting, where two views of each datum are available. The main result is that linear functions of the learned representations are nearly optimal on downstream prediction tasks whenever the two views provide redundant information about the label.
Deep Q-Learning: Theoretical Insights from an Asymptotic Analysis
Venue: arXiv cs.LG 2021
Year: 2021

Deep Q-Learning is an important reinforcement learning algorithm, which involves training a deep neural network, called Deep Q-Network (DQN), to approximate the well-known Q-function. Although wildly successful under laboratory conditions, serious gaps between theory and practice as well as a lack of formal guarantees prevent its use in the real world. Adopting a dynamical systems perspective, we provide a theoretical analysis of a popular version of Deep Q-Learning under realistic and verifiable assumptions. More specifically, we prove an important result on the convergence of the algorithm, characterizing the asymptotic behavior of the learning process. Our result sheds light on hitherto unexplained properties of the algorithm and helps understand empirical observations, such as performance inconsistencies even after training. Unlike previous theories, our analysis accommodates state Markov processes with multiple stationary distributions. In spite of the focus on Deep Q-Learning, we believe that our theory may be applied to understand other deep learning algorithms
Comonadic semantics for guarded fragments
Venue: arXiv cs.LO 2021
Year: 2021

In previous work, Abramsky, Dawar and Wang (LiCS 2017) and Abramsky and Shah (CSL 2018) have shown how a range of model comparison games which play a central role in finite model theory, including Ehrenfeucht-Fraisse, pebbling, and bisimulation games, can be captured in terms of resource-indexed comonads on the category of relational structures. Moreover, the coalgebras for these comonads capture important combinatorial parameters such as tree-width and tree-depth. The present paper extends this analysis to quantifier-guarded fragments of first-order logic. We give a systematic account, covering atomic, loose and clique guards. In each case, we show that coKleisli morphisms capture winning strategies for Duplicator in the existential guarded bisimulation game, while back-and-forth bisimulation, and hence equivalence in the full guarded fragment, is captured by spans of open morphisms. We study the coalgebras for these comonads, and show that they correspond to guarded tree decompositions. We relate these constructions to a syntax-free setting, with a comonad on the category of hypergraphs.
A Tale of Two Cities: Software Developers Working from Home During the COVID-19 Pandemic
Venue: arXiv cs.SE 2021
Year: 2021

The COVID-19 pandemic has shaken the world to its core and has provoked an overnight exodus of developers that normally worked in an office setting to working from home. The magnitude of this shift and the factors that have accompanied this new unplanned work setting go beyond what the software engineering community has previously understood to be remote work. To find out how developers and their productivity were affected, we distributed two surveys (with a combined total of 3,634 responses that answered all required questions) -- weeks apart to understand the presence and prevalence of the benefits, challenges, and opportunities to improve this special circumstance of remote work. From our thematic qualitative analysis and statistical quantitative analysis, we find that there is a dichotomy of developer experiences influenced by many different factors (that for some are a benefit, while for others a challenge). For example, a benefit for some was being close to family members but for others having family members share their working space and interrupting their focus, was a challenge. Our surveys led to powerful narratives from respondents and revealed the scale at which these experiences exist to provide insights as to how the future of (pandemic) remote work can evolve.
Physically Unclonable Functions and AI: Two Decades of Marriage
Venue: arXiv cs.CR 2021
Year: 2021

The current chapter aims at establishing a relationship between artificial intelligence (AI) and hardware security. Such a connection between AI and software security has been confirmed and well-reviewed in the relevant literature. The main focus here is to explore the methods borrowed from AI to assess the security of a hardware primitive, namely physically unclonable functions (PUFs), which has found applications in cryptographic protocols, e.g., authentication and key generation. Metrics and procedures devised for this are further discussed. Moreover, By reviewing PUFs designed by applying AI techniques, we give insight into future research directions in this area.
FileBounty: Fair Data Exchange
Venue: arXiv cs.CR 2021
Year: 2021

Digital contents are typically sold online through centralized and custodian marketplaces, which requires the trading partners to trust a central entity. We present FileBounty, a fair protocol which, assuming the cryptographic hash of the file of interest is known to the buyer, is trust-free and lets a buyer purchase data for a previously agreed monetary amount, while guaranteeing the integrity of the contents. To prevent misbehavior, FileBounty guarantees that any deviation from the expected participants' behavior results in a negative financial payoff; i.e. we show that honest behavior corresponds to a subgame perfect Nash equilibrium. Our novel deposit refunding scheme is resistant to extortion attacks under rational adversaries. If buyer and seller behave honestly, FileBounty's execution requires only three on-chain transactions, while the actual data is exchanged off-chain in an efficient and privacy-preserving manner. We moreover show how FileBounty enables a flexible peer-to-peer setting where multiple parties fairly sell a file to a buyer.
AMBERT: A Pre-trained Language Model with Multi-Grained Tokenization
Venue: arXiv cs.CL 2021
Year: 2021

Pre-trained language models such as BERT have exhibited remarkable performances in many tasks in natural language understanding (NLU). The tokens in the models are usually fine-grained in the sense that for languages like English they are words or sub-words and for languages like Chinese they are characters. In English, for example, there are multi-word expressions which form natural lexical units and thus the use of coarse-grained tokenization also appears to be reasonable. In fact, both fine-grained and coarse-grained tokenizations have advantages and disadvantages for learning of pre-trained language models. In this paper, we propose a novel pre-trained language model, referred to as AMBERT (A Multi-grained BERT), on the basis of both fine-grained and coarse-grained tokenizations. For English, AMBERT takes both the sequence of words (fine-grained tokens) and the sequence of phrases (coarse-grained tokens) as input after tokenization, employs one encoder for processing the sequence of words and the other encoder for processing the sequence of the phrases, utilizes shared parameters between the two encoders, and finally creates a sequence of contextualized representations of the words and a sequence of contextualized representations of the phrases. Experiments have been conducted on benchmark datasets for Chinese and English, including CLUE, GLUE, SQuAD and RACE. The results show that AMBERT can outperform BERT in all cases, particularly the improvements are significant for Chinese. We also develop a method to improve the efficiency of AMBERT in inference, which still performs better than BERT with the same computational cost as BERT.
Open is not forever: a study of vanished open access journals
Venue: arXiv cs.DL 2021
Year: 2021

The preservation of the scholarly record has been a point of concern since the beginning of knowledge production. With print publications, the responsibility rested primarily with librarians, but the shift toward digital publishing and, in particular, the introduction of open access (OA) have caused ambiguity and complexity. Consequently, the long-term accessibility of journals is not always guaranteed, and they can even disappear from the web completely. The focus of this exploratory study is on the phenomenon of vanished journals, something that has not been carried out before. For the analysis, we consulted several major bibliographic indexes, such as Scopus, Ulrichsweb, and the Directory of Open Access Journals, and traced the journals through the Internet Archive's Wayback Machine. We found 174 OA journals that, through lack of comprehensive and open archives, vanished from the web between 2000 and 2019, spanning all major research disciplines and geographic regions of the world. Our results raise vital concern for the integrity of the scholarly record and highlight the urgency to take collaborative action to ensure continued access and prevent the loss of more scholarly knowledge. We encourage those interested in the phenomenon of vanished journals to use the public dataset for their own research.
Orbit Structure of Grassmannian $G_{2, m}$ and a decoder for Grassmann code $C(2, m)$
Venue: arXiv cs.IT 2021
Year: 2021

In this manuscript, we consider decoding Grassmann codes, linear codes associated to Grassmannian of planes in an affine space. We look at the orbit structure of Grassmannian arising from the natural action of multiplicative group of certain finite field extension. We project the corresponding Grassmann code onto these orbits to obtain a few subcodes of certain Reed-Solomon code. We prove that some of these projected codes contains an information set of the parent Grassmann code. By improving the efficiency of Peterson's decoding algorithm for the projected subcodes, we prove that one can correct up to $\lfloor d-1/2\rfloor$ errors for Grassmann code, where $d$ is the minimum distance of Grassmann code.
Certainty Equivalent Perception-Based Control
Venue: arXiv cs.LG 2021
Year: 2021

In order to certify performance and safety, feedback control requires precise characterization of sensor errors. In this paper, we provide guarantees on such feedback systems when sensors are characterized by solving a supervised learning problem. We show a uniform error bound on nonparametric kernel regression under a dynamically-achievable dense sampling scheme. This allows for a finite-time convergence rate on the sub-optimality of using the regressor in closed-loop for waypoint tracking. We demonstrate our results in simulation with simplified unmanned aerial vehicle and autonomous driving examples.