OpenRaiser/Intern-Atlas huggingface dataset:
Personalization in E-Grocery: Top-N versus Top-k Rankings
Venue: arXiv cs.IR 2021
Year: 2021

Business success in e-commerce depends on customer perceived value. A customer with high perceived value buys, returns, and recommends items. The perceived value is at risk whenever the information load harms users' shopping experience. In e-grocery, shoppers face an overwhelming number of items, the majority of which is irrelevant for the shopper. Recommender systems (RS) enable businesses to master information overload (IO) by providing users with an item ranking by relevance. Prior work proposes RS with short personalized rankings (top-k). Given large order sizes and high user heterogeneity in e-grocery, top-k RS are insufficient to diminish IO in this domain. To fill this gap and raise business performance, this paper introduces an RS with a personalized long ranking (top-N). Undertaking a randomized field experiment, the paper establishes the merit of shifting from top-k to top-N rankings. Specifically, the proposed RS reduces IO by 29.4% and lowers users' search time by 3.3 seconds per item. The field experiment also reveals a 7% uplift in revenue due to the top-N ranking. Substantial benefits for the customer and the company highlight the business value of top-N rankings as a new design requirement for recommender systems in e-grocery.
Identity and Attribute Preserving Thumbnail Upscaling
Venue: arXiv cs.CV 2021
Year: 2021

We consider the task of upscaling a low resolution thumbnail image of a person, to a higher resolution image, which preserves the person's identity and other attributes. Since the thumbnail image is of low resolution, many higher resolution versions exist. Previous approaches produce solutions where the person's identity is not preserved, or biased solutions, such as predominantly Caucasian faces. We address the existing ambiguity by first augmenting the feature extractor to better capture facial identity, facial attributes (such as smiling or not) and race, and second, use this feature extractor to generate high-resolution images which are identity preserving as well as conditioned on race and facial attributes. Our results indicate an improvement in face similarity recognition and lookalike generation as well as in the ability to generate higher resolution images which preserve an input thumbnail identity and whose race and attributes are maintained.
FED-$χ^2$: Privacy Preserving Federated Correlation Test
Venue: arXiv cs.CR 2021
Year: 2021

In this paper, we propose the first secure federated $χ^2$-test protocol Fed-$χ^2$. To minimize both the privacy leakage and the communication cost, we recast $χ^2$-test to the second moment estimation problem and thus can take advantage of stable projection to encode the local information in a short vector. As such encodings can be aggregated with only summation, secure aggregation can be naturally applied to hide the individual updates. We formally prove the security guarantee of Fed-$χ^2$ that the joint distribution is hidden in a subspace with exponential possible distributions. Our evaluation results show that Fed-$χ^2$ achieves negligible accuracy drops with small client-side computation overhead. In several real-world case studies, the performance of Fed-$χ^2$ is comparable to the centralized $χ^2$-test.
$\ell_2$-norm Flow Diffusion in Near-Linear Time
Venue: arXiv cs.DS 2021
Year: 2021

Diffusion is a fundamental graph procedure and has been a basic building block in a wide range of theoretical and empirical applications such as graph partitioning and semi-supervised learning on graphs. In this paper, we study computationally efficient diffusion primitives beyond random walk. We design an $\widetilde{O}(m)$-time randomized algorithm for the $\ell_2$-norm flow diffusion problem, a recently proposed diffusion model based on network flow with demonstrated graph clustering related applications both in theory and in practice. Examples include finding locally-biased low conductance cuts. Using a known connection between the optimal dual solution of the flow diffusion problem and the local cut structure, our algorithm gives an alternative approach for finding such cuts in nearly linear time. From a technical point of view, our algorithm contributes a novel way of dealing with inequality constraints in graph optimization problems. It adapts the high-level algorithmic framework of nearly linear time Laplacian system solvers, but requires several new tools: vertex elimination under constraints, a new family of graph ultra-sparsifiers, and accelerated proximal gradient methods with inexact proximal mapping computation.
Organizational Artifacts of Code Development
Venue: arXiv cs.CY 2021
Year: 2021

Software is the outcome of active and effective communication between members of an organization. This has been noted with Conway's law, which states that ``organizations design systems that mirror their own communication structure.'' However, software developers are often members of multiple organizational groups (e.g., corporate, regional,) and it is unclear how association with groups beyond one's company influence the development process. In this paper, we study social effects of country by measuring differences in software repositories associated with different countries. Using a novel dataset we obtain from GitHub, we identify key properties that differentiate software repositories based upon the country of the developers. We propose a novel approach of modeling repositories based on their sequence of development activities as a sequence embedding task and coupled with repo profile features we achieve 79.2% accuracy in identifying the country of a repository. Finally, we conduct a case study on repos from well-known corporations and find that country can describe the differences in development better than the company affiliation itself. These results have larger implications for software development and indicate the importance of considering the multiple groups developers are associated with when considering the formation and structure of teams.
On the Secrecy Rate under Statistical QoS Provisioning for RIS-Assisted MISO Wiretap Channel
Venue: arXiv cs.IT 2021
Year: 2021

