BER-PEF: Unified Human Mobility Predictability Evaluation via Bayes Error Rate Estimation

• Predictability estimates a model-independent performance limit, unlike empirical metrics that report one predictor's performance under a particular train–test protocol.The limit concerns predictive structure under fixed history, target labels, and representation, and indicates distance from attainable performance.Source: §1 · p. 1
• Predictability limits help interpret model accuracy and distinguish room to improve a predictor from limited predictive information under current conditions.Comparing limits across temporal, semantic, and structural conditions can inform whether to improve the model, enrich inputs, or reconsider the task definition.Source: §1 · p. 1
• On real mobility data, unobservable ground truth and differing estimator assumptions prevent static outputs from establishing which estimator is reliable.The challenge extends across symbolic check-ins, continuous GPS trajectories, contextual inputs, and learned embeddings.Source: §1 · p. 1
• BER-PEF treats predictability as the complement of Bayes-optimal error and uses BER estimators to produce lower- and upper-side estimates in a common feature–label space.The estimator generates estimates; the framework evaluates their consistency and reliability.Source: §1 · p. 2
• Controlled perturbation curves give estimators shared samples, label spaces, representations, and reference intervals, assessed with lower-side, upper-side, and full-interval discrepancies.A unified representation layer maps symbolic sequences, numeric trajectories, and temporal or categorical context into a common feature–label representation.Source: §1 · p. 2
• Selected BER-based estimates achieve lower reference discrepancy than existing upper-side methods and track empirical prediction changes under perturbation.Across datasets, BER-based estimates remain close to and strongly correlated with the best observed prediction performance, even when the best-performing algorithm changes.Source: §1 · p. 2

2.1 Human Mobility Prediction

• Deep learning models capture higher-order mobility dependencies, but their shared objective remains improving empirical predictor accuracy for specific tasks and data conditions.Earlier Markov and probabilistic models have clear interpretations and low training costs, but prescribed transitions constrain their ability to capture high-order spatiotemporal dependencies.Source: §2.1 · p. 2
• BER-PEF estimates attainable predictability limits rather than proposing a new mobility predictor.This contrasts with mobility knowledge-transfer, multi-city, and external-knowledge work that extends predictor design.Source: §2.1 · p. 2

2.2 Predictability Evaluation and Bayes Error Estimation

• Entropy, compression, context-based, and permutation-entropy methods provide foundations but often depend on particular sequence forms or report only upper-side estimates.These constraints complicate unified comparison across continuous trajectories, multidimensional context, and learned embeddings.Source: §2.2 · pp. 2–3, Figure 1 · p. 3
• Bayes error gives the same limit as best attainable classifier performance in a representation space, but prior work lacked a complete real-mobility workflow for heterogeneous inputs without observable ground truth.BER-PEF extends this connection using a unified representation layer, controlled perturbation curves, and a common reliability protocol.Source: §2.2 · p. 3

3.1 Problem Formulation

• Predictability is the optimal attainable performance in a fixed representation space, distinct from one predictor’s empirical accuracy under a particular protocol.History windows become feature–label samples: the input encodes mobility history, the target is the next observation, and context can be included as input.Source: §3.1 · pp. 3–4

3.2 Unified Evaluation Architecture

• Three layers map mobility inputs to numeric features, estimate lower- and upper-side predictability under perturbations, and compare the resulting curves with a reference interval.The area-evaluation layer summarizes discrepancy over perturbation strength.Source: Figure 2 · p. 4, §3.2 · p. 5

3.2.1 Unified Representation Layer

• Symbolic, numeric, and contextual inputs share an encoder whose projected sample representations are paired with target labels for BER estimation.Next-step supervision trains the representation, but the prediction head and its accuracy are not the final predictability estimate; UNIMOB is a primary, not mandatory, implementation.Source: §3.2.1 · p. 5

3.2.2 Predictability-Curve Evaluation Protocol

• Controlled perturbations create a difficulty curve using shared samples, labels, and representations, while reference bounds constrain reasonable estimates as regularity is removed.Normalized lower-side, upper-side, and total discrepancies aggregate curve deviations; trapezoidal integration uses actual perturbation coordinates, and held-out data separately test practical reliability.Source: §3.2.2 · pp. 5–6
• Area evaluation can distinguish estimators that match at zero perturbation but differ over a positive-width interval.The protocol aggregates repeated runs at each perturbation level before trapezoidal integration; the practical reliability advantage is tested separately on held-out data.Source: §3.2.2 · p. 6

3.3 BER Estimator Family and Extensibility

• BER-PEF is an estimator-agnostic comparison protocol, with core nearest-neighbor estimators and an extended family representing additional assumptions.The core experiments use 1NN(k = 3), kNN, and kNN-LOO; extended estimators demonstrate compatibility rather than presumed superiority.Source: §3.3 · p. 6

4.1 Experimental Setup

