OpenRaiser/Intern-Atlas huggingface dataset:
Learning User Preferences in Non-Stationary Environments
Venue: arXiv cs.LG 2021
Year: 2021

Recommendation systems often use online collaborative filtering (CF) algorithms to identify items a given user likes over time, based on ratings that this user and a large number of other users have provided in the past. This problem has been studied extensively when users' preferences do not change over time (static case); an assumption that is often violated in practical settings. In this paper, we introduce a novel model for online non-stationary recommendation systems which allows for temporal uncertainties in the users' preferences. For this model, we propose a user-based CF algorithm, and provide a theoretical analysis of its achievable reward. Compared to related non-stationary multi-armed bandit literature, the main fundamental difficulty in our model lies in the fact that variations in the preferences of a certain user may affect the recommendations for other users severely. We also test our algorithm over real-world datasets, showing its effectiveness in real-world applications. One of the main surprising observations in our experiments is the fact our algorithm outperforms other static algorithms even when preferences do not change over time. This hints toward the general conclusion that in practice, dynamic algorithms, such as the one we propose, might be beneficial even in stationary environments.
Probabilistic Inference of Winners in Elections by Independent Random Voters
Venue: arXiv cs.GT 2021
Year: 2021

We investigate the problem of computing the probability of winning in an election where voter attendance is uncertain. More precisely, we study the setting where, in addition to a total ordering of the candidates, each voter is associated with a probability of attending the poll, and the attendances of different voters are probabilistically independent. We show that the probability of winning can be computed in polynomial time for the plurality and veto rules. However, it is computationally hard (#P-hard) for various other rules, including $k$-approval and $k$-veto for $k>1$, Borda, Condorcet, and Maximin. For some of these rules, it is even hard to find a multiplicative approximation since it is already hard to determine whether this probability is nonzero. In contrast, we devise a fully polynomial-time randomized approximation scheme (FPRAS) for the complement probability, namely the probability of losing, for every positional scoring rule (with polynomial scores), as well as for the Condorcet rule.
The iterated local transitivity model for hypergraphs
Venue: arXiv cs.DM 2021
Year: 2021

Complex networks are pervasive in the real world, capturing dyadic interactions between pairs of vertices, and a large corpus has emerged on their mining and modeling. However, many phenomena are comprised of polyadic interactions between more than two vertices. Such complex hypergraphs range from emails among groups of individuals, scholarly collaboration, or joint interactions of proteins in living cells. A key generative principle within social and other complex networks is transitivity, where friends of friends are more likely friends. The previously proposed Iterated Local Transitivity (ILT) model incorporated transitivity as an evolutionary mechanism. The ILT model provably satisfies many observed properties of social networks, such as densification, low average distances, and high clustering coefficients. We propose a new, generative model for complex hypergraphs based on transitivity, called the Iterated Local Transitivity Hypergraph (or ILTH) model. In ILTH, we iteratively apply the principle of transitivity to form new hypergraphs. The resulting model generates hypergraphs simulating properties observed in real-world complex hypergraphs, such as densification and low average distances. We consider properties unique to hypergraphs not captured by their 2-section. We show that certain motifs, which are specified subhypergraphs of small order, have faster growth rates in ILTH hypergraphs than in random hypergraphs with the same order and expected average degree. We show that the graphs admitting a homomorphism into the 2-section of the initial hypergraph appear as induced subgraphs in the 2-section of ILTH hypergraphs. We consider new and existing hypergraph clustering coefficients, and show that these coefficients have larger values in ILTH hypergraphs than in comparable random hypergraphs.
Applying Bayesian Analysis Guidelines to Empirical Software Engineering Data: The Case of Programming Languages and Code Quality
Venue: arXiv cs.SE 2021
Year: 2021

Statistical analysis is the tool of choice to turn data into information, and then information into empirical knowledge. To be valid, the process that goes from data to knowledge should be supported by detailed, rigorous guidelines, which help ferret out issues with the data or model, and lead to qualified results that strike a reasonable balance between generality and practical relevance. Such guidelines are being developed by statisticians to support the latest techniques for Bayesian data analysis. In this article, we frame these guidelines in a way that is apt to empirical research in software engineering. To demonstrate the guidelines in practice, we apply them to reanalyze a GitHub dataset about code quality in different programming languages. The dataset's original analysis (Ray et al., 2014) and a critical reanalysis (Berger at al., 2019) have attracted considerable attention -- in no small part because they target a topic (the impact of different programming languages) on which strong opinions abound. The goals of our reanalysis are largely orthogonal to this previous work, as we are concerned with demonstrating, on data in an interesting domain, how to build a principled Bayesian data analysis and to showcase some of its benefits. In the process, we will also shed light on some critical aspects of the analyzed data and of the relationship between programming languages and code quality. The high-level conclusions of our exercise will be that Bayesian statistical techniques can be applied to analyze software engineering data in a way that is principled, flexible, and leads to convincing results that inform the state of the art while highlighting the boundaries of its validity. The guidelines can support building solid statistical analyses and connecting their results, and hence help buttress continued progress in empirical software engineering research.
Polynomial Trajectory Predictions for Improved Learning Performance
Venue: arXiv cs.CV 2021
Year: 2021

The rising demand for Active Safety systems in automotive applications stresses the need for a reliable short to mid-term trajectory prediction. Anticipating the unfolding path of road users, one can act to increase the overall safety. In this work, we propose to train artificial neural networks for movement understanding by predicting trajectories in their natural form, as a function of time. Predicting polynomial coefficients allows us to increased accuracy and improve generalisation.
CD2CR: Co-reference Resolution Across Documents and Domains
Venue: arXiv cs.CL 2021
Year: 2021

Cross-document co-reference resolution (CDCR) is the task of identifying and linking mentions to entities and concepts across many text documents. Current state-of-the-art models for this task assume that all documents are of the same type (e.g. news articles) or fall under the same theme. However, it is also desirable to perform CDCR across different domains (type or theme). A particular use case we focus on in this paper is the resolution of entities mentioned across scientific work and newspaper articles that discuss them. Identifying the same entities and corresponding concepts in both scientific articles and news can help scientists understand how their work is represented in mainstream media. We propose a new task and English language dataset for cross-document cross-domain co-reference resolution (CD$^2$CR). The task aims to identify links between entities across heterogeneous document types. We show that in this cross-domain, cross-document setting, existing CDCR models do not perform well and we provide a baseline model that outperforms current state-of-the-art CDCR models on CD$^2$CR. Our data set, annotation tool and guidelines as well as our model for cross-document cross-domain co-reference are all supplied as open access open source resources.
Optimizing $αμ$
Venue: arXiv cs.AI 2021
Year: 2021

$αμ$ is a search algorithm which repairs two defaults of Perfect Information Monte Carlo search: strategy fusion and non locality. In this paper we optimize $αμ$ for the game of Bridge, avoiding useless computations. The proposed optimizations are general and apply to other imperfect information turn-based games. We define multiple optimizations involving Pareto fronts, and show that these optimizations speed up the search. Some of these optimizations are cuts that stop the search at a node, while others keep track of which possible worlds have become redundant, avoiding unnecessary, costly evaluations. We also measure the benefits of parallelizing the double dummy searches at the leaves of the $αμ$ search tree.
A new communication paradigm: from bit accuracy to semantic fidelity
Venue: arXiv cs.NI 2021
Year: 2021

Wireless communication has achieved great success in the past several decades. The challenge is of improving bandwidth with limited spectrum and power consumption, which however has gradually become a bottleneck with evolution going on. The intrinsic problem is that communication is modeled as a message transportation from sender to receiver and pursues for an exact message replication in Shannon's information theory, which certainly leads to large bandwidth and power requirements with data explosion. However, the goal for communication among intelligent agents, entities with intelligence including humans, is to understand the meaning or semantics underlying data, not an accurate recovery of the transmitted messages. The separate first transmission and then understanding is a waste on bandwidth. In this article, we deploy semantics to solve the spectrum and power bottleneck and propose a first understanding and then transmission framework with high semantic fidelity. We first give a brief introduction of semantics covering the definition and properties to show the insights and scope of this paper. Then the proposed communication towards semantic fidelity framework is introduced, which takes the above mentioned properties into account to further improve efficiency. Specially, a semantic transformation is introduced to transform the input into semantic symbols. Different from the conventional transformations in signal processing area, for example discrete cosine transform, the transformation is with data loss, which is also the reason that the proposed framework can achieve large bandwidth saving with high semantic fidelity. Besides, we also discuss semantic noise and performance measurement. To evaluate the effectiveness, a case study of audio transmission is carried out. Finally, we discuss the typical applications and open challenges.
DOA Estimation for Transmit Beamspace MIMO Radar via Tensor Decomposition with Vandermonde Factor Matrix
Venue: arXiv cs.IT 2021
Year: 2021

We address the problem of tensor decomposition in application to direction-of-arrival (DOA) estimation for transmit beamspace (TB) multiple-input multiple-output (MIMO) radar. A general 4-order tensor model that enables computationally efficient DOA estimation is designed. Whereas other tensor decomposition-based methods treat all factor matrices as arbitrary, the essence of the proposed DOA estimation method is to fully exploit the Vandermonde structure of the factor matrices to take advantage of the shift-invariance between and within different subarrays. Specifically, the received signal of TB MIMO radar is expressed as a 4-order tensor. Depending on the target Doppler shifts, the constructed tensor is reshaped into two distinct 3-order tensors. A computationally efficient tensor decomposition method is proposed to decompose the Vandermonde factor matrices. The generators of the Vandermonde factor matrices are computed to estimate the phase rotations between subarrays, which can be utilized as a look-up table for finding target DOA. It is further shown that our proposed method can be used in a more general scenario where the subarray structures can be arbitrary but identical. The proposed DOA estimation method requires no prior information about the tensor rank and is guaranteed to achieve precise decomposition result. Simulation results illustrate the performance improvement of the proposed DOA estimation method as compared to conventional DOA estimation techniques for TB MIMO Radar.
On the weight distribution of the cosets of MDS codes
Venue: arXiv cs.IT 2021
Year: 2021

The weight distribution of the cosets of maximum distance separable (MDS) codes is considered. In 1990, P.G. Bonneau proposed a relation to obtain the full weight distribution of a coset of an MDS code with minimum distance $d$ using the known numbers of vectors of weights $\le d-2$ in this coset. In this paper, the Bonneau formula is transformed into a more structured and convenient form. The new version of the formula allows to consider effectively cosets of distinct weights $W$. (The weight $W$ of a coset is the smallest Hamming weight of any vector in the coset.) For each of the considered $W$ or regions of $W$, special relations more simple than the general ones are obtained. For the MDS code cosets of weight $W=1$ and weight $W=d-1$ we obtain formulas of the weight distributions depending only on the code parameters. This proves that all the cosets of weight $W=1$ (as well as $W=d-1$) have the same weight distribution. The cosets of weight $W=2$ or $W=d-2$ may have different weight distributions; in this case, we proved that the distributions are symmetrical in some sense. The weight distributions of the cosets of MDS codes corresponding to arcs in the projective plane $\mathrm{PG}(2,q)$ are also considered. For MDS codes of covering radius $R=d-1$ we obtain the number of the weight $W=d-1$ cosets and their weight distribution that gives rise to a certain classification of the so-called deep holes. We show that any MDS code of covering radius $R=d-1$ is an almost perfect multiple covering of the farthest-off points (deep holes); moreover, it corresponds to an optimal multiple saturating set in the projective space $\mathrm{PG}(N,q)$.
State of the Art: Content-based and Hybrid Phishing Detection
Venue: arXiv cs.CR 2021
Year: 2021

Phishing attacks have evolved and increased over time and, for this reason, the task of distinguishing between a legitimate site and a phishing site is more and more difficult, fooling even the most expert users. The main proposals focused on addressing this problem can be divided into four approaches: List-based, URL based, content-based, and hybrid. In this state of the art, the most recent techniques using web content-based and hybrid approaches for Phishing Detection are reviewed and compared.
Sequential prediction under log-loss and misspecification
Venue: arXiv cs.LG 2021
Year: 2021

We consider the question of sequential prediction under the log-loss in terms of cumulative regret. Namely, given a hypothesis class of distributions, learner sequentially predicts the (distribution of the) next letter in sequence and its performance is compared to the baseline of the best constant predictor from the hypothesis class. The well-specified case corresponds to an additional assumption that the data-generating distribution belongs to the hypothesis class as well. Here we present results in the more general misspecified case. Due to special properties of the log-loss, the same problem arises in the context of competitive-optimality in density estimation, and model selection. For the $d$-dimensional Gaussian location hypothesis class, we show that cumulative regrets in the well-specified and misspecified cases asymptotically coincide. In other words, we provide an $o(1)$ characterization of the distribution-free (or PAC) regret in this case -- the first such result as far as we know. We recall that the worst-case (or individual-sequence) regret in this case is larger by an additive constant ${d\over 2} + o(1)$. Surprisingly, neither the traditional Bayesian estimators, nor the Shtarkov's normalized maximum likelihood achieve the PAC regret and our estimator requires special "robustification" against heavy-tailed data. In addition, we show two general results for misspecified regret: the existence and uniqueness of the optimal estimator, and the bound sandwiching the misspecified regret between well-specified regrets with (asymptotically) close hypotheses classes.
Neural 3D Clothes Retargeting from a Single Image
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we present a method of clothes retargeting; generating the potential poses and deformations of a given 3D clothing template model to fit onto a person in a single RGB image. The problem is fundamentally ill-posed as attaining the ground truth data is impossible, i.e., images of people wearing the different 3D clothing template model at exact same pose. We address this challenge by utilizing large-scale synthetic data generated from physical simulation, allowing us to map 2D dense body pose to 3D clothing deformation. With the simulated data, we propose a semi-supervised learning framework that validates the physical plausibility of the 3D deformation by matching with the prescribed body-to-cloth contact points and clothing silhouette to fit onto the unlabeled real images. A new neural clothes retargeting network (CRNet) is designed to integrate the semi-supervised retargeting task in an end-to-end fashion. In our evaluation, we show that our method can predict the realistic 3D pose and deformation field needed for retargeting clothes models in real-world examples.
Belief function-based semi-supervised learning for brain tumor segmentation
Venue: arXiv cs.CV 2021
Year: 2021

Precise segmentation of a lesion area is important for optimizing its treatment. Deep learning makes it possible to detect and segment a lesion field using annotated data. However, obtaining precisely annotated data is very challenging in the medical domain. Moreover, labeling uncertainty and imprecision make segmentation results unreliable. In this paper, we address the uncertain boundary problem by a new evidential neural network with an information fusion strategy, and the scarcity of annotated data by semi-supervised learning. Experimental results show that our proposal has better performance than state-of-the-art methods.
Latent-Space Inpainting for Packet Loss Concealment in Collaborative Object Detection
Venue: arXiv cs.CV 2021
Year: 2021

Edge devices, such as cameras and mobile units, are increasingly capable of performing sophisticated computation in addition to their traditional roles in sensing and communicating signals. The focus of this paper is on collaborative object detection, where deep features computed on the edge device from input images are transmitted to the cloud for further processing. We consider the impact of packet loss on the transmitted features and examine several ways for recovering the missing data. In particular, through theory and experiments, we show that methods for image inpainting based on partial differential equations work well for the recovery of missing features in the latent space. The obtained results represent the new state of the art for missing data recovery in collaborative object detection.
Monitoring the Impacts of a Tailings Dam Failure Using Satellite Images
Venue: arXiv cs.CV 2021
Year: 2021

Monitoring dam failures using satellite images provides first responders with efficient management of early interventions. It is also equally important to monitor spatial and temporal changes in the inundation area to track the post-disaster recovery. On January 25th, 2019, the tailings dam of the Córrego do Feijão iron ore mine, located in Brumadinho, Brazil, collapsed. This disaster caused more than 230 fatalities and 30 missing people leading to damage on the order of multiple billions of dollars. This study uses Sentinel-2 satellite images to map the inundation area and assess and delineate the land use and land cover impacted by the dam failure. The images correspond to data captures from January 22nd (3 days before), and February 02 (7 days after the collapse). Satellite images of the region were classified for before and aftermath of the disaster implementing a machine learning algorithm. In order to have sufficient land cover types to validate the quality and accuracy of the algorithm, 7 classes were defined: mine, forest, build-up, river, agricultural, clear water, and grassland. The developed classification algorithm yielded a high accuracy (99%) for the image before the collapse. This paper determines land cover impact using two different models, 1) by using the trained network in the "after" image, and 2) by creating a second network, trained in a subset of points of the "after" image, and then comparing the land cover results of the two trained networks. In the first model, applying the trained network to the "after" image, the accuracy is still high (86%), but lower than using the second model (98%). This strategy can be applied at a low cost for monitoring and assessment by using openly available satellite information and, in case of dam collapse or with a larger budget, higher resolution and faster data can be obtained by fly-overs on the area of concern.
Taxonomic survey of Hindi Language NLP systems
Venue: arXiv cs.CL 2021
Year: 2021

