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

点击翻译按钮获取中文摘要

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.