• The experiments compare estimator agreement, empirical calibration, task-level prediction benchmarks, evaluation reliability, and representation robustness across symbolic sequences and continuous trajectories.The protocol-specific procedures are introduced with the corresponding research questions.Source: §4.1 · p. 7

4.1.1 Datasets and Tasks

• Symbolic tasks use Foursquare NYC and TKY next-location labels; numeric tasks use GeoLife and T-Drive trajectories represented in local coordinates and discretized for next-state prediction.The selected fixed-size subsets are controlled comparison units, not survey samples for citywide user distributions.Source: §4.1.1 · p. 7

4.1.2 Compared Methods

• The evaluation includes task-specific entropy and regularity methods, plus BER-PEF estimators spanning nearest-neighbor, density/KDE, divergence/GHP, and extrapolation approaches.Existing methods provide upper-side estimates; BER-PEF estimators provide both sides of the reference interval.Source: §4.1.2 · p. 7

4.2 Cross-Form Estimator Comparison under a Unified Perturbation Protocol

• The protocol compares estimator outputs along shared perturbation curves using upper-side discrepancy for existing methods and lower-side, upper-side, and Total discrepancy for BER-PEF estimators.Total is LD + UD and measures deviation across the full reference interval.Source: §4.2 · p. 7, §4.1.2 · p. 7

4.2.1 Symbolic Mobility Sequences

• On NYC/TKY, KDE, KDE-kNN-LOO, and GHP have UD values of 0.046/0.033, 0.053/0.052, and 0.074/0.071, all below LZ-Fano’s 0.101/0.109.These BER-PEF estimators were selected by mean Total; Fig. 4 compares upper-side discrepancy across symbolic and numeric data forms.Source: §4.2.1 · p. 7, Figure 4 · p. 8
• GHP’s symbolic UD is low, but its Total values are 0.325/0.322, indicating that its main discrepancy is on the lower side.Full-interval evaluation exposes deviations that an upper-side comparison alone would not show.Source: §4.2.1 · p. 7

4.2.2 Numeric Trajectories

• On GeoLife/T-Drive, kNN-LOO, 1NN(k = 3), and GHP achieve Total values of 0.073/0.035, 0.075/0.035, and 0.075/0.036, with near-zero UD.The Fig. 6 curves show BER-based estimates following the reference interval as trajectory perturbation increases.Source: §4.2.2 · pp. 7–8

4.3 Calibration to Empirical Prediction Performance

• Calibration uses the highest Acc@1 among Linear-Ngram, SEQMLP, and UNIMOB on shared perturbed labels as an empirical best-of-three proxy.Trend agreement is measured with Pearson and Spearman correlations, fit with OLS R2, and scale calibration with MAE to y = x.Source: §4.3 · pp. 8–9
• BER-LR attains Pearson correlation 0.9986, R2 = 0.9972, and identity MAE 0.0111; Predictability(LZ) has Pearson correlation 0.9575 and identity MAE 0.4372.The best-performing BER estimators track changes in prediction performance and match its observed scale more closely than Predictability(LZ).Source: §4.3 · p. 9

4.4 BER Predictability against an Empirical Algorithm Benchmark

• The benchmark takes the highest observed Acc@1 from each dataset’s applicable algorithm pool, with BER-kNN and the seven shared predictors evaluated on matched samples, labels, splits, and noise seeds.The comparison reports a four-dataset macro mean absolute gap and perturbation curves, with two-sided Student-t 95% confidence intervals over ten realizations.Source: §4.4 · p. 9
• 0.019298 is BER-kNN’s four-dataset mean absolute gap, below Random Forest’s 0.029946 and 5NN’s 0.033425, ranking first among eight common methods.Its dataset gaps are 0.011425 on NYC, 0.007166 on TKY, 0.038392 on GeoLife, and 0.020209 on T-Drive.Source: §4.4 · p. 9, Table 2 · p. 10
• Pearson correlation between BER-kNN and the benchmark ranges from 0.995 to 0.999 across datasets, while Spearman correlation is 1.0 throughout the six perturbation-level means.BER-kNN follows the decline in empirical prediction performance as perturbation increases.Source: §4.4 · p. 10
• A gap between an algorithm and the BER predictability estimate indicates remaining room for algorithmic or representational improvement; convergence toward the estimate suggests gains are increasingly constrained by predictable information.The stable agreement with the empirical algorithm envelope provides a task-level reference for distinguishing algorithm mismatch from data-limited performance.Source: §4.4 · p. 10

4.5 Selection Reliability of Multi-Point Area Evaluation

