Yunsong Guo
PhD
Department of Computer Science
Ithaca, NY 14853
I was a PhD
student at Cornell University from 2005-2010. My research focus is in Machine Learning and
Combinatorial
Optimization.
During my time at Cornell, I have been blessed to have an amazing thesis committee, including Professor Carla Gomes, Thorsten Joachims, David Williamson, Bart Selman and Dexter Kozen
Here is my PhD dissertation titled Supervised Learning with Implicit Preferences and Constraints.
I graduated in August 2010 and joined Goldman Sachs thereafter to work in the inspiring world of Algorithmic Trading.
A resume (to be updated).
List of Refereed Conference
and Journal Publications
18. Yunsong Guo, Carla Gomes, Learning optimal subsets with implicit user preferences, The 21st International Joint Conference on Artificial Intelligence (IJCAI), 2009; a preliminary version also appeared in NIPS08 workshop on structured input and structured output.
We study the problem of learning an optimal subset from a larger ground set of items, where the optimality criterion is defined by an unknown preference function. We model the problem as a discriminative structural learning problem and solve it using a Structural Support Vector Machine (SSVM) that optimizes a "set accuracy" performance measure representing set similarities. Our approach departs from previous approaches since we do not explicitly learn a pre-defined preference function. Experimental results on both a synthetic problem domain and a real-world face image subset selection problem show that our method significantly outperforms previous learning approaches for such problems.
17. Yunsong Guo, Carla Gomes, Ranking structured documents: a large margin based approach for patent prior art search , The 21st International Joint Conference on Artificial Intelligence (IJCAI), 2009
We propose an approach for automatically ranking structured documents applied to patent prior art search. Our model, SVM Patent Ranking (SVM_PR) incorporates margin constraints that directly capture the specificities of patent citation ranking. Our approach combines patent domain knowledge features with meta-score features from several different general Information Retrieval methods. The training algorithm is an extension of the Pegasos algorithm with performance guarantees, effectively handling hundreds of thousands of patent-pair judgements in a high dimensional feature space. Experiments on a homogeneous essential wireless patent dataset show that SVM_PR performs on average 30%-40% better than many other state-of-the-art general-purpose Information Retrieval methods in terms of the NDCG measure at different cut-off positions.
16. Nam Nguyen, Yunsong Guo, Metric learning: a support vector machine approach, The 18th European Conference on Machine Learning (ECML/PKDD), 2008.
In this paper, we address the metric learning problem utilizing a margin-based approach. Our metric learning problem is formulated as a quadratic semi-definite programming problem (QSDP) with local neighborhood constraints, which is based on the Support Vector Machine (SVM) framework. The local neighborhood constraints ensure that examples of the same class are separated from examples of di erent classes by a margin. In addition to providing an efficient algorithm to solve the metric learning problem, extensive experiments on various data sets show that our algorithm is able to produce a new distance metric to improve the performance of the classical K-nearest neighbor (KNN) algorithm on the classi cation task. Our performance is always competitive and often significantly better than other state-of-the-art metric learning algorithms.
15. Yunsong Guo, Yanzhi Li, Andrew Lim, Brian Rodrigues, Tariff concessions in production sourcing, European Journal of Operational Research (EJOR), 187(2) , 2008.
In this paper, we study a multi-stage production sourcing problem where tariff concessions can be exploited at the firm level using free trade agreements between countries. To solve the problem, an algorithm which embeds a very large-scale neighborhood (VSLN) search into a simulated annealing framework is developed. A numerical study is conducted to verify the effectiveness of the solution approach.
14. Yunsong Guo, Bart Selman, ExOpaque: a framework to explain opaque machine learning models using inductive logic programming, The 19th IEEE international Conference on Tools with Artificial Intelligence (ICTAI), 2007.
In this paper we developed an Inductive Logic Programming (ILP) based framework ExOpaque that is able to extract a set of Horn clauses from an arbitrary opaque machine learning model, to describe the behavior of the opaque model with high fidelity while maintaining the simplicity of the Horn clauses for human interpretations. In addition, traditional ILP systems often utilize a set of background knowledge to make accurate predictions. We also proposed a new method to use generated artificial training examples and high-accuracy opaque models to boost the prediction accuracy of an ILP system when background knowledge is absent and hard to obtain.
In this paper, we survey the current state-ofart models for structured learning problems, including Hidden Markov Model (HMM), Conditional Random Fields (CRF), Averaged Perceptron (AP), Structured SVMs (SVMstruct), Max Margin Markov Networks (M3N), and an integration of search and learning algorithm (SEARN). With all due tuning efforts of various parameters of each model, on the data sets we have applied the models to, we found that SVMstruct enjoys better performance compared with the others. In addition, we also propose a new method which we call the Structured Learning Ensemble (SLE) to combine these structured learning models. Empirical results show that our SLE algorithm provides more accurate solutions compared with the best results of the individual models.
12. Yunsong Guo, Andrew Lim, Brian Rodrigues, Shanhu Yu, Machine scheduling performance with maintenance and failure, Mathematical And Computer Modelling (MCM), 45(9-10), 2007.
In manufacturing control, machine scheduling research has mostly dealt with problems either without maintenance or with deterministic maintenance when no failure can occur. This can be unrealistic in practical settings. In this work, an experimental model is developed to evaluate the effect of corrective and preventive maintenance schemes on scheduling performance in the presence machine failure where the scheduling objective is to minimize schedule duration. We show that neither scheme is clearly superior, but that the applicability of each depends on several system parameters as well as the scheduling environment itself. Further, we show that parameter values can be chosen for which preventive maintenance does better than corrective maintenance. The results provided in this study can be useful to practitioners and to system or machine administrators in manufacturing and elsewhere.
11. Yunsong Guo, Andrew Lim, Brian Rodrigues and Liang Yang, Minimizing the makespan for unrelated parallel machines, International Journal on Artificial Intelligence Tools (IJAIT), 16(3), 2007.
In this paper, we study the unrelated parallel machine problem for minimizing the makespan, which is NP-hard. We used Simulated Annealing (SA) and Tabu Search (TS) with Neighborhood Search (NS) based on the structure of the problem. We also used a modi ed SA algorithm, which gives better results than the traditional SA and developed an e ective heuristic for the problem: Squeaky Wheel Optimization (SWO) hybrid with TS. Experimental results average 2.52% from the lower bound and are within acceptable timescales improving current best results for the problem.
10. Yunsong Guo, Andrew Lim, Brian Rodrigues, Jiqing Tang, Using a lagrangian heuristic for a combinatorial auction problem, International Journal on Artificial Intelligence Tools (IJAIT), 15(3), 2006.
Combinatorial auctions allow bidders to bid for items leading to more efficient allocations, but determining winners in auctions is NP-complete. In this work, a simple yet e®ective Lagrangian relaxation based heuristic algorithm is presented. Extensive computational experiments using standard benchmark data (CATS) as well as newly generated more realistic test sets were conducted which showed the heuristic was able to provide optimal solutions for most test cases and is within 1% from the optimums for the rest within very short times. Experiements comparing CPLEX 8.0, the fastest current algorithm, showed the heuristic was able to provide equally godd or better solutions often requring less than 1% of the time required by CPLEX 8.0.
9. Yunsong Guo, Andrew Lim, Brian Rodrigues and Yi Zhu, Carrier assignment models in transportation procurement, Journal of the Operational Research Society (JORS), 57, 2006.
This paper extends carrier assignment models used in winner determination auctions for transportation procurement to include shipper non-price objectives and carrier transit point costs. The models are unlike traditional carrier assignment models which incorporate only carrier lane bids, and different from combinatorial auction models which focus on packets of lanes without considering transit point costs. We develop solutions, including metaheuristics, for the new models and through computational experimentation show that the algorithms work well and can be easily implemented.
8. Yunsong Guo, Andrew Lim, Brian Rodrigues and Yi Zhu, Heuristics for a bidding problem, Computers & Operations Research (COR) , 33(8), 2006.
In this paper we study a bidding problem which can be modelled as a set packing problem. A simulated annealing heuristic with three local moves, including an embed- ded branch-and-bound move, is developed for the problem. We compared the heuristic with the CPLEX 8.0 solver and the current best non-exact method, Casanova, using the standard CATS benchmark and other realistic test sets. Results show that the heuristic outperforms CPLEX and Casanova.
7. Ping Chen, Yunsong Guo, Andrew Lim, and Brian Rodrigues, Multiple crossdocks with inventory and time windows, Computers & Operations Research (COR), 33(1), 2006.
Crossdocking studies have mostly been concerned with the physical layout of a crossdock or on a single crossdock. In this work, we study a network of crossdocks taking into consideration delivery and pickup time windows, warehouse capacities and inventory handling costs. Because of the complexity of the problem, local search techniques are developed and used with simulated annealing and tabu search heuristics. Extensive experiments were conducted and results show the heuristics outperform CPLEX, providing solutions in realistic timescales.
6. Yunsong Guo, Yanzhi Li, Andrew Lim, Brian Rodrigues, A multi-exchange heuristic to production line design under free trade agreement, The 18th Australian Joint Conference on Artificial Intelligence(AUAI), 2005; also appeared in Lecture Notes in Computer Science, Editors S. Zhang and R. Jarvis, Springer-Verlag, Heidelberg, Volume 3809 (2005), pp. 871 - 874
Production line design(PLD) can be viewed as a facility location problem in global supply chain. However, New cost factors such as tari® are introduced under free trade agreements which appeared about ten years ago and is becoming pervasive in global trading. A multinational manufacturer has factories all over the world to produce a product. When a demand arises from a new market, the manufacturer can fully utilize the existing resources and configure a most cost-e®ective production line to satisfy the new demand. Such a problem turns out to be NP-hard. We provide an integer programming model, which is hard to solve optimally while able to provide a lower bound. We then propose a multi-exchange heuristic embedded in simulated annealing to tackle the problem. Extensive experiments are conducted and comparisons are made with the lower bound and show that our algorithm performs very well.
5. Yunsong Guo, Andrew Lim, Brian Rodrigues and Jiqing Tang, Using a lagrangian heuristic for a combinatorial auction problem, The 17th International Conference on Tools with Artificial Intelligence (ICTAI), 2005.
In this paper, a combinatorial auction problem is modeled as a NP-complete set packing problem and a Lagrangian relaxation based heuristic algorithm is proposed. Extensive experiments are conducted using benchmark CATS test sets and more complex test sets. The algorithm provides optimal solutions for most test sets and is always 1% from the optimal solutions for all CATS test sets. Comparisons with CPLEX 8.0 are also provided, which show that the algorithm provides good solutions.
4. Yunsong Guo,
Andrew Lim, Brian Rodrigues and Yi Zhu, A non-exact approach and experiment studies on the
combinatorial auction problem, The 38th
In this paper we formulate a combinatorial auction brokering problem as a set packing problem and apply a simulated annealing heuristic with hybrid local moves to solve the problem. We study the existing exact and nonexact approaches to the problem and analyze the performance of those approaches. We compared our heuristic with the leading exact method CPLEX 8.0 solver and another non-exact algorithms Casanova using both the CATS test sets and test cases believed more difficult than CATS. Results show that the method is competitive with CPLEX 8.0 and obtains near optimal solutions for the CATS cases and up to 15% and 40% better solutions compared with CPLEX and Casanova, respectively, when the other instances were used.
3. Yunsong Guo, Andrew Lim, Brian Rodrigues and Shanhu Yu, Minimizing total flow time in single machine environment with release time: an experimental analysis, Computers & Industrial Engineering (CIE), 47(2-3), 2004.
We study the problem of minimizing total flow time on a single machine with job release times. This problem is NP-complete for which is no constant ratio approximation algorithm. Our objective is to study experimentally how well, on average, the problem can be solved. The algorithm we use produces non-preemptive schedules converted from preemptive ones. We evaluate average solution quality for the problem to identify the characteristics of difficult instances. Results obtained are compared with those recently obtained by other researchers. Based on extensive experiments, we also develop an empirical model to predict solution quality using interpolation.
2. Yunsong Guo, Andrew Lim, Brian Rodrigues and Yi Zhu, Heuristics for a brokering set packing problem, The 8th International Symposium on Artificial Intelligence and Mathematics (AMAI), 2004.
In this paper we formulate the combinatorial auction brokering problem as a Set Packing Problem (SPP) and apply a simulated annealing heuristic to solve SPP. Experimental results are compared with a recent heuristic algorithm and also with the CPLEX Integer Programming solver where we found that the simulated annealing approach outperforms the previous heuristic method and CPLEX obtaining results within smaller timescales.
1. Yunsong Guo, Andrew Lim, Brian Rodrigues and Yi Zhu, Transportation bid analysis optimization with shipper input, The 15th International Conference on Tools with Artificial Intelligence (ICTAI), 2003.
This paper extends carrier assignment models used in bid analysis for transportation procurement to incorporate shipper business considerations. These include restricting carrier numbers, favoring incumbents and performance considerations. We provide representative models and develop solutions for these which include the use of metaheuristics. Experimentation shows that our algorithms work well.
Updated Sep-09