Page 67 - profile2014.indd

研究員
呂及人 Chi-Jen Lu

Research Fellow
Ph.D., Computer Science, University of Massachusetts at Amherst
Tel: +886-2-2788-3799 ext. 1820 Fax: +886-2-2782-4814
Email: cjlu@iis.sinica.edu.tw
http://www.iis.sinica.edu.tw/pages/cjlu

Research Description ● Associate Research Fellow, IIS,
Academia Sinica (2003/10 -
Many situations in daily life require us to make repeated decisions before knowing the 2008/11)
resulting outcomes. This motivates the study of the so-called online decision problem, in ● Assistant Research Fellow, IIS, Ac-
which one must iteratively choose an action and then receive some corresponding loss for ademia Sinica (1999/8 - 2003/10)
a number of rounds. It is a fundamental problem in the area of machine learning, and it has ● Assistant Professor, CSIE, National
found surprising applications in several other areas as well. For this problem, we obtained Chi-Nan University (1999/2 -
the following results. 1999/7)
● M.S., CSIE, National Taiwan Uni-
First, we identi ed natural scenarios in which online algorithms with better performances versity (1990)

can be designed. Second, we transformed the powerful boosting algorithm in machine
learning from the traditional batch setting into this online setting. Finally, we discovered ● B.S., CSIE, National Taiwan Univer-
new applications of this problem in other areas, such as game theory and complexity theo- sity (1988)
ry, which again demonstrate the importance of this problem.

在日常生活中，我們時常必須不斷在未知的環境中作決定，並為此付出代價。這可被抽象化為所謂的「線上決策問
題」，而我們希望能為此問題設計出好的線上演算法，可以從過去的歷史中學習，而能在未來做出好的決定。此問
題除了是機器學習領域中的一個重要問題，在一些其他領域也有令人意料之外的應用。對此問題，我們刻畫出一些
自然而常見的環境條件，並在這些條件下設計出更有效率的線上演算法。此外，我們也將機器學習中重要的強化學
習演算法，由傳統批次的作業方式，成功的轉化成線上的運作方式。最後，我們將一些賽局理論與複雜度理論中的
問題，轉化成某種線上決策問題，使得線上決策問題的成果可以用來解決這些問題。

Publications

1. Shang-Tse Chen, Hsuan-Tien Lin, and Chi-Jen Lu. Boosting 7. Chia-Jung Lee, Chi-Jen Lu and Shi-Chun Tsai. Extracting
with online binary learners for the multiclass bandit problem. computational entropy and learning noisy linear functions.
st
In Proceedings of the 31 International Conference on Ma- IEEE Transaction on Information Theory, 57(8), pp. 5485-
chine Learning (ICML), 2014. 5496, 2011.
2. Po-An Chen and Chi-Jen Lu. Generalized mirror descents 8. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. Complexity

in congestion games with splittable flows. In proceedings of of hard-core set proofs. Computational Complexity, 20(1), pp.
th
the 13 International Conference on Autonomous Agents and 145 – 171, 2011.
Multiagent Systems (AAMAS), 2014.
9. Chi-Jen Lu and Wei-Fu Lu. Making online decisions with
nd
3. Chao-Kai Chiang, Chia-Jung Lee, and Chi-Jen Lu. Beating bounded memory. In Proceedings of the 22 International
bandits in gradually evolving worlds. In Proceedings of the Conference on Algorithmic Learning Theory (ALT), 2011.
th
26 Conference on Learning Theory (COLT), 2013.
10. Chia-Jung Lee, Chi-Jen Lu, and Shi-Chun Tsai. Deterministic
4. Shang-Tse Chen, Hsuan-Tien Lin, and Chi-Jen Lu. An online extractors for independent-symbol sources. IEEE Transaction

boosting algorithm with theoretical justifications. In Proceed- on Information Theory, 56(12), pp. 6501 – 6512, 2010.
th
ings of the 29 International Conference on Machine Learning
(ICML), 2012.
5. Chao-Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad
Mahdavi, Chi-Jen Lu, Rong Jin and Shenghuo Zhu. Online
optimization with gradual variations. In Proceedings of the
th
25 Conference on Learning Theory (COLT), 2012.
6. Chi-Jen Lu. Hitting set generators for sparse polynomials over

any finite fields. In Proceedings of the 27 Annual IEEE Con-
th

ference on Computational Complexity (CCC), 2012.

67