Pith. sign in

REVIEW 3 major objections 3 minor 24 references

Scalable Unsupervised Segmentation via Random Fourier Feature-based Gaussian Process

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Random Fourier features make GP-HSMM segmentation 278 times faster.

desk verdict Straightforward engineering extension of GP-HSMM with real speedup on one dataset; accuracy claims rest on a thin evaluation and an unexamined factorized-likelihood approximation. read the letter →

arxiv 2507.10632 v1 pith:YK4YVAAY submitted 2025-07-14 cs.LG cs.AI

Issei Saito , Masatoshi Nagano , Tomoaki Nakamura , Daichi Mochihashi , Koki Mimura This is my paper
classification cs.LGcs.AI
keywords randomFourierfeaturesGaussianprocesshiddensemi-Markovmodelunsupervisedtime-seriessegmentationBayesianlinearregressionmotion-capturedatacomputationalefficiencyblockedGibbssamplerkernelmatrixinversion
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is trying to establish that the Gaussian process hidden semi-Markov model, an accurate but slow unsupervised segmentation method, can be made practical for large time series without sacrificing accuracy. The fix is to replace the Gaussian process's kernel matrix, whose inversion grows with the number of data points, with a fixed-size random Fourier feature representation so that per-segment cost no longer depends on segment length. If correct, this matters because GP-HSMM can then be used for real-time or near-real-time segmentation of long recordings such as motion capture, speech, and industrial logs, where nine-hour runs are currently prohibitive. The evidence is one experiment: on a 39,200-frame motion-capture dataset, segmentation accuracy stays around 0.357 in normalized Hamming distance versus 0.351 for the baseline, while runtime drops roughly 278-fold from about nine hours to about two minutes.

What carries the argument

The central object is the random Fourier feature map $\phi(t) = \sqrt{2/M}\,[\cos(\omega^{(m)} t + b^{(m)})]_{m=1}^{M}$, which makes the RBF kernel approximately the inner product $\phi(t_p)^\top \phi(t_q)$. This converts Gaussian process regression, which needs the $N_c \times N_c$ kernel inverse, into Bayesian linear regression whose only matrix inverse is $M \times M$ and depends only on the fixed number of features. The paper sets $M=20$ and keeps the rest of GP-HSMM unchanged—Poisson segment durations, Dirichlet transition priors, and blocked Gibbs sampling with forward filtering–backward sampling—so the entire speedup comes from this substitution.

What would settle it

Re-run the large-scale experiment with $M=20$ and $M=200$ (plus intermediate values) on the same CMU sequences: if the normalized Hamming distance drops significantly as $M$ grows, the reported parity with GP-HSMM is an artifact of an undersized feature count. A complementary check is to compute a uniform bound on $|k(t_p,t_q) - \phi(t_p)^\top \phi(t_q)|$ from the RFF concentration inequality and see whether the implied predictive-variance error exceeds the observed 0.006 NHD gap.

Watch

Extended reading notes

Core claim

The paper proposes RFF-GP-HSMM, a probabilistic unsupervised segmentation model in which the Gaussian process emission of GP-HSMM is replaced by Bayesian linear regression on random Fourier features. For a segment of length $N_c$, the original model must invert an $N_c \times N_c$ kernel matrix, whereas RFF-GP-HSMM inverts a fixed $M \times M$ matrix with $M=20$, so the computational cost per segment stays constant as data grow. On the CMU motion-capture exercise dataset, the method reports a normalized Hamming distance of 0.357 against 0.351 for conventional GP-HSMM, and a 278-fold speedup on a 39,200-frame dataset where GP-HSMM takes about $3.3 \times 10^4$ seconds and RFF-GP-HSMM takes about $1.2 \times 10^2$ seconds.

Load-bearing premise

The load-bearing premise is that $M=20$ random Fourier features approximate the RBF kernel well enough that segmentation quality is essentially unchanged, and the paper provides no error bound or sensitivity analysis for $M$.

Editorial extensions

