Negative Sampling › Implementing Efficient Negative Sampling
Michael BrenndoerferApril 4, 20253 min read
Language AI HandbookAll chapters Part 4 of 67Word Embeddings
Negative Sampling › Implementing Efficient Negative SamplingOne section · Sections in this chapter8 / 15 ↓
Sections in this chapter15
Reading tools Definitions & inline links
Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.
Article links
Make inline references clickable
A practical implementation needs to sample from the noise distribution efficiently. Computing probabilities for 100,000 words on every sample would be slow. Instead, we precompute a sampling structure. The key approach uses a cumulative probability array and binary search, giving per sample after preprocessing.
In[22]:
Codeclass NegativeSampler:
"""
Efficient negative sampling using precomputed cumulative distribution.
Preprocessing: O(V)
Sampling: O(log V) per sample using binary search
"""
def __init__(self, word_counts, alpha=0.75):
"""
Initialize the sampler with word frequency counts.
Args:
word_counts: Dict mapping words or indices to frequencies
alpha: Smoothing exponent (default 0.75)
"""
self.words = list(word_counts.keys())
self.word_to_idx = {w: i for i, w in enumerate(self.words)}
freqs = np.array([word_counts[w] for w in self.words], dtype=np.float64)
smoothed = freqs**alpha
self.probs = smoothed / smoothed.sum()
# Precompute cumulative distribution for binary search sampling
self.cumsum = np.cumsum(self.probs)
def sample(self, k, exclude_idx=None):
"""
Sample k negative word indices.
Args:
k: Number of samples
exclude_idx: Index to exclude (typically the positive word)
Returns:
List of k word indices
"""
samples = []
while len(samples) < k:
r = np.random.random()
idx = np.searchsorted(self.cumsum, r)
if idx != exclude_idx:
samples.append(idx)
return samples
# Create sampler with our example vocabulary
sampler = NegativeSampler(word_frequencies, alpha=0.75)Out[23]:
ConsoleNegative Sampling Demonstration: ------------------------------------------------------- Drew 1000 batches of 5 negative samples each Total samples: 5000 Word sampling frequencies (should roughly match smoothed dist): Word Expected Observed Ratio --------------------------------------------- the 0.3931 0.3972 1.01 a 0.3325 0.3312 1.00 is 0.2337 0.2306 0.99 word 0.0124 0.0148 1.19 embedding 0.0074 0.0066 0.89 neural 0.0063 0.0056 0.90 semantic 0.0037 0.0036 0.97 vector 0.0105 0.0102 0.97
Out[24]:
Visualization