`nx_ir_eval.nx` source

↩ module page · 139 lines · 4576 B
1// nx_ir_eval.nx -- sovereign IR evaluation metrics: THE RULER for search SOTA.
2//
3// module: nishi-core.search.ir_eval
4// depends: fx.nx, syscalls.nx
5// capability: CORE_COMPUTE
6// wired_status: LIBRARY
7//
8// genealogy_id: jarvelin_kekalainen_2002_ndcg ; voorhees_trec_mrr ; trec_map
9//
10// WHY: "state of the art" is a MEASURED claim, never an asserted one. Before any
11// fusion/rerank rung may claim a lift it must move a number on a FIXED ruler.
12// This organ is that ruler -- nDCG@k, MRR, Recall@k, Precision@k, and Average
13// Precision -- computed bit-exact in Q16.16 (fx.nx) so a score is reproducible on
14// every target and a faked improvement cannot hide. The rank discount is
15// 1/log2(rank+1) via fx_log2_int (Jarvelin & Kekalainen 2002), the exact use
16// fx.nx's fixed-point log2 was built for.
17//
18// Conventions:
19//   gains[i] = graded relevance of the doc at 0-based rank i (>= 0).
20//   rels[i]  = 1 if the doc at rank i is relevant, else 0.
21//   n        = number of ranked results;  k = cutoff.
22// All ratio outputs are Q16.16 in [0, FX_ONE(=65536)]; 0 means undefined/empty.
23
24import "fx.nx"
25import "syscalls.nx"
26
27// ---- discounted cumulative gain ----------------------------------
28
29// DCG@k = sum_{i=0}^{min(n,k)-1} gain[i] / log2(i+2).  Rank r=i+1, discount
30// log2(r+1)=log2(i+2); the rank-1 discount log2(2)=1.0 is exact. Result Q16.16.
31func ie_dcg_at_k(gains: *i64, n: i64, k: i64) -> i64 {
32    var lim: i64 = n
33    if k < lim { lim = k }
34    var acc: i64 = 0
35    var i: i64 = 0
36    while i < lim {
37        let g: i64 = gains[i]
38        if g > 0 {
39            let disc: i64 = fx_log2_int(i + 2)
40            acc = acc + fx_div(fx_from_int(g), disc)
41        }
42        i = i + 1
43    }
44    return acc
45}
46
47// Copy src -> dst and selection-sort dst into DESCENDING order (the ideal
48// ranking).  n small (top-k); deterministic by construction.
49func ie_sort_desc(src: *i64, n: i64, dst: *i64) -> i64 {
50    var i: i64 = 0
51    while i < n { dst[i] = src[i]; i = i + 1 }
52    var a: i64 = 0
53    while a < n {
54        var best: i64 = a
55        var b: i64 = a + 1
56        while b < n {
57            if dst[b] > dst[best] { best = b }
58            b = b + 1
59        }
60        if best != a {
61            let t: i64 = dst[a]
62            dst[a] = dst[best]
63            dst[best] = t
64        }
65        a = a + 1
66    }
67    return 0
68}
69
70// nDCG@k = DCG@k / IDCG@k, Q16.16 in [0, FX_ONE].  IDCG uses gains sorted
71// descending (the ideal ranking).  Returns 0 if there are no relevant docs.
72func ie_ndcg_at_k(gains: *i64, n: i64, k: i64) -> i64 {
73    if n <= 0 { return 0 }
74    let ideal: *i64 = sys_mmap(n * 8) as *i64
75    ie_sort_desc(gains, n, ideal)
76    let idcg: i64 = ie_dcg_at_k(ideal, n, k)
77    if idcg <= 0 { return 0 }
78    let dcg: i64 = ie_dcg_at_k(gains, n, k)
79    return fx_div(dcg, idcg)
80}
81
82// ---- reciprocal rank ---------------------------------------------
83
84// MRR for a single query: 1/(1-based rank of the first relevant doc), Q16.16.
85// Returns 0 if no relevant doc appears.
86func ie_mrr(rels: *i64, n: i64) -> i64 {
87    var i: i64 = 0
88    while i < n {
89        if rels[i] != 0 { return fx_from_frac(1, i + 1) }
90        i = i + 1
91    }
92    return 0
93}
94
95// ---- recall / precision ------------------------------------------
96
97// Count relevant docs within the top-k.
98func ie_hits_at_k(rels: *i64, n: i64, k: i64) -> i64 {
99    var lim: i64 = n
100    if k < lim { lim = k }
101    var h: i64 = 0
102    var i: i64 = 0
103    while i < lim {
104        if rels[i] != 0 { h = h + 1 }
105        i = i + 1
106    }
107    return h
108}
109
110// Recall@k = hits@k / total_relevant, Q16.16.  0 if total_relevant <= 0.
111func ie_recall_at_k(rels: *i64, n: i64, k: i64, total_relevant: i64) -> i64 {
112    if total_relevant <= 0 { return 0 }
113    return fx_from_frac(ie_hits_at_k(rels, n, k), total_relevant)
114}
115
116// Precision@k = hits@k / k, Q16.16.  0 if k <= 0.
117func ie_precision_at_k(rels: *i64, n: i64, k: i64) -> i64 {
118    if k <= 0 { return 0 }
119    return fx_from_frac(ie_hits_at_k(rels, n, k), k)
120}
121
122// ---- average precision -------------------------------------------
123
124// AP = (sum over relevant ranks r of Precision@r) / total_relevant, Q16.16.
125// The standard TREC single-query AP; mean over queries = MAP (caller averages).
126func ie_ap(rels: *i64, n: i64, total_relevant: i64) -> i64 {
127    if total_relevant <= 0 { return 0 }
128    var acc: i64 = 0
129    var hits: i64 = 0
130    var i: i64 = 0
131    while i < n {
132        if rels[i] != 0 {
133            hits = hits + 1
134            acc = acc + fx_from_frac(hits, i + 1)
135        }
136        i = i + 1
137    }
138    return fx_div(acc, fx_from_int(total_relevant))
139}
nx_ir_eval.nx source

`nx_ir_eval.nx` source