Reconfigurable intelligent surface (RIS) assisted radio is considered as an enabling technology with great potential for the sixth-generation (6G) wireless communications standard. The achievable secrecy rate (ASR) is one of the most fundamental metrics to evaluate the capability of facilitating secure communication for RIS-assisted systems. However, the definition of ASR is based on Shannon's information theory, which generally requires long codewords and thus fails to quantify the secrecy of emerging delay-critical services. Motivated by this, in this paper we investigate the problem of maximizing the secrecy rate under a delay-limited quality-of-service (QoS) constraint, termed as the effective secrecy rate (ESR), for an RIS-assisted multiple-input single-output (MISO) wiretap channel subject to a transmit power constraint. We propose an iterative method to find a stationary solution to the formulated non-convex optimization problem using a block coordinate ascent method (BCAM), where both the beamforming vector at the transmitter as well as the phase shifts at the RIS are obtained in closed forms in each iteration. We also present a convergence proof, an efficient implementation, and the associated complexity analysis for the proposed method. Our numerical results demonstrate that the proposed optimization algorithm converges significantly faster that an existing solution. The simulation results also confirm that the secrecy rate performance of the system with stringent delay requirements reduce significantly compared to the system without any delay constraints, and that this reduction can be significantly mitigated by an appropriately placed large-size RIS.
Sharper bounds for online learning of smooth functions of a single variable
Venue: arXiv cs.LG 2021
Year: 2021

We investigate the generalization of the mistake-bound model to continuous real-valued single variable functions. Let $\mathcal{F}_q$ be the class of absolutely continuous functions $f: [0, 1] \rightarrow \mathbb{R}$ with $||f'||_q \le 1$, and define $opt_p(\mathcal{F}_q)$ as the best possible bound on the worst-case sum of the $p^{th}$ powers of the absolute prediction errors over any number of trials. Kimber and Long (Theoretical Computer Science, 1995) proved for $q \ge 2$ that $opt_p(\mathcal{F}_q) = 1$ when $p \ge 2$ and $opt_p(\mathcal{F}_q) = \infty$ when $p = 1$. For $1 < p < 2$ with $p = 1+ε$, the only known bound was $opt_p(\mathcal{F}_{q}) = O(ε^{-1})$ from the same paper. We show for all $ε\in (0, 1)$ and $q \ge 2$ that $opt_{1+ε}(\mathcal{F}_q) = Θ(ε^{-\frac{1}{2}})$, where the constants in the bound do not depend on $q$. We also show that $opt_{1+ε}(\mathcal{F}_{\infty}) = Θ(ε^{-\frac{1}{2}})$.
EchoFilter: End-to-End Neural Network for Acoustic Echo Cancellation
Venue: arXiv cs.SD 2021
Year: 2021

Acoustic Echo Cancellation (AEC) whose aim is to suppress the echo originated from acoustic coupling between loudspeakers and microphones, plays a key role in voice interaction. Linear adaptive filter (AF) is always used for handling this problem. However, since there would be some severe effects in real scenarios, such nonlinear distortions, background noises, and microphone clipping, it would lead to considerable residual echo, giving poor performance in practice. In this paper, we propose an end-to-end network structure for echo cancellation, which is directly done on time-domain audio waveform. It is transformed to deep representation by temporal convolution, and modelled by Long Short-Term Memory (LSTM) for considering temporal property. Since time delay and severe reverberation may exist at the near-end with respect to the far-end, a local attention is employed for alignment. The network is trained using multitask learning by employing an auxiliary classification network for double-talk detection. Experiments show the superiority of our proposed method in terms of the echo return loss enhancement (ERLE) for single-talk periods and the perceptual evaluation of speech quality (PESQ) score for double-talk periods in background noise and nonlinear distortion scenarios.
Robustifying $\ell_\infty$ Adversarial Training to the Union of Perturbation Models
Venue: arXiv cs.LG 2021
Year: 2021

