ML-augmented algorithms utilize predictions to achieve performance beyond
their worst-case bounds. Producing these predictions might be a costly
operation -- this motivated Im et al. '22 to introduce the study of algorithms
which use predictions parsimoniously. We design parsimonious algorithms for
caching and MTS with action predictions, proposed by Antoniadis et al. '20,
focusing on the parameters of consistency (performance with perfect
predictions) and smoothness (dependence of their performance on the prediction
error). Our algorithm for caching is 1-consistent, robust, and its smoothness
deteriorates with the decreasing number of available predictions. We propose an
algorithm for general MTS whose consistency and smoothness both scale linearly
with the decreasing number of predictions. Without the restriction on the
number of available predictions, both algorithms match the earlier guarantees
achieved by Antoniadis et al. '20.

使用预测的 ML 增强算法对缓存和 MTS 进行研究，提出了具有一致性和平滑性参数的节俭算法，能够在预测准确性下提高性能。

减少预测数量的缓存和 MTS 算法

Algorithms for Caching and MTS with reduced number of predictions

Multivariate time series (MTS) arise when multiple interconnected sensors
record data over time. Dealing with this high-dimensional data is challenging
for every classifier for at least two aspects: First, an MTS is not only
characterized by individual feature values, but also by the interplay of
features in different dimensions. Second, this typically adds large amounts of
irrelevant data and noise. We present our novel MTS classifier WEASEL+MUSE
which addresses both challenges. WEASEL+MUSE builds a multivariate feature
vector, first using a sliding-window approach applied to each dimension of the
MTS, then extracts discrete features per window and dimension. The feature
vector is subsequently fed through feature selection, removing
non-discriminative features, and analysed by a machine learning classifier. The
novelty of WEASEL+MUSE lies in its specific way of extracting and filtering
multivariate features from MTS by encoding context information into each
feature. Still the resulting feature set is small, yet very discriminative and
useful for MTS classification. Based on a popular benchmark of 20 MTS datasets,
we found that WEASEL+MUSE is among the most accurate classifiers, when compared
to the state of the art. The outstanding robustness of WEASEL+MUSE is further
confirmed based on motion gesture recognition data, where it out-of-the-box
achieved similar accuracies as domain-specific methods.

本研究提出了一种新型的 MTS 分类器 WEASEL + MUSE，通过在每个 MTS 的维度上使用滑动窗口方法提取离散特征，并基于特征选择构建一个小但具有区分性和 MTS 分类有用的特征集。实验表明，WEASEL + MUSE 是一种准确率最高的 MTS 分类器之一，具有良好的鲁棒性。