RLHF Mathematics

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Pair {int a, b; int winner;}; // winner = 0 means a>b, 1 means b>a
5
6
// Numerically stable sigmoid
7
static inline double sigmoid(double x) {
8
    if (x >= 0) {
9
        double z = exp(-x);
10
        return 1.0 / (1.0 + z);
11
    } else {
12
        double z = exp(x);
13
        return z / (1.0 + z);
14
    }
15
}
16
17
int main() {
18
    ios::sync_with_stdio(false);
19
    cin.tie(nullptr);
20
21
    // 1) Generate synthetic data
22
    int n = 8;                // number of items (responses)
23
    int m = 5000;             // number of comparisons
24
    unsigned seed = 42;
25
    mt19937 rng(seed);
26
    normal_distribution<double> nd(0.0, 1.0);
27
    uniform_int_distribution<int> uid(0, n-1);
28
29
    // Ground-truth scores (mean-centered)
30
    vector<double> r_true(n);
31
    for (int i = 0; i < n; ++i) r_true[i] = nd(rng);
32
    double mean = accumulate(r_true.begin(), r_true.end(), 0.0) / n;
33
    for (double &x : r_true) x -= mean;
34
35
    // Create comparisons according to Bradley–Terry
36
    vector<Pair> data;
37
    data.reserve(m);
38
    for (int k = 0; k < m; ++k) {
39
        int a = uid(rng), b = uid(rng);
40
        while (b == a) b = uid(rng);
41
        double p = sigmoid(r_true[a] - r_true[b]);
42
        bernoulli_distribution bd(p);
43
        bool a_wins = bd(rng);
44
        Pair pr{a, b, a_wins ? 0 : 1};
45
        data.push_back(pr);
46
    }
47
48
    // 2) Train Bradley–Terry scores with gradient ascent
49
    vector<double> r(n, 0.0); // initialize learned scores to 0
50
    double lr = 0.1;          // learning rate
51
    double lambda = 1e-3;     // L2 regularization strength (stabilizes scale)
52
    int epochs = 20;
53
54
    vector<double> grad(n, 0.0);
55
    for (int ep = 0; ep < epochs; ++ep) {
56
        fill(grad.begin(), grad.end(), 0.0);
57
        shuffle(data.begin(), data.end(), rng);
58
        double loglik = 0.0;
59
        for (const auto &pr : data) {
60
            int a = pr.a, b = pr.b;
61
            // Define outcome y in {+1, -1}: +1 means a preferred, -1 means b preferred
62
            int y = (pr.winner == 0) ? +1 : -1;
63
            double z = (r[a] - r[b]) * y;        // signed margin
64
            double p = sigmoid(z);               // probability of observed outcome
65
            loglik += log(max(1e-15, p));        // accumulate log-likelihood (safe)
66
            double coeff = (1.0 - p) * y;        // gradient of log sigma(z) wrt (r[a]-r[b])
67
            grad[a] += coeff;
68
            grad[b] -= coeff;
69
        }
70
        // Add L2 regularization gradient and update
71
        for (int i = 0; i < n; ++i) {
72
            grad[i] -= lambda * r[i];
73
            r[i] += lr * grad[i];
74
        }
75
        // Mean-center to fix gauge (optional but helps stability)
76
        double mu = accumulate(r.begin(), r.end(), 0.0) / n;
77
        for (double &x : r) x -= mu;
78
79
        if ((ep+1) % 5 == 0) {
80
            cerr << "Epoch " << (ep+1) << ", avg loglik per pair = " << (loglik / m) << "\n";
81
        }
82
    }
83
84
    // 3) Evaluate: rank correlation with ground truth & sample predictions
85
    vector<int> idx(n); iota(idx.begin(), idx.end(), 0);
86
    sort(idx.begin(), idx.end(), [&](int i, int j){return r[i] > r[j];});
87
    cout << "Learned scores (descending):\n";
88
    for (int id : idx) cout << "item " << id << ": r=" << r[id] << ", r_true=" << r_true[id] << "\n";
89
90
    // Predict win probability for a random pair
91
    int A = 0, B = 1;
92
    double pred = sigmoid(r[A] - r[B]);
93
    cout << fixed << setprecision(3);
94
    cout << "P(item " << A << " > item " << B << ") = " << pred << "\n";
95
    return 0;
96
}
97

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Stable sigmoid
5
static inline double sigmoid(double x) {
6
    if (x >= 0) { double z = exp(-x); return 1.0 / (1.0 + z); }
7
    else { double z = exp(x); return z / (1.0 + z); }
8
}
9
10
struct Example {
11
    vector<double> f1; // features of response 1
12
    vector<double> f2; // features of response 2
13
    int y;             // 1 if response 1 preferred, 0 otherwise
14
};
15
16
int main(){
17
    ios::sync_with_stdio(false);
18
    cin.tie(nullptr);
19
20
    int d = 10;          // feature dimension
21
    int m = 4000;        // number of pairwise examples
22
    unsigned seed = 7;
23
    mt19937 rng(seed);
24
    normal_distribution<double> nd(0.0, 1.0);
25
26
    // Ground-truth linear reward: r(y)=w*^T phi(y)
27
    vector<double> w_true(d);
28
    for (int i = 0; i < d; ++i) w_true[i] = nd(rng);
29
30
    // Generate synthetic examples
31
    vector<Example> data; data.reserve(m);
32
    for (int k = 0; k < m; ++k) {
33
        Example ex; ex.f1.resize(d); ex.f2.resize(d);
34
        for (int i = 0; i < d; ++i) { ex.f1[i] = nd(rng); ex.f2[i] = nd(rng); }
35
        // Preference probability depends on difference of features
36
        double z = 0.0; for (int i = 0; i < d; ++i) z += w_true[i] * (ex.f1[i] - ex.f2[i]);
37
        double p = sigmoid(z);
38
        bernoulli_distribution bd(p);
39
        ex.y = bd(rng) ? 1 : 0;
40
        data.push_back(move(ex));
41
    }
42
43
    // Train logistic regression on feature differences
44
    vector<double> w(d, 0.0);
45
    double lr = 0.2;     // learning rate
46
    double lambda = 1e-3;// L2 regularization
47
    int epochs = 15;
48
49
    vector<int> order(m); iota(order.begin(), order.end(), 0);
50
    for (int ep = 0; ep < epochs; ++ep) {
51
        shuffle(order.begin(), order.end(), rng);
52
        double loglik = 0.0;
53
        // Accumulate gradient in mini-batches (here full-batch for simplicity)
54
        vector<double> grad(d, 0.0);
55
        for (int idx : order) {
56
            const auto &ex = data[idx];
57
            // Delta features
58
            double z = 0.0; 
59
            for (int i = 0; i < d; ++i) z += w[i] * (ex.f1[i] - ex.f2[i]);
60
            double p = sigmoid(z);
61
            loglik += ex.y ? log(max(1e-15, p)) : log(max(1e-15, 1.0 - p));
62
            double err = (ex.y - p); // gradient coefficient
63
            for (int i = 0; i < d; ++i) grad[i] += err * (ex.f1[i] - ex.f2[i]);
64
        }
65
        for (int i = 0; i < d; ++i) {
66
            grad[i] -= lambda * w[i];
67
            w[i] += lr * grad[i] / m; // average gradient update
68
        }
69
        if ((ep+1) % 5 == 0) cerr << "Epoch " << (ep+1) << ": avg loglik = " << (loglik/m) << "\n";
70
    }
71
72
    // Evaluate: accuracy on the training set (for demo) and compare to w_true direction
73
    int correct = 0;
74
    for (const auto &ex : data) {
75
        double z = 0.0; for (int i = 0; i < d; ++i) z += w[i] * (ex.f1[i] - ex.f2[i]);
76
        int pred = sigmoid(z) >= 0.5 ? 1 : 0;
77
        correct += (pred == ex.y);
78
    }
79
    cout << fixed << setprecision(3);
80
    cout << "Training accuracy: " << (double)correct / m << "\n";
81
82
    // Print first few learned vs. true weights (scaled cosine similarity)
83
    double dot=0, n1=0, n2=0; for (int i=0;i<d;++i){dot+=w[i]*w_true[i]; n1+=w[i]*w[i]; n2+=w_true[i]*w_true[i];}
84
    cout << "Cosine similarity(w, w_true): " << (dot / (sqrt(n1)*sqrt(n2)+1e-12)) << "\n";
85
86
    return 0;
87
}
88

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
static inline double sigmoid(double x){
5
    if (x >= 0) { double z = exp(-x); return 1.0/(1.0+z); }
6
    else { double z = exp(x); return z/(1.0+z); }
7
}
8
9
struct Pair {int i,j; double uncertainty;};
10
11
int main(){
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    // Suppose we have current Bradley–Terry scores r for n items
16
    int n = 10; 
17
    vector<double> r = {0.9, -0.2, 1.3, 0.1, -1.1, 0.4, -0.7, 0.0, 0.8, -0.5};
18
19
    // For active data collection, prioritize pairs with high predictive uncertainty
20
    // A natural measure is p(1-p) where p = sigma(r[i]-r[j]); it is maximized near 0.5
21
    vector<Pair> candidates;
22
    for (int i = 0; i < n; ++i) {
23
        for (int j = i+1; j < n; ++j) {
24
            double p = sigmoid(r[i]-r[j]);
25
            double u = p*(1.0-p); // variance of Bernoulli; proxy for informativeness
26
            candidates.push_back({i,j,u});
27
        }
28
    }
29
30
    int K = 8; // request top-K most uncertain pairs
31
    nth_element(candidates.begin(), candidates.begin()+min(K,(int)candidates.size()) , candidates.end(),
32
                [](const Pair& a, const Pair& b){return a.uncertainty > b.uncertainty;});
33
    sort(candidates.begin(), candidates.begin()+min(K,(int)candidates.size()),
34
         [](const Pair& a, const Pair& b){return a.uncertainty > b.uncertainty;});
35
36
    cout << fixed << setprecision(4);
37
    cout << "Top-" << K << " most uncertain pairs (i,j) with uncertainty p(1-p):\n";
38
    for (int k = 0; k < K && k < (int)candidates.size(); ++k) {
39
        auto &c = candidates[k];
40
        cout << "(" << c.i << "," << c.j << ")\tunc=" << c.uncertainty << "\n";
41
    }
42
43
    return 0;
44
}
45