If this is right

  • Segmentation of a 39,200-frame sequence takes about 2 minutes instead of 9 hours, making GP-HSMM usable on long recordings in practice.
  • Runtime per segment no longer grows with segment length, so the method should extend to datasets far larger than the 39,200 frames tested.
  • Accuracy on the tested motion-capture data is essentially unchanged (0.357 versus 0.351 NHD), so the speedup does not come at an obvious accuracy cost in this setting.
  • Because the rest of the model is unchanged, RFF-GP-HSMM can be dropped into existing GP-HSMM application areas—work analysis, animal behavior, robot motion learning—as a faster substitute.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper reports only $M=20$, so it leaves open a practical accuracy-speed dial: smaller $M$ for faster inference, larger $M$ for a closer kernel approximation, with the optimal value likely dataset-dependent.
  • The same random-Fourier-feature substitution should apply to hierarchical Dirichlet process variants of GP-HSMM, potentially carrying similar speedups to those used for animal behavior analysis.
  • A formal concentration bound on the kernel approximation error would let a user set $M$ from a desired normalized Hamming distance tolerance rather than by trial and error.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper proposes RFF-GP-HSMM, an unsupervised time-series segmentation method that replaces the Gaussian process emission of GP-HSMM with Bayesian linear regression on random Fourier features. This replaces the inversion of an N×N kernel matrix by the inversion of an M×M matrix, with M set to 20. Using CMU motion-capture data (three sequences duplicated to up to 39,200 frames), the paper reports normalized Hamming distance 0.351 for GP-HSMM versus 0.357 for RFF-GP-HSMM, and a maximum speed-up of approximately 278×. Inference is performed with a blocked Gibbs sampler using forward filtering-backward sampling, and the implementation is promised to be released on GitHub.

Significance. If the claims hold, the paper makes GP-HSMM practical for large-scale and near-real-time segmentation, which is a meaningful contribution given the method's previous cubic scaling. The complexity argument is sound in principle and the timing results are consistent with the expected algorithmic improvement. The paper also provides a concrete algorithm and promises code, which aids reproducibility. However, the evidence for 'comparable accuracy' is currently narrow (one dataset, best-of-10 selection, no variance reporting) and the segment-likelihood computation in Eq. (28) requires clarification. These issues are fixable and do not invalidate the core speed-up result, but they must be addressed before the accuracy claims can be fully trusted.

