fynch 0.3.0

Differentiable sorting and ranking: PAVA, Fenchel-Young losses, and O(n log n) FastSoftSort
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

//! External grounding for the fast (Blondel) soft sort/rank path.
//!
//! The fixture in `tests/fixtures/blondel_reference.json` was generated by
//! running google-research/fast-soft-sort (the reference implementation of
//! Blondel et al. 2020, arXiv:2002.08871) `numpy_ops.soft_sort` /
//! `numpy_ops.soft_rank` with `direction="ASCENDING"`,
//! `regularization="l2"` over several inputs (including ties and negatives)
//! and regularization strengths. Asserting against those values grounds
//! `fast_soft_sort` / `fast_soft_rank` in an implementation that shares no
//! code or author with this crate; the in-repo property tests alone are
//! self-consistency checks and cannot catch a shared misconception.

const TOLERANCE: f64 = 1e-6;

struct Case {
    input: Vec<f64>,
    strength: f64,
    soft_rank: Vec<f64>,
    soft_sort: Vec<f64>,
}

fn load_cases() -> Vec<Case> {
    let raw = std::fs::read_to_string(concat!(
        env!("CARGO_MANIFEST_DIR"),
        "/tests/fixtures/blondel_reference.json"
    ))
    .expect("fixture readable");
    let v: serde_json::Value = serde_json::from_str(&raw).expect("fixture parses");
    let floats = |x: &serde_json::Value| -> Vec<f64> {
        x.as_array()
            .expect("array")
            .iter()
            .map(|f| f.as_f64().expect("f64"))
            .collect()
    };
    v["cases"]
        .as_array()
        .expect("cases array")
        .iter()
        .map(|c| Case {
            input: floats(&c["input"]),
            strength: c["regularization_strength"].as_f64().expect("strength"),
            soft_rank: floats(&c["soft_rank"]),
            soft_sort: floats(&c["soft_sort"]),
        })
        .collect()
}

fn assert_close(got: &[f64], want: &[f64], what: &str, case: &Case) {
    assert_eq!(got.len(), want.len(), "{what}: length mismatch");
    for (i, (g, w)) in got.iter().zip(want).enumerate() {
        assert!(
            (g - w).abs() < TOLERANCE,
            "{what} diverges from the reference at index {i}: got {g}, want {w} \
             (input {:?}, strength {})",
            case.input,
            case.strength,
        );
    }
}

#[test]
fn fast_soft_sort_matches_reference_implementation() {
    let cases = load_cases();
    assert!(cases.len() >= 12, "fixture unexpectedly small");
    for case in &cases {
        let got = fynch::fast_soft_sort(&case.input, case.strength);
        assert_close(&got, &case.soft_sort, "fast_soft_sort", case);
    }
}

#[test]
fn fast_soft_rank_matches_reference_implementation() {
    let cases = load_cases();
    for case in &cases {
        let got = fynch::fast_soft_rank(&case.input, case.strength).expect("valid input");
        assert_close(&got, &case.soft_rank, "fast_soft_rank", case);
    }
}

#[test]
fn fast_soft_rank_hard_limit_recovers_integer_ranks() {
    // Independent of the fixture: at tiny regularization the soft ranks
    // converge to the hard ascending ranks.
    let x = [0.5, 0.2, 0.8, 0.1];
    let ranks = fynch::fast_soft_rank(&x, 1e-6).expect("valid input");
    let expected = [3.0, 2.0, 4.0, 1.0];
    for (g, w) in ranks.iter().zip(&expected) {
        assert!((g - w).abs() < 1e-3, "hard limit: got {g}, want {w}");
    }
}