Function compute_naive_auc

ciphercore-base/src/ops/auc.rs:118–177

(y_true: Node, y_pred: Node, fp: &FixedPrecisionConfig)

}

fn compute_naive_auc(y_true: Node, y_pred: Node, fp: &FixedPrecisionConfig) -> Result<Node> {
    // This function doesn't account for equal predictions.
    // Assuming all predictions are distinct:
    // AUC = (number of pairs (i, j) such that y_pred[i] < y_pred[j] and y_true[i] < y_true[j]) / (number of pairs (i, j) such that y_true[i] < y_true[j]).
    let g = y_true.get_graph();
    let joined =
        g.create_named_tuple(vec![("y_pred".into(), y_pred), ("y_true".into(), y_true)])?;
    let joined = g.custom_op(
        CustomOperation::new(SortByIntegerKey {
            key: "y_pred".into(),
        }),
        vec![joined],
    )?;
    let y_true = joined.named_tuple_get("y_true".into())?;

    // Compute AUC denominator, i.e. num_ones * num_zeros.
    let num_ones = y_true.sum(vec![0])?.truncate(fp.denominator())?;
    let n = y_true.get_type()?.get_dimensions()[0] as i64;
    let n = constant_scalar(&g, n, INT64)?;
    let num_zeros = n.subtract(num_ones.clone())?;
    let denominator = num_ones.multiply(num_zeros)?;

    // Compute AUC numerator.
    let one = constant_scalar(&g, fp.denominator(), INT64)?;
    let num_zeros_on_prefix = one.subtract(y_true.clone())?.cum_sum(0)?;
    let num_zeros_before_one = num_zeros_on_prefix
        .multiply(y_true)?
        .truncate(fp.denominator())?;
    let numerator = num_zeros_before_one
        .sum(vec![0])?
        .truncate(fp.denominator())?;

    // Compute AUC.
    let numerator = i64_to_i128(numerator)?;
    let denominator = i64_to_i128(denominator)?;
    let denom_bits = MAX_LOG_ARRAY_SIZE * 2;
    // Note: GoldschmidtDivision requires denominator to be smaller than 2 ** denominator_cap_2k.
    // We use 2 ** 40 as a hard-coded constant, meaning that sqrt(denominator) must be smaller than 2 ** 20 (imposing restriction on the number of elements in the array).
    // We can potentially support larger arrays, if we first divide by num_ones, and then - by num_zeros.
    let result = g.custom_op(
        CustomOperation::new(GoldschmidtDivision {
            // Use 7 = log_2(128) iterations.
            iterations: 7,
            denominator_cap_2k: denom_bits,
        }),
        vec![numerator, denominator],
    )?;

    let result = match denom_bits.cmp(&fp.fractional_bits) {
        Ordering::Less => result.multiply(constant_scalar(
            &g,
            1 << (fp.fractional_bits - denom_bits),
            INT128,
        )?)?,
        Ordering::Equal => result,
        Ordering::Greater => result.truncate(1 << (denom_bits - fp.fractional_bits))?,
    };