major comments (3)
  1. [§III-B.3, Eq. (28)] The forward probability in Eq. (28) multiplies pointwise predictive densities p(s_{n,t'}|t', X_c, t_c), but the Bayesian linear regression model of Eqs. (22)-(26) implies a joint predictive distribution over a candidate segment with covariance β^{-1}I + ΦΣ_cΦ^T, so the off-diagonal terms are generally nonzero. The product in Eq. (28) is therefore a pseudo-likelihood rather than the exact segment likelihood of the stated model. The paper should state this explicitly and, importantly, clarify whether the GP-HSMM baseline in Table II uses the same pseudo-likelihood; otherwise the accuracy comparison may reflect a change in model, not only the RFF approximation.
  2. [§IV-B, Table II] The accuracy evaluation uses a single dataset (three motion sequences from Subject 14), reports no standard deviation or error bars, and selects the best of 10 initializations. The difference between 0.351 and 0.357 is small, but without repeated-run variability or a statistical test the claim of 'comparable accuracy' is not established beyond this one setting. Please report mean and standard deviation over initializations, include additional subjects or datasets, and consider a significance test or confidence intervals.
  3. [§IV-A, M=20] The number of random features M is the key approximation parameter, yet the paper provides no justification for choosing M=20 and no sensitivity analysis. If the approximation error grows for more complex motions or larger datasets, the uniform 'comparable accuracy' claim would fail. Please add an M-sweep showing segmentation accuracy and runtime for several values of M (e.g., 5, 10, 20, 50, 100, 200) on at least one dataset.
minor comments (3)
  1. [Algorithm 1, line 13] In the backward sampling step, the notation p(c_{j+1}|c) is confusing; Eq. (31) suggests that p(c_{j-1}|c) is intended. Please align the algorithm and the equation.
  2. [§IV-B] The text says the three sequences were 'duplicated 10 times, resulting in a total of 30 sequences' and then refers to 10 trials with different initial values. Please clarify the relationship between the data duplication and the number of trials, since these appear to be independent experimental choices.
  3. [Eq. (14)] The derivation of the integral over b is correct but would be easier to follow if the factor 1/(2π) from p(b) were shown explicitly in the evaluation of the integral.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the speed-up is measured, the RFF approximation is standard external theory, and the accuracy comparison is between two implemented models.

full rationale

The paper's central claims are (i) RFF eliminates the N_c x N_c kernel inversion by replacing the GP prior with Bayesian linear regression on M random Fourier features, and (ii) the resulting implementation is about 278x faster with comparable Hamming distance. Neither claim is circular. Equations (22)-(26) are the standard closed-form Bayesian linear regression posterior, and the Fourier-feature approximation in Eqs. (8)-(21) is the external Rahimi-Recht construction; no parameter is fitted to the evaluation data and then reported as a prediction. The speed-up is a measured runtime comparison (Table III), and the accuracy score is an independent comparison against ground-truth labels (Table II). The authors' self-citations, principally [7] for the GP-HSMM baseline, are used as the method being approximated or as related work, not as the justification that RFF preserves accuracy; the comparison is performed in this paper. The product form in Eq. (28) is a pseudo-likelihood/segmentation scoring choice rather than a circular reduction: it is not the same quantity being predicted, and no fitted parameter is renamed as a prediction. Thus no significant circularity is present.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The method relies on standard RFF theory and Bayesian linear regression, where the approximation error is controlled by the hyperparameter M. The paper does not analyze this error or justify the choice M=20. No new entities are introduced.

free parameters (5)
  • M (number of random features) = 20
    Set to 20 with no sensitivity analysis; controls the fidelity of the kernel approximation.
  • λ (mean segment length) = 20
    Poisson segment length parameter, taken from GP-HSMM defaults; not tuned in this paper.
  • Kmin, Kmax (segment length bounds) = 15, 30
    Bounds on segment length; chosen as in prior work.
  • Number of blocked Gibbs iterations = 5
    Stopped at 5 iterations with no convergence diagnostics.
  • Observation noise β and prior variance ψ = not specified
    Hyperparameters in the Bayesian linear regression formulas (Eq. 25) but their values are not reported.
assumptions (5)
  • standard math RFF approximates the RBF kernel with finite-dimensional features (Bochner's theorem)
    Used to justify replacing the GP with Bayesian linear regression; standard result with a known convergence rate.
  • standard math Bayesian linear regression formulas for predictive distribution
    Equations (22)-(26) are standard conjugacy results for Gaussian likelihood with Gaussian prior.
  • domain assumption GP-HSMM generative model
    Assumes motions are generated as repeated segments with class-specific emission distributions and Poisson-duration HSMM; inherited from [7].
  • domain assumption Blocked Gibbs sampler reaches typical set in 5 iterations
    Inference uses 5 rounds with no convergence check; results may depend on initialization.
  • domain assumption Output dimensions are independent given the class
    Equation (27) factorizes the likelihood over output dimensions, ignoring correlations between hand and foot movements.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Scalable Unsupervised Segmentation via Random Fourier Feature-based Gaussian Process." pith.science (2026). https://pith.science/paper/YK4YVAAY

@misc{pith2026250710632,
  author       = {Pith},
  title        = {Pith review of: Scalable Unsupervised Segmentation via Random Fourier Feature-based Gaussian Process},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YK4YVAAY}},
  note         = {Machine review of arXiv:2507.10632}
}
read the original abstract

In this paper, we propose RFF-GP-HSMM, a fast unsupervised time-series segmentation method that incorporates random Fourier features (RFF) to address the high computational cost of the Gaussian process hidden semi-Markov model (GP-HSMM). GP-HSMM models time-series data using Gaussian processes, requiring inversion of an N times N kernel matrix during training, where N is the number of data points. As the scale of the data increases, matrix inversion incurs a significant computational cost. To address this, the proposed method approximates the Gaussian process with linear regression using RFF, preserving expressive power while eliminating the need for inversion of the kernel matrix. Experiments on the Carnegie Mellon University (CMU) motion-capture dataset demonstrate that the proposed method achieves segmentation performance comparable to that of conventional methods, with approximately 278 times faster segmentation on time-series data comprising 39,200 frames.

Figures

Figures reproduced from arXiv: 2507.10632 by the authors.