Classical adversarial training (AT) frameworks are designed to achieve high adversarial accuracy against a single attack type, typically $\ell_\infty$ norm-bounded perturbations. Recent extensions in AT have focused on defending against the union of multiple perturbations but this benefit is obtained at the expense of a significant (up to $10\times$) increase in training complexity over single-attack $\ell_\infty$ AT. In this work, we expand the capabilities of widely popular single-attack $\ell_\infty$ AT frameworks to provide robustness to the union of ($\ell_\infty, \ell_2, \ell_1$) perturbations while preserving their training efficiency. Our technique, referred to as Shaped Noise Augmented Processing (SNAP), exploits a well-established byproduct of single-attack AT frameworks -- the reduction in the curvature of the decision boundary of networks. SNAP prepends a given deep net with a shaped noise augmentation layer whose distribution is learned along with network parameters using any standard single-attack AT. As a result, SNAP enhances adversarial accuracy of ResNet-18 on CIFAR-10 against the union of ($\ell_\infty, \ell_2, \ell_1$) perturbations by 14%-to-20% for four state-of-the-art (SOTA) single-attack $\ell_\infty$ AT frameworks, and, for the first time, establishes a benchmark for ResNet-50 and ResNet-101 on ImageNet.
Diffy: Inductive Reasoning of Array Programs using Difference Invariants
Venue: arXiv cs.PL 2021
Year: 2021

We present a novel verification technique to prove interesting properties of a class of array programs with a symbolic parameter N denoting the size of arrays. The technique relies on constructing two slightly different versions of the same program. It infers difference relations between the corresponding variables at key control points of the joint control-flow graph of the two program versions. The desired post-condition is then proved by inducting on the program parameter $N$, wherein the difference invariants are crucially used in the inductive step. This contrasts with classical techniques that rely on finding potentially complex loop invaraints for each loop in the program. Our synergistic combination of inductive reasoning and finding simple difference invariants helps prove properties of programs that cannot be proved even by the winner of Arrays sub-category from SV-COMP 2021. We have implemented a prototype tool called diffy to demonstrate these ideas. We present results comparing the performance of diffy with that of state-of-the-art tools.
List-decoding and list-recovery of Reed-Solomon codes beyond the Johnson radius for any rate
Venue: arXiv cs.IT 2021
Year: 2021

Understanding the limits of list-decoding and list-recovery of Reed-Solomon (RS) codes is of prime interest in coding theory and has attracted a lot of attention in recent decades. However, the best possible parameters for these problems are still unknown, and in this paper, we take a step in this direction. We show the existence of RS codes that are list-decodable or list-recoverable beyond the Johnson radius for \emph{any} rate, with a polynomial field size in the block length. In particular, we show that for any $ε\in (0,1)$ there exist RS codes that are list-decodable from radius $1-ε$ and rate less than $\fracε{2-ε}$, with constant list size. We deduce our results by extending and strengthening a recent result of Ferber, Kwan, and Sauermann on puncturing codes with large minimum distance and by utilizing the underlying code's linearity.
Bimanual Shelf Picking Planner Based on Collapse Prediction
Venue: arXiv cs.RO 2021
Year: 2021

In logistics warehouse, since many objects are randomly stacked on shelves, it becomes difficult for a robot to safely extract one of the objects without other objects falling from the shelf. In previous works, a robot needed to extract the target object after rearranging the neighboring objects. In contrast, humans extract an object from a shelf while supporting other neighboring objects. In this paper, we propose a bimanual manipulation planner based on collapse prediction trained with data generated from a physics simulator, which can safely extract a single object while supporting the other object. We confirmed that the proposed method achieves more than 80% success rate for safe extraction by real-world experiments using a dual-arm manipulator.
Procedural Content Generation: Better Benchmarks for Transfer Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

The idea of transfer in reinforcement learning (TRL) is intriguing: being able to transfer knowledge from one problem to another problem without learning everything from scratch. This promises quicker learning and learning more complex methods. To gain an insight into the field and to detect emerging trends, we performed a database search. We note a surprisingly late adoption of deep learning that starts in 2018. The introduction of deep learning has not yet solved the greatest challenge of TRL: generalization. Transfer between different domains works well when domains have strong similarities (e.g. MountainCar to Cartpole), and most TRL publications focus on different tasks within the same domain that have few differences. Most TRL applications we encountered compare their improvements against self-defined baselines, and the field is still missing unified benchmarks. We consider this to be a disappointing situation. For the future, we note that: (1) A clear measure of task similarity is needed. (2) Generalization needs to improve. Promising approaches merge deep learning with planning via MCTS or introduce memory through LSTMs. (3) The lack of benchmarking tools will be remedied to enable meaningful comparison and measure progress. Already Alchemy and Meta-World are emerging as interesting benchmark suites. We note that another development, the increase in procedural content generation (PCG), can improve both benchmarking and generalization in TRL.
Electryo, In-person Voting with Transparent Voter Verifiability and Eligibility Verifiability
Venue: arXiv cs.CR 2021
Year: 2021

