Feature-based generators for time series data

ABSTRACT

A variety of interesting domains, such as financial markets, weather systems, herding phenomena, etc., are characterized by highly complex time series datasets which defy simple description and prediction. The generation of input data for simulators operating in these domains is challenging because process description usually involves high-dimensional joint distributions that are either too complex or simply unavailable. In such applications, a standard approach is to drive simulators with (historical) trace-data, along with facilities for real-time interaction and synchronization. But, limited input data, or conversely, abundant but low-fidelity random data, limits the usefulness and quality of the results. With a view to generating high-fidelity, random input for such applications, we propose a methodology which uses the original data, as a template, to generate candidate datasets, to finally accept only those datasets which resemble the template, based upon parameterized features. We demonstrate the methodology with some early experimental results.

REFERENCES

• 1: Aho, A. V., R. Sethi, and J. D. Ullman. 1986. Compilers. Boston, MA: Addison-Wesley.
• 2: J. Glenn Brookshear, Theory of computation: formal languages, automata, and complexity, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1989
• 3: Fink, E. and K. Pratt. 2003. Indexing of compressed time series. In Data mining in time series databases, ed. M. Last, A. Kandel, and H. Bunke, 43--65. Singapore: World Scientific.
• 4: Friedman, M., and A. Kandel. 1999. Introduction to pattern recognition: Statistical, structural, neural and fuzzy logic approaches. Series in Machine Perception and Artifical Intelligence., Vol. 32. Singapore: World Scientific.
• 5: Fu, K. S. 1982. Syntactic pattern recognition and applications. Englewood Cliffs, NJ:Prentice Hall.
• 6: Martin Gavrilov , Dragomir Anguelov , Piotr Indyk , Rajeev Motwani, Mining the stock market (extended abstract): which measure is best?, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.487-496, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347189]
• 7: Jurafsky, D., C. Wooters, J. Segal, A. Stolcke, E. Fosler, G. Tajchman, and N. Morgan. 1995. Using a stochastic context-free grammar as a language model for speech recognition. In Proceedings of the 1995 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 189--192. Piscataway, NJ:Institute of Electrical and Electronics Engineers.
• 8: Michael Kearns , Luis Ortiz, The Penn-Lehman Automated Trading Project, IEEE Intelligent Systems, v.18 n.6, p.22-31, November 2003 [doi>10.1109/MIS.2003.1249166]
• 9: Last, M., Y. Klein, and A. Kandel. 2001. Knowledge discovery in time series databases. IEEE Transactions on Systems, Man, and Cybernetics, 31B(1):160--169.
• 10: Averill M. Law , David M. Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1999
• 11: Malkiel, B. G. 2004. A random walk down wall street. 8th ed. New York, NY: W. W. Norton & Company.
• 12: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 13: Judea Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 14: David V. Pynadath , Michael P. Wellman, Generalized Queries on Probabilistic Context-Free Grammars, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.1, p.65-77, January 1998 [doi>10.1109/34.655650]
• 15: Ramos, J. R., and V. Rego. 2005. Financial data and information. Report in preparation. Technical report CSD, Department of Computer Science, Purdue University.
• 16: Sakakibara, Y., M. Brown, R. Underwood, I. S. Mian, and D. Haussler. Stochastic context-free grammars for modeling RNA. In Proceedings of the 27th Hawaii International Conference on System Sciences, 284--283. Honolulu: IEEE Computer Society Press.
• 17: Steedman, M. J. 1984. A generative grammar for jazz chord sequences. Music Perception, 2(1):52--77.
• 18: Andreas Stolcke , Stephen M. Omohundro, Inducing Probabilistic Grammars by Bayesian Model Merging, Proceedings of the Second International Colloquium on Grammatical Inference and Applications, p.106-118, September 21-23, 1994
• 19: Sullivan, R., A. Timmermann, and H. White. 1998. Data snooping, technical trading, rule performance and the bootstrap. Financial Markets Group, discussion paper 303. London, UK:London School of Economics.