Figure 1
Figure 1. Graphical model of the RFF-GP-HSMM. Segment xj , corresponding to class cj , is generated using linear regression with weights wc: xj ∼ p(x|wcj ). (4) The observed time-series data S are generated by concate￾nating the segments xj . However, simple linear regression alone cannot adequately capture complex time-series patterns. To address this, RFF-GP-HSMM uses linear regression based on basis functions derived from … view at source ↗
Figure 2
Figure 2. Motions included in exercise motion: (a) jumping jack, [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Computation time of GP-HSMM and RFF-GP-HSMM. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: highlights only the computation times for RFF-GP￾HSMM extracted from [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references · 20 canonical work pages

  1. [1]

    Joint modeling of multiple related time series via the beta process,

    E. B. Fox, E. B. Sudderth, M. I. Jordan, and A. S. Willsky, “Joint modeling of multiple related time series via the beta process,” 2011

    work page 2011

  2. [2]

    Autoplait: Automatic mining of co-evolving time sequences,

    Y . Matsubara, Y . Sakurai, and C. Faloutsos, “Autoplait: Automatic mining of co-evolving time sequences,” in Proceedings of the 2014 ACM SIGMOD international conference on Management of data , 2014, pp. 193–204

    work page 2014

  3. [3]

    Unsupervised learning and segmentation of complex activities from video,

    F. Sener and A. Yao, “Unsupervised learning and segmentation of complex activities from video,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition , 2018, pp. 8368–8376

    work page 2018

  4. [4]

    Weakly supervised action labeling in videos under ordering constraints,

    P. Bojanowski, R. Lajugie, F. Bach, I. Laptev, J. Ponce, C. Schmid, and J. Sivic, “Weakly supervised action labeling in videos under ordering constraints,” in Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13. Springer, 2014, pp. 628–643

    work page 2014

  5. [5]

    Connectionist temporal modeling for weakly supervised action labeling,

    D.-A. Huang, L. Fei-Fei, and J. C. Niebles, “Connectionist temporal modeling for weakly supervised action labeling,” in Computer Vision– ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11–14, 2016, Proceedings, Part IV 14 . Springer, 2016, pp. 137–153

    work page 2016

  6. [6]

    Weakly supervised action learning with rnn based fine-to-coarse modeling,

    A. Richard, H. Kuehne, and J. Gall, “Weakly supervised action learning with rnn based fine-to-coarse modeling,” in Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, 2017, pp. 754– 763

    work page 2017

  7. [7]

    Segmenting continuous motions with hidden semi-markov models and gaussian processes,

    T. Nakamura, T. Nagai, D. Mochihashi, I. Kobayashi, H. Asoh, and M. Kaneko, “Segmenting continuous motions with hidden semi-markov models and gaussian processes,” Frontiers in neurorobotics , vol. 11, p. 67, 2017

    work page 2017

  8. [8]

    Unsupervised work behavior analysis using hierarchical probabilistic segmentation,

    I. Saito, T. Nakamura, T. Hatta, W. Fujita, S. Watanabe, and S. Miwa, “Unsupervised work behavior analysis using hierarchical probabilistic segmentation,” in IECON 2023- 49th Annual Conference of the IEEE Industrial Electronics Society , 2023, pp. 1–6

    work page 2023

Show all 24 references
  1. [9]

    Unsupervised decom- position of natural monkey behavior into a sequence of motion motifs,

    K. Mimura, J. Matsumoto, D. Mochihashi, T. Nakamura, H. Nishijo, M. Higuchi, T. Hirabayashi, and T. Minamimoto, “Unsupervised decom- position of natural monkey behavior into a sequence of motion motifs,” Communications Biology, vol. 7, no. 1, p. 1080, 2024

    2024

  2. [10]

    Emergence of continuous signals as shared symbols through emergent communication,

    I. Saito, T. Nakamura, A. Taniguchi, T. Taniguchi, Y . Hayamizu, and S. Zhang, “Emergence of continuous signals as shared symbols through emergent communication,” in 2024 IEEE International Conference on Development and Learning (ICDL) , 2024, pp. 1–6

    2024

  3. [11]

    Multi-step motion learning by combining learning-from-demonstration and policy-search,

    Y . Mo, H. Sasaki, T. Matsubara, and K. Yamazaki, “Multi-step motion learning by combining learning-from-demonstration and policy-search,” Advanced Robotics , vol. 37, no. 9, pp. 560–575, 2023. [Online]. Available: https://doi.org/10.1080/01691864.2022.2163187 2https://github....

    2023

  4. [12]

    Random features for large-scale kernel machines,

    A. Rahimi and B. Recht, “Random features for large-scale kernel machines,” in Advances in Neural Information Processing Systems , J. Platt, D. Koller, Y . Singer, and S. Roweis, Eds., vol. 20. Curran Associates, Inc., 2007

    2007

  5. [13]

    Fine- grained action recognition in assembly work scenes by drawing attention to the hands,

    T. Kobayashi, Y . Aoki, S. Shimizu, K. Kusano, and S. Okumura, “Fine- grained action recognition in assembly work scenes by drawing attention to the hands,” in 2019 15th International Conference on Signal-Image Technology Internet-Based Systems (SITIS) , 2019, pp. 440–446

    2019

  6. [14]

    Tempo- ral convolutional networks for action segmentation and detection,

    C. Lea, M. D. Flynn, R. Vidal, A. Reiter, and G. D. Hager, “Tempo- ral convolutional networks for action segmentation and detection,” in proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017, pp. 156–165

    2017

  7. [15]

    End-to-end learning of action detection from frame glimpses in videos,

    S. Yeung, O. Russakovsky, G. Mori, and L. Fei-Fei, “End-to-end learning of action detection from frame glimpses in videos,” in Proceedings of the IEEE conference on computer vision and pattern recognition , 2016, pp. 2678–2687

    2016

  8. [16]

    Spatio-temporal channel correlation networks for action classification,

    A. Diba, M. Fayyaz, V . Sharma, M. M. Arzani, R. Yousefzadeh, J. Gall, and L. Van Gool, “Spatio-temporal channel correlation networks for action classification,” in Proceedings of the European Conference on Computer Vision (ECCV) , 2018, pp. 284–299

    2018

  9. [17]

    Temporal segment transformer for action segmentation,

    Z. Liu, L. Wang, D. Zhou, J. Wang, S. Zhang, Y . Bai, E. Ding, and R. Fan, “Temporal segment transformer for action segmentation,” arXiv preprint arXiv:2302.13074, 2023

    2023 arXiv

  10. [18]

    Trans- formers in time series: A survey,

    Q. Wen, T. Zhou, C. Zhang, W. Chen, Z. Ma, J. Yan, and L. Sun, “Trans- formers in time series: A survey,” arXiv preprint arXiv:2202.07125 , 2022

    2022 arXiv

  11. [19]

    Long- term forecasting with tide: Time-series dense encoder,

    A. Das, W. Kong, A. Leach, S. Mathur, R. Sen, and R. Yu, “Long- term forecasting with tide: Time-series dense encoder,” arXiv preprint arXiv:2304.08424, 2023

    2023 arXiv

  12. [20]

    Sequence pattern extraction by segmenting time series data using gp-hsmm with hierarchical dirichlet process,

    M. Nagano, T. Nakamura, T. Nagai, D. Mochihashi, I. Kobayashi, and M. Kaneko, “Sequence pattern extraction by segmenting time series data using gp-hsmm with hierarchical dirichlet process,” in 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) , 20...

    2018

  13. [21]

    Bayesian non-linear latent variable modeling via random fourier features,

    M. M. Zhang, G. W. Gundersen, and B. E. Engelhardt, “Bayesian non-linear latent variable modeling via random fourier features,” arXiv preprint arXiv:2306.08352, 2023

    2023 arXiv

  14. [22]

    Preventing model col- lapse in gaussian process latent variable models,

    Y . Li, Z. Lin, F. Yin, and M. M. Zhang, “Preventing model col- lapse in gaussian process latent variable models,” arXiv preprint arXiv:2404.01697, 2024

    2024 arXiv

  15. [23]

    Scalable hybrid hmm with gaussian process emission for sequential time-series data clustering,

    Y . Jung and J. Park, “Scalable hybrid hmm with gaussian process emission for sequential time-series data clustering,” arXiv preprint arXiv:2001.01917, 2020

    2001 arXiv

  16. [24]

    A high-speed method of segmenting human body motions with regular time interval sensor data based on gaussian process hidden semi- markov model,

    Y . Sasaki, M. Kawamura, and Y . Nakamura, “A high-speed method of segmenting human body motions with regular time interval sensor data based on gaussian process hidden semi- markov model,” IFAC-PapersOnLine, vol. 56, no. 2, pp. 9691– 9696, 2023, 22nd IFAC World Congress. [Onl...

    2023

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.