Natural Language processing (NLP) represents the task of automatic handling of natural human language by machines.There is large spectrum of possible applications of NLP which help in automating tasks like translating text from one language to other, retrieving and summarizing data from very huge repositories, spam email filtering, identifying fake news in digital media, find sentiment and feedback of people, find political opinions and views of people on various government policies, provide effective medical assistance based on past history records of patient etc. Hindi is the official language of India with nearly 691 million users in India and 366 million in rest of world. At present, a number of government and private sector projects and researchers in India and abroad, are working towards developing NLP applications and resources for Indian languages. This survey gives a report of the resources and applications available for Hindi language NLP.
EdgeWorkflowReal: An Edge Computing based Workflow Execution Engine for Smart Systems
Venue: arXiv cs.SE 2021
Year: 2021

Current cloud-based smart systems suffer from weaknesses such as high response latency, limited network bandwidth and the restricted computing power of smart end devices which seriously affect the system's QoS (Quality of Service). Recently, given its advantages of low latency, high bandwidth and location awareness, edge computing has become a promising solution for smart systems. However, the development of edge computing based smart systems is a very challenging job for software developers who do not have the skills for the creation of edge computing environments. The management of edge computing resources and computing tasks is also very challenging. Workflow technology has been widely used in smart systems to automate task and resource management, but there does not yet exist a real-world deployable edge computing based workflow execution engine. To fill this gap, we present EdgeWorkflowReal, an edge computing based workflow execution engine for smart systems. EdgeWorkflowReal supports: 1) automatic creation of a real edge computing environment according to user settings; 2) visualized modelling of edge workflow applications; and 3) automatic deployment, monitoring and performance evaluation of edge workflow applications in a smart system.