Contrastive Learning Theory

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// L2-normalize a vector in-place
5
void l2_normalize(vector<double>& v) {
6
    double norm = 0.0;
7
    for (double x : v) norm += x * x;
8
    norm = sqrt(max(norm, 1e-12));
9
    for (double& x : v) x /= norm;
10
}
11
12
// Dot product
13
double dot(const vector<double>& a, const vector<double>& b) {
14
    double s = 0.0;
15
    for (size_t i = 0; i < a.size(); ++i) s += a[i] * b[i];
16
    return s;
17
}
18
19
// Compute InfoNCE loss for a batch.
20
// Inputs:
21
//  - Z: B x d anchor embeddings
22
//  - Z_all: (B + K) x d candidate embeddings (first B usually include anchors or their positives; the rest may come from a queue)
23
//  - pos_index[i]: index in [0, B+K) of the positive for anchor i
24
//  - tau: temperature > 0
25
// Assumptions:
26
//  - All embeddings will be L2-normalized to use cosine similarity.
27
//  - Self-comparisons (i with itself) are excluded if they appear among candidates.
28
double infoNCE_loss(const vector<vector<double>>& Z,
29
                    const vector<vector<double>>& Z_all,
30
                    const vector<int>& pos_index,
31
                    double tau) {
32
    const int B = (int)Z.size();
33
    const int C = (int)Z_all.size();
34
    const int d = (int)Z[0].size();
35
36
    // Copy and normalize anchors and candidates
37
    vector<vector<double>> ZA = Z;
38
    vector<vector<double>> ZC = Z_all;
39
    for (int i = 0; i < B; ++i) l2_normalize(ZA[i]);
40
    for (int j = 0; j < C; ++j) l2_normalize(ZC[j]);
41
42
    double total_loss = 0.0;
43
    for (int i = 0; i < B; ++i) {
44
        // Compute logits = sim(anchor_i, candidate_j)/tau for all j
45
        vector<double> logits(C);
46
        for (int j = 0; j < C; ++j) {
47
            logits[j] = dot(ZA[i], ZC[j]) / tau; // cosine similarity since normalized
48
        }
49
        // Optional: exclude exact self-match if Z is a subset of Z_all
50
        // Here, we simply avoid using i-th candidate as positive unless pos_index[i]==i by construction.
51
52
        // Numerical stability: log-sum-exp trick
53
        double m = -numeric_limits<double>::infinity();
54
        for (double v : logits) m = max(m, v);
55
        double denom = 0.0;
56
        for (int j = 0; j < C; ++j) denom += exp(logits[j] - m);
57
        double log_denom = m + log(max(denom, 1e-300));
58
59
        // Positive logit
60
        int pj = pos_index[i];
61
        if (pj < 0 || pj >= C) {
62
            throw runtime_error("pos_index out of range");
63
        }
64
        double logit_pos = logits[pj];
65
66
        // Loss for this anchor: -log (exp(l_pos) / sum exp(l_j))
67
        total_loss += -(logit_pos - log_denom);
68
    }
69
    return total_loss / max(B, 1);
70
}
71
72
int main() {
73
    ios::sync_with_stdio(false);
74
    cin.tie(nullptr);
75
76
    // Toy demo: B=4 anchors, d=8, K=6 queued negatives
77
    int B = 4, d = 8, K = 6;
78
    std::mt19937 rng(42);
79
    std::normal_distribution<double> nd(0.0, 1.0);
80
81
    // Create anchors Z and their positives Z_pos by adding small noise
82
    vector<vector<double>> Z(B, vector<double>(d));
83
    vector<vector<double>> Z_pos(B, vector<double>(d));
84
    for (int i = 0; i < B; ++i) {
85
        for (int j = 0; j < d; ++j) {
86
            double base = nd(rng);
87
            Z[i][j] = base + 0.1 * nd(rng);      // anchor
88
            Z_pos[i][j] = base + 0.1 * nd(rng);  // positive (similar)
89
        }
90
    }
91
92
    // Create K random negatives
93
    vector<vector<double>> Z_neg(K, vector<double>(d));
94
    for (int k = 0; k < K; ++k) for (int j = 0; j < d; ++j) Z_neg[k][j] = nd(rng);
95
96
    // Candidates = all positives first (B), then negatives (K)
97
    vector<vector<double>> Z_all;
98
    Z_all.insert(Z_all.end(), Z_pos.begin(), Z_pos.end());
99
    Z_all.insert(Z_all.end(), Z_neg.begin(), Z_neg.end());
100
101
    // For each anchor i, the positive is at index i in Z_all
102
    vector<int> pos_index(B);
103
    iota(pos_index.begin(), pos_index.end(), 0);
104
105
    double tau = 0.1;
106
    double L = infoNCE_loss(Z, Z_all, pos_index, tau);
107
    cout << fixed << setprecision(6);
108
    cout << "InfoNCE loss (toy): " << L << "\n";
109
110
    return 0;
111
}
112

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct NegativeQueue {
5
    int capacity;        // maximum number of items in the queue
6
    int d;               // embedding dimension
7
    int head;            // next position to write (circular)
8
    int size;            // current number of items
9
    vector<vector<double>> buf; // storage: capacity x d
10
11
    NegativeQueue(int capacity_, int d_) : capacity(capacity_), d(d_), head(0), size(0), buf(capacity_, vector<double>(d_, 0.0)) {}
12
13
    // Enqueue a batch of embeddings (overwrites oldest when full)
14
    void enqueueBatch(const vector<vector<double>>& X) {
15
        for (const auto& v : X) {
16
            if ((int)v.size() != d) throw runtime_error("Dimension mismatch");
17
            buf[head] = v;                 // copy embedding
18
            head = (head + 1) % capacity;  // advance head
19
            size = min(size + 1, capacity);
20
        }
21
    }
22
23
    // Get the current contents as a contiguous vector (oldest first is not guaranteed)
24
    vector<vector<double>> getAll() const {
25
        vector<vector<double>> out;
26
        out.reserve(size);
27
        // Return in circular order: from (head - size) to (head - 1)
28
        int start = (head - size + capacity) % capacity;
29
        for (int i = 0; i < size; ++i) {
30
            int idx = (start + i) % capacity;
31
            out.push_back(buf[idx]);
32
        }
33
        return out;
34
    }
35
};
36
37
int main() {
38
    ios::sync_with_stdio(false);
39
    cin.tie(nullptr);
40
41
    int d = 4;
42
    NegativeQueue q(5, d); // capacity 5 embeddings of dimension 4
43
44
    // Enqueue 3 vectors
45
    vector<vector<double>> A = {{1,2,3,4},{2,3,4,5},{3,4,5,6}};
46
    q.enqueueBatch(A);
47
48
    // Enqueue 4 more; the first two will be overwritten (capacity=5)
49
    vector<vector<double>> B = {{10,0,0,0},{0,10,0,0},{0,0,10,0},{0,0,0,10}};
50
    q.enqueueBatch(B);
51
52
    auto all = q.getAll();
53
    cout << "Queue size: " << all.size() << "\n";
54
    for (size_t i = 0; i < all.size(); ++i) {
55
        cout << i << ": ";
56
        for (double x : all[i]) cout << x << ' ';
57
        cout << '\n';
58
    }
59
    return 0;
60
}
61

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
void l2_normalize(vector<double>& v) {
5
    double n = 0.0; for (double x : v) n += x*x; n = sqrt(max(n, 1e-12));
6
    for (double& x : v) x /= n;
7
}
8
9
// Mean squared distance between positives (alignment)
10
double alignment(const vector<vector<double>>& Z, const vector<vector<double>>& Z_pos, double alpha=2.0) {
11
    if (Z.size() != Z_pos.size()) throw runtime_error("Mismatched batch size");
12
    const int B = (int)Z.size();
13
    double s = 0.0;
14
    for (int i = 0; i < B; ++i) {
15
        if (Z[i].size() != Z_pos[i].size()) throw runtime_error("Dim mismatch");
16
        double dist2 = 0.0;
17
        for (size_t j = 0; j < Z[i].size(); ++j) {
18
            double d = Z[i][j] - Z_pos[i][j];
19
            dist2 += d * d;
20
        }
21
        // alpha=2 yields squared distance; other alphas would require pow
22
        s += (alpha == 2.0 ? dist2 : pow(max(dist2, 1e-12), alpha/2.0));
23
    }
24
    return s / max(B, 1);
25
}
26
27
// Uniformity: log mean exp(-t * squared distance) over all unordered pairs
28
double uniformity(vector<vector<double>> Z, double t=2.0) {
29
    const int B = (int)Z.size();
30
    if (B <= 1) return 0.0;
31
    // Normalize to hypersphere for cosine geometry
32
    for (int i = 0; i < B; ++i) l2_normalize(Z[i]);
33
    double sum_exp = 0.0;
34
    long long pairs = 0;
35
    for (int i = 0; i < B; ++i) {
36
        for (int j = i+1; j < B; ++j) {
37
            double dist2 = 0.0;
38
            for (size_t k = 0; k < Z[i].size(); ++k) {
39
                double d = Z[i][k] - Z[j][k];
40
                dist2 += d * d;
41
            }
42
            sum_exp += exp(-t * dist2);
43
            ++pairs;
44
        }
45
    }
46
    double mean_exp = sum_exp / max(1LL, pairs);
47
    return log(max(mean_exp, 1e-300));
48
}
49
50
int main(){
51
    ios::sync_with_stdio(false);
52
    cin.tie(nullptr);
53
54
    int B=5, d=6; std::mt19937 rng(7); std::normal_distribution<double> nd(0,1);
55
    vector<vector<double>> Z(B, vector<double>(d)), Zpos(B, vector<double>(d));
56
    for (int i=0;i<B;++i){
57
        for (int j=0;j<d;++j){
58
            double base = nd(rng);
59
            Z[i][j]    = base + 0.2*nd(rng);
60
            Zpos[i][j] = base + 0.2*nd(rng);
61
        }
62
    }
63
    cout << fixed << setprecision(6);
64
    cout << "Alignment (alpha=2): " << alignment(Z, Zpos, 2.0) << "\n";
65
    cout << "Uniformity (t=2):   " << uniformity(Z, 2.0) << "\n";
66
    return 0;
67
}
68