Selene is an e-voting protocol that allows voters to directly check their individual vote, in cleartext, in the final tally via a tracker system, while providing good coercion mitigation. This is in contrast to conventional, end-to-end verifiable schemes in which the voter verifies the presence of an encryption of her vote on the bulletin board. The Selene mechanism can be applied to many e-voting schemes, but here we present an application to the polling station context, resulting in a voter-verifiable electronic tally with a paper audit trail. The system uses a smartcard-based public key system to provide the individual verification and universal eligibility verifiability. The paper record contains an encrypted link to the voter's identity, requiring stronger assumptions on ballot privacy than normal paper voting, but with the benefit of providing good auditability and dispute resolution as well as supporting (comparison) risk limiting audits.
Gradient-based Data Subversion Attack Against Binary Classifiers
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning based data-driven technologies have shown impressive performances in a variety of application domains. Most enterprises use data from multiple sources to provide quality applications. The reliability of the external data sources raises concerns for the security of the machine learning techniques adopted. An attacker can tamper the training or test datasets to subvert the predictions of models generated by these techniques. Data poisoning is one such attack wherein the attacker tries to degrade the performance of a classifier by manipulating the training data. In this work, we focus on label contamination attack in which an attacker poisons the labels of data to compromise the functionality of the system. We develop Gradient-based Data Subversion strategies to achieve model degradation under the assumption that the attacker has limited-knowledge of the victim model. We exploit the gradients of a differentiable convex loss function (residual errors) with respect to the predicted label as a warm-start and formulate different strategies to find a set of data instances to contaminate. Further, we analyze the transferability of attacks and the susceptibility of binary classifiers. Our experiments show that the proposed approach outperforms the baselines and is computationally efficient.
SQUADfps: Integrated Model-Based Machine Safety and Product Quality for Flexible Production Systems
Venue: arXiv cs.OH 2021
Year: 2021

Growing individualization of products up to lot-size-1 and high volatility of product mixes lead to new challenges in the manufacturing domain, including the need for frequent reconfiguration of the system and reacting to changing orders. Thus, apart from functional aspects, safety aspects of the production system as well as product quality assurance aspects must be addressed for flexible and reconfigurable manufacturing systems at runtime. To cope with the mentioned challenges, we present an integrated model-based approach SQUADfps (machine Safety and product QUAlity for flexible proDuction systems) to support the automatic conduct of the risk assessment of flexible production scenarios in terms of safety as well as the process-FMEA to ensure that the requirements w.r.t. the quality of the production process and the resulting product are met. Our approach is based on a meta-model which captures all information needed to conduct both risk assessment and process-FMEA dynamically during the runtime, and thus enables flexible manufacturing scenarios with frequent changes of the production system and orders up to a lot-size of one while guaranteeing safety and product quality requirements. The automatically generated results will assist human in making further decisions. To demonstrate the feasibility of our approach, we apply it to a case study.
Why does CTC result in peaky behavior?
Venue: arXiv cs.LG 2021
Year: 2021

The peaky behavior of CTC models is well known experimentally. However, an understanding about why peaky behavior occurs is missing, and whether this is a good property. We provide a formal analysis of the peaky behavior and gradient descent convergence properties of the CTC loss and related training criteria. Our analysis provides a deep understanding why peaky behavior occurs and when it is suboptimal. On a simple example which should be trivial to learn for any model, we prove that a feed-forward neural network trained with CTC from uniform initialization converges towards peaky behavior with a 100% error rate. Our analysis further explains why CTC only works well together with the blank label. We further demonstrate that peaky behavior does not occur on other related losses including a label prior model, and that this improves convergence.
Definability Results for Top-Down Tree Transducers
Venue: arXiv cs.FL 2021
Year: 2021

We prove that for a given deterministic top-down transducer with look-ahead it is decidable whether or not its translation is definable (1)~by a linear top-down tree transducer or (2)~by a tree homomorphism. We present algorithms that construct equivalent such transducers if they exist.
GWLAN: General Word-Level AutocompletioN for Computer-Aided Translation
Venue: arXiv cs.CL 2021
Year: 2021

Computer-aided translation (CAT), the use of software to assist a human translator in the translation process, has been proven to be useful in enhancing the productivity of human translators. Autocompletion, which suggests translation results according to the text pieces provided by human translators, is a core function of CAT. There are two limitations in previous research in this line. First, most research works on this topic focus on sentence-level autocompletion (i.e., generating the whole translation as a sentence based on human input), but word-level autocompletion is under-explored so far. Second, almost no public benchmarks are available for the autocompletion task of CAT. This might be among the reasons why research progress in CAT is much slower compared to automatic MT. In this paper, we propose the task of general word-level autocompletion (GWLAN) from a real-world CAT scenario, and construct the first public benchmark to facilitate research in this topic. In addition, we propose an effective method for GWLAN and compare it with several strong baselines. Experiments demonstrate that our proposed method can give significantly more accurate predictions than the baseline methods on our benchmark datasets.