CAREER: Optimization Based Methods for Robust Pattern Recognition in Time-Series Data

本研究提出了新的数学和算法工具，用于识别模式和有效挖掘时间序列数据，即一系列数据点，通常在连续的时间瞬间以均匀的时间间隔间隔测量。各种各样的现实世界数据源，如语音和音频、生物医学信号、医疗记录、网络流量和股票市场数据等，都表现为时间序列，它们的分析对政府和行业都有重大意义。数字革命加剧了这类数据源的爆炸式增长，即互联网上大量的音频-视频流，电子数据库中存储了大量按时间顺序排列的卫生保健记录，以及由于传感技术的进步而不断产生新的时间序列数据。自动化的软件工具可以在大的时间序列序列中找到模式，帮助快速和可扩展的检索，并对大的时间序列集合进行分类，因此是非常可取的。建议的研究是开发这样的软件（算法）工具，特别关注鲁棒性和可扩展性。鲁棒性问题指的是对人类消费者具有“相同吸引力”的时间序列，例如同一首歌曲/视频的不同版本，不一定是数字相同的。因此，需要能够承受不改变时间序列内容本质的扭曲的强大技术。可伸缩性要求模式匹配技术快速且易于实现，以便部署解决方案来挖掘大型集合。此外，为了培养下一代电气工程和计算机科学方面的工程师，该项目包括一个强大的教育组成部分。这个教育组件的核心是一个寓教于乐的游戏，在这个游戏中，人类玩家，即具有不同学术准备水平的学生（高中，本科和研究生），在视频盗版挑战中与计算机算法竞争。这款游戏旨在使学习过程更具互动性，尤其是对本科生而言。为新兴应用挖掘时间序列数据的一个严重的实际挑战是承受扭曲的能力——通常是在噪声、幅度和/或时间缩放和其他杂项操作下观察到“相同的底层”时间序列的实例。许多现有的时间序列比较技术不能实现失真鲁棒性，而那些能够实现的技术通常需要大量的计算成本。此外，现有的算法技术只能在直观的、通常是启发式的水平上控制时间序列特征的关键属性，如鲁棒性和唯一性。提出的研究主张明智地选择时间序列极值，旨在打破时间序列特征提取和比较的计算效率与对扭曲的鲁棒性之间的传统权衡。与现有方法不同，现有方法采用从直觉“启发”的预处理时间序列滤波器，在成本函数的意义上提出了滤波器的显式优化，以捕获关键特征属性，如提取的极值的鲁棒性和唯一性。最优极值提取将在两种不同的设置中进行研究：a.)在优化中使用示例训练时间序列的确定性框架，b.)在时间序列上使用随机模型的统计框架。各种相关的子问题也出现了，即：a)与图像处理和视觉中的边缘检测问题的联系，b)时间序列极值的编码和比较，以及c)扩展到在时间序列上的非线性操作下寻找鲁棒极值。研究计划是将算法工具的发展与两个现实世界的应用并列：1)多媒体指纹识别和2)生物医学时间序列分析。此外，软件工具，即寓教于乐的游戏将开发基于这些应用程序，这将在加强PI的研究和课堂教学中发挥关键作用。研究成果的传播将通过在主要期刊和会议上发表的文章以及在线MATLAB软件工具箱来完成。

This research proposes new mathematical and algorithmic tools for identifying patterns in and effectively mining time-series data, i.e. a sequence of data points, measured typically at successive time instantsspaced at uniform time intervals. A large variety of real-world data sources such as speech and audio,biomedical signals, health care records, network-traffic and stock market data etc. manifest as time-seriesand their analysis is of significant interest to both government and industry. The explosion of such data sources has only been exacerbated by the digital revolution, viz. the generous amount of audio-videostreams on the internet, the storage of large amounts of chronological health care records in electronicdatabases and the continuous generation of new time-series data from advances in sensing. Automated softwaretools that can find patterns in a large time-series sequence, help in fast and scalable retrieval, andcategorize large time-series collections are hence highly desirable. The proposed research is in developing such software (algorithmic)tools with a particular focus on robustness and scalability. The problem of robustness refers to the fact that time-series that may have the "same appeal" to a human consumer, e.g. different versions of the same song/video, may not necessarily be digitally identical. Hence, robust techniques are needed that can withstand distortions which do not change the essence of the time-series content. Scalability requires that the pattern-matching techniques be fast and easy to implement, so thatthe solutions can be deployed to mine large collections. Further, to prepare the next generation ofengineers in electrical engineering and computer science, the project includes a strong educationalcomponent. At the heart of this educational component is an edutainment game where a human player, i.e.students with varying levels of academic preparation (high-school, undergraduate and graduate), compete against a computer algorithm in a video piracy challenge. The game is aimed at making the learning process more interactive, particularly for undergraduate students.A serious practical challenge in mining time-series data for emerging applications is the ability towithstand distortions - that is often instances of the "same underlying" time series are observedunder noise, amplitude and/or time scaling and other miscellaneous operations. Many existingtechniques for time-series comparisons do not enable distortion robustness and the ones that do,often come at a substantial computational cost. Further, existing algorithmic techniques enablecontrol of key properties of time-series features such as robustness and uniqueness only at anintuitive, often heuristic level. The proposed research advocates judicious selection of time-seriesextrema and aims to break the classical trade-off between computational efficiency in time-seriesfeature extraction and comparison vs. enabling robustness to distortions. Unlike existing methods,which employ pre-processing time-series filters "inspired" from intuition, explicit optimization of thefilter is proposed in the sense of cost functions that capture key feature attributes such as robustnessand uniqueness of the extracted extrema. Optimal extrema extraction will be investigated in twodifferent setups: a.) a deterministic framework where example training time-series are used in theoptimization, and b.) a statistical framework where stochastic models on time-series are used. Avariety of related sub-problems also emerge, namely: a.) connections to edge detection problemsin image processing and vision, b.) encoding and comparisons of time-series extrema, and c.)extensions to finding robust extrema under non-linear operations on the time-series. The researchplan is to juxtapose the development of the algorithmic tools with two real-world applications: 1.)multimedia fingerprinting, and 2.) bio-medical time series analysis. Additionally, software toolsnamely edutainment games will be developed based on these applications which will play a crucialrole in enhancing the PI's research and classroom teaching. Dissemination of research results will bedone via articles in leading Journals and conferences, and via online MATLAB software toolboxes.