• Origin-only selection uses the lowest Total at ρ = 0, whereas the prespecified eight-point protocol selects by normalized Total area and is validated on 20 disjoint repetitions at held-out levels.Selection uses ten repetitions; the held-out regret is the selected estimator’s Total difference from the held-out oracle, with zero meaning the oracle was selected.Source: §4.5 · p. 10
• Mean subset regret falls from 0.000479 at four points to 0.000201 at six and 0.000126 at eight, while worst-case regret falls from 0.001326 to 0.000875 and 0.000193.The enumerated subsets are endpoint-anchored observation sets with two to eight points.Source: §4.5 · pp. 10–11
• The eight-point protocol lowers pooled held-out regret from 0.000727 to 0.000130, raises oracle top-1 recovery from 0.567 to 0.887, and improves pairwise ordering accuracy from 0.633 to 0.962.The regret difference is −0.000596 with a 95% hierarchical bootstrap interval of [−0.001476, 0.000085].Source: §4.5 · p. 10, Figure 8 · p. 11
• Multi-point area evaluation reduces selection sensitivity to the origin and to the placement of observation levels, providing interval-level evidence for estimator selection.The protocol compares BER-kNN with the seven shared prediction algorithms across Foursquare NYC, Foursquare TKY, GeoLife, and T-Drive.Source: §4.5 · p. 11, Figure 8 · p. 11

4.6 Predictive Information and Estimator Quality with Contextual Features

• Context raises Acc@1 from 0.360 to 0.394–0.399 on NYC and from 0.354 to 0.382–0.405 on TKY across time, category, and time-plus-category inputs.Category reaches 0.405 on TKY; category and time-plus-category each reach approximately 0.399 on NYC.Source: §4.6 · p. 11
• KDE-kNN-LOO’s LD of 0.044–0.085 is lower in every dataset–context condition than the best context-aware method’s range of 0.133–0.201.The comparison includes CTX, CTX-Merge, three core BER estimators, and KDE-kNN-LOO under the same LD metric.Source: §4.6 · p. 11
• Each core estimator has lower LD after adding context than under its corresponding baseline, and BER-PEF evaluates these empirical gains within a task-level framework.The experiment fixes history length, sample size, architectures, training and perturbation protocols, and the reference definition.Source: §4.6 · p. 11

4.7 Prediction Effectiveness and BER Evaluation Robustness of Unified Representations

• UNIMOB achieves Acc@1 of 0.379/0.384 on NYC/TKY, above SEQMLP’s 0.299/0.305 and Linear-Ngram’s 0.233/0.212.Its Acc@10 values of 0.723/0.760 are highest in both cities; Hit@10 is highest on TKY at 0.586 and is 0.531 on NYC versus SEQMLP’s 0.545.Source: §4.7 · pp. 11–12, Figure 11 · p. 13
• For numeric trajectories, learned representations lower best Total on GeoLife/T-Drive from RawTraj’s 0.237/0.075 to SEQMLP’s 0.070/0.046 and UNIMOB’s 0.074/0.034.For time-plus-category inputs, SEQMLP-C and UNIMOB-C obtain 0.315/0.297 and 0.297/0.263, below OneHot’s 0.582/0.561.Source: §4.7 · p. 12, Figure 12 · p. 13
• Frequency, Ngram-PCA, Linear-Ngram, SEQMLP, and UNIMOB produce comparable LD/UD results for symbolic data under the same protocol.The reported best-of-core values select among 1NN(k = 3), kNN, and kNN-LOO; Total comes from one estimator and equals LD + UD.Source: §4.7 · pp. 11–12, Figure 12 · p. 13
• BER-PEF is not tied to UNIMOB: task-relevant structure retained by a representation affects BER quality, and the protocol accommodates multiple structured representations.When poorer prediction performance accompanies higher discrepancy, lost predictive information in the representation may be a limitation rather than the predictor alone.Source: §4.7 · pp. 12–13

4.8 SOTA-Reference Robustness

• The analysis varies the SOTA-accuracy reference by factors from 0.75 to 1.25 while keeping estimator outputs fixed.Perturbed samples, representations, and labels also remain unchanged across settings.Source: §4.8 · p. 13
• Despite changes to the SOTA reference, core UD winners remain stable: NYC includes kNN-LOO and 1NN(k = 3), while TKY includes 1NN(k = 3).The corresponding LD winners are kNN-LOO on NYC and 1NN(k = 3) on TKY.Source: §4.8 · p. 13
• Absolute UD values change with the SOTA reference, so reference uncertainty affects discrepancy scale without changing the principal core-estimator comparison.The analysis focuses on 1NN(k = 3), kNN, and kNN-LOO.Source: §4.8 · p. 13

5 CONCLUSION

• BER-PEF addresses the lack of observable predictability ground truth by combining BER-based estimation with controlled perturbation evaluation and shared reference-interval discrepancies.The framework defines the predictability limit as the complement of Bayes-optimal error.Source: §5 · p. 13
• The representation layer supports symbolic sequences, continuous trajectories, context-enhanced inputs, and multiple learned representations under a common evaluation framework.Experiments show consistent evaluation across heterogeneous inputs.Source: §5 · p. 14
• The paper concludes that BER-PEF offers a unified, comparable, and verifiable path for predictability estimation and reliability analysis without observable ground truth.Source: §5 · p. 14