Softmax is the most commonly used output function for multiclass problems and
is widely used in areas such as vision, natural language processing, and
recommendation. A softmax model has linear costs in the number of classes which
makes it too expensive for many real-world problems. A common approach to speed
up training involves sampling only some of the classes at each training step.
It is known that this method is biased and that the bias increases the more the
sampling distribution deviates from the output distribution. Nevertheless,
almost any recent work uses simple sampling distributions that require a large
sample size to mitigate the bias. In this work, we propose a new class of
kernel based sampling methods and develop an efficient sampling algorithm.
Kernel based sampling adapts to the model as it is trained, thus resulting in
low bias. Kernel based sampling can be easily applied to many models because it
relies only on the model's last hidden layer. We empirically study the
trade-off of bias, sampling distribution and sample size and show that kernel
based sampling results in low bias with few samples.

本文提出了基于核函数的采样方法并发展了高效的采样算法以减少对于大量样本情况下传统采样方法的偏倚问题。实验结果表明此方法相较于传统采样方法偏差较小并且需要的样本数更少。

基于核采样的自适应采样 Softmax

Adaptive Sampled Softmax with Kernel Based Sampling

A number of online services nowadays rely upon machine learning to extract
valuable information from data collected in the wild. This exposes learning
algorithms to the threat of data poisoning, i.e., a coordinate attack in which
a fraction of the training data is controlled by the attacker and manipulated
to subvert the learning process. To date, these attacks have been devised only
against a limited class of binary learning algorithms, due to the inherent
complexity of the gradient-based procedure used to optimize the poisoning
points (a.k.a. adversarial training examples). In this work, we rst extend the
de nition of poisoning attacks to multiclass problems. We then propose a novel
poisoning algorithm based on the idea of back-gradient optimization, i.e., to
compute the gradient of interest through automatic di erentiation, while also
reversing the learning procedure to drastically reduce the attack complexity.
Compared to current poisoning strategies, our approach is able to target a
wider class of learning algorithms, trained with gradient- based procedures,
including neural networks and deep learning architectures. We empirically
evaluate its e ectiveness on several application examples, including spam
ltering, malware detection, and handwritten digit recognition. We nally show
that, similarly to adversarial test examples, adversarial training examples can
also be transferred across di erent learning algorithms.

该论文提出了一种基于反向梯度优化的毒化攻击算法，能够对梯度优化训练的广泛学习算法进行攻击，并在实际应用中进行了有效性评估。

使用反向梯度优化实现深度学习算法中的毒化技术

Towards Poisoning of Deep Learning Algorithms with Back-gradient  Optimization

Many modern multiclass and multilabel problems are characterized by
increasingly large output spaces. For these problems, label embeddings have
been shown to be a useful primitive that can improve computational and
statistical efficiency. In this work we utilize a correspondence between rank
constrained estimation and low dimensional label embeddings that uncovers a
fast label embedding algorithm which works in both the multiclass and
multilabel settings. The result is a randomized algorithm for partial least
squares, whose running time is exponentially faster than naive algorithms. We
demonstrate our techniques on two large-scale public datasets, from the Large
Scale Hierarchical Text Challenge and the Open Directory Project, where we
obtain state of the art results.

本文提出了利用排名约束估计与低维标签嵌入之间的对应关系来发现一种新的、快速的标签嵌入算法，并展示了其在多类问题和多标签问题中的应用，最终实现了指数级的运行时间优化，其中在两个大规模公共数据集上的结果优于现有技术。

极大输出空间的快速标签嵌入

Fast Label Embeddings for Extremely Large Output Spaces

Random projections have been applied in many machine learning algorithms.
However, whether margin is preserved after random projection is non-trivial and
not well studied. In this paper we analyse margin distortion after random
projection, and give the conditions of margin preservation for binary
classification problems. We also extend our analysis to margin for multiclass
problems, and provide theoretical bounds on multiclass margin on the projected
data.

本文分析随机投影后的距离边界失真，给出二进制分类问题保留边界的条件，并扩展分析到多类分类问题，提供了关于投影数据上多类边界的理论界限。