Algorithm E.1 Golden search algorithm, l : c : o + 0 . 3 8 2 ( b – a ) . 2 : w h i l e b – a > e d o 3 : d , : b – 0 . 3 8 2 ( b – a ) . 4: if f (d) > /(c) then 5 : b : d . 6: else 7 : a : q c : d . 8: end if 9: end while
10: return c.
zs, the following expression is obtained:
Taking the derivative of the function with respect to r and setting it to zero leads to the following equation:
f (*) = f (ro) + @ – ro) f’ (*o) + @+t f” (ro).
f ‘(“) : f
‘(ro) + (, – rg) ftt(rs) : g
f ‘(ro) r : 10_7- l ‘1 i l .
(E.6)
(E.7)
Equation E.7 can be used to update r until it converges to the location of the minimum value. It can be shown that Newton’s method has quadratic convergence, although it may fail to converge in some cases, especially when the initial point rs is located far away from the minimum point. A summary of this method is given in Algorithm E.2
Algorithm E.2 Newton’s method. 1: Let as be the initial point. 2: while lf ‘(ro)l ) e do
r t ( – ^ \3: t r : ro – f f f i . 4 : t r o : n . 5: end while 6: return r.
Newton’s method can first order derivative //(r)
be extended to multivariate data by replacing the with the gradient operator V/(x) and the second
E.1- Unconstrained Optimization 745
order derivative ftt(r) with the Hessian matrix fI:
x: x – r r – lv / (x) .
However, instead of computing the inverse of the Hessian matrix, it is easier to solve the following equation:
Hz: -V / ( * )
to obtain the vector z. The iterative formula for finding the stationary point
i s m o d i f i e d t o x : x * 2 .
Gradient Descent Method Newton’s method is one of several incremental methods to progressively locate the stationary point of a function using the following update formula:
x : x+ )9 (x ) ) , (E.8)
The function g(x) determines the direction in which the search should proceed
and .\ determines the step size. The gradient descent method assumes that the function /(x) is differen-
tiable and computes the stationary point as follows:
x : x – )V / ( x ) , (E.e)
In this method, the location of x is updated in the direction of the steepest descent, which means that x is moved towards the decreasing value of /. Section 5.4.2 described how the gradient descent method can be used to learn the weight parameters of an artificial neural network. A summary of this method is given in Algorithm E.3. Notice that the algorithm looks very similar to AlgorithmE.2, except for the update formula.
Algorithm E.3 Gradient descent method. 1: Let xs be the initial point. 2: while l lv/(*o)l l ) e do 3 : t r : n o – ) V / ( x ) . 4: f io : t r . 5: end while 6: return r.
746 Appendix E Optimization
8.2 Constrained Optimization
This section examines how to solve an optimization problem when the variables are subjected to various types of constraints.
8.2.L Equality Constraints
Consider the problem of finding the minimum value of f (ryn2t…,ra) sub- jected to equaiity constraints of the form
7 t ( x ) : 0 , ‘ i : I , 2 , . . . , P .
A method known as Lagrange multipliers can be used to solve the constrained optimization problem. This method involves the following steps:
1. Define the Lagrangian, I(x,,\) : /(x) +Dl:r\gilx), where )i is a dummy variable called the Lagrange multiplier.
2. Set the first-order derivatives of the Lagrangian with respect to x and the Lagrange multipliers to zero,
#:0, Vi :1,2, . . . ,d
and AL
N : 0 ‘ V z i : I ‘ 2 ” ” ‘ P ‘
3. Solve the (d * p) equations in step 2 to obtain the stationary point x* and the corresponding values for )6’s.
The following example illustrates how the Lagrange multiplier method works.
Example 8.2. Let f (r,g) : r l2A. Suppose we want to minimize the function f (“,A) subject to the constraint ,’+ A2 – 4 : 0. The Lagrange multiplier method can be used to solve this constrained optimization problem in the following way.
First, we introduce the Lagrangian
L(r ,A, , ) ) : , I2y – t ) , ( r2 + A2 – 4) ,
8.2 Constrained Optimization 747
where .\ is the Lagrange multiplier. To determine its minimum value, we need to differentiate the Lagrangian with respect to its parameters:
AL 0r AL 0y AL 0^
: L l2 ) , r :0
: 2+2^a :0
: , , +a, – 4 😮
(E.10)
(E .11 )
(E.13)
(E.14)
(E. i5)
(E.16)
Solving these equations yields S: +t/51a. 7 :121t/5, and g : a4lJB. When A: l| l4, f (-2lr/b,-4lr/6) : -r0l\/5.Similarly, when ) : -t/614, f (21’/5,41t/5): L\lt/5.Thus, the function f(r,g) has its minimum value at r: -2lt /5 and g: -41’/5.
8.2.2 Inequality Constraints
Consider the problem of finding the minimum value of. f (q,r2t…, z6) sub- jected to inequality constraints of the form
h t @ ) < 0 , i : t , 2 , . . . , e .
The method for solving this problem is quite similar to the Lagrange method described above. However, the inequality constraints impose additional con- ditions to the optimization problem. Specifically, the optimization problem stated above leads to the following Lagrangian
i ? , , 9 , , ,r : f 8 ) + l \ i h i$ ) . (E .12) i.:r
and constraints known as the Karush-Kuhn-Tucker (KKT) conditions:
AL : l l
0u hil*)
),,i
,\ah6(x) : 0,
Y i : I , 2 , . . . , d
V ‘ i : 1 , 2 r . . . r Q
Y ‘ i : 1 , 2 r . . . r Q
Y ‘ i : 7 ,2 , . . . r e .
Notice that the Lagrange multipliers are no longer unbounded in the presence of inequality constraints.
748 Appendix E Optimization
Example E.3. Suppose we want to minimize the function f (r,A) : @ –
7)’ + (A – 3)2 subject to the following constraints:
r * y 1 2 , a n d y 2 r .
The Lagrangian for this problem is .L : (r – I)’ + @- g)’ + ),t(r i a –
2) + \2(r – g) subjected to the following KKT constraints:
A r .
#:2(r – i )+)r* )z 😮 AT, F:2 (a -3 ) * ) r – l z :ooa ) 1 ( z *A -2 ) : 0
^z ( r – A ) : 0
) r ) 0 , , \ z )0 , r+A<2 ,U2 r
(E.17)
(E.18)
(E.1e)
(E.20)
(E.21)
To solve the above equations, we need to examine all the possible cases of
Equations E.19 and E.20.
Case 1: )r : 0, )z : 0. In this case, we obtain the following equations:
2 ( t – 1 ) : 0 a n d 2 ( Y – 3 ) : 0 ,
whose solution is given by r : 1 and U : 3. Since z * A :4, this is not a feasible solution because it violates the constraint r * y < 2.
Case 2: )r : 0, \z 10. In this case, we obtain the following equations:
r – a : 0, 2(r- 1) + )z : 0, 2(a -3) – \z : 0,
whose solution is given by r : 2, A : 2, and \z : -2, which is not a feasible solution because it violates the conditions )2 ) 0 and r * y 1 2.
Case 3: \ 10, )z : 0. In this case, we obtain the following equations:
r+A-2 :0 ,2 ( * – 1 ) – | ) r :0 , -2 ( r +1) + ) r :0 ,
whose solution is given by r : 0, U :2, and \t : 2, which is a feasible solution.
8.2 Constrained Optimization 749
Case 4: \r # 0, \z 10. In this case, we obtain the following equations:
r+A -2 :0 , t r -A :0 ,2 ( r – 1 )+ ) r * l z : 0 ,2 (A -3 )+ )1 – . \ 2 : Q ,
whose solution is r : L, a : 1, ,\1 : 2, and \2 : -2, which is not a feasible solutiorr.
Therefore, the solution for this problem is r : 0 and A :2. I
Solving the KKT conditions can be quite a laborious task especially if the number of constraining inequalities is large. In such cases, finding a closed- form solution is no longer possible and it is necessary to use numerical tech- niques such as linear and quadratic programming.
Author Index
Abdulghani, .A., 399 Abe, N. , 315 Abel lo , J . ,646 Abiteboul, S., 402 Abraham, 8. ,677 Adams, N. M., 397 Aelst , S. V. ,679 Agarwal, R. C., 314, 397, 678 Aggarwal, C. C., 397, 677 Agrawal, R., 14, 88, 197, 198, 397, 401,
402, 47L, 472, 644 Aha, D. W., 196, 312 Aldenderfer, M. S., 556 Alexandridis, M. G., 197 Ali, K., 397 Allwein, E. L.,312 Alsabti, K., 196 Altman, R. 8., 15 Anderberg, M. R., 86, 556 Anderson, T. W., 7LT Andrews, R., 312 Ankerst, M., 557 Antonie, M.-L.,47I Aone, C., 558 Arabie, P., 557, 558 Arnold, 4. ,677 Aumann, Y. ,47I Austin, J., 678 Ayres, J., 471
Bakiri, G., 313 Ball, G., 557 Banerjee, 4., 557 Barbar6, D., 397, 644 Barnett, V.,677 Bastide, Y., 401 Batistakis, Y., 557 Baxter, R. A., 678
Bay, S. D., 397, 677 Bayardo, R., 397 Beckman, R. J.,677 Belanche, L., 88 Belk in, M. ,717 Ben-David, S., 16 Benjamini, Y., 397 Bennett, K.,312 Berkhin, P., 557 Berry, M. J. A., 14 Bertino, E., 16 Bi lmes, J . ,644 Bins, M., 1-97 Bishop, C. M., 196, 312,644 Blashfield, R. K., 556 Blum, A. ,86 Bock, H. H., 87 Boley, D., 557, 558 Bolton, R. J., 397 Borg, I., 87 Boswell, R., 312 Bosworth, 4., I4l Boulicaut, J.-F.,47L Bowyer, K. W., 312 Bradley, A. P., 312 Bradley, P. S., 14, 403,557,645 Bratko, I., 197 Breiman, L., L96,3L2 Breslow, L. A., 196 Breunig, M. M., 557,677 Brin, S., 397,40L Brockwell, A., 16 Brodley C. E., 198, 679 Buntine, W., 196 Burges, C. J . C. ,3I2 Burn, D. A., 140 Bykowski, L.,47I
Cai, C. H., 397 Campbell, C.,3L2 Cantri-Paz, tr., 196 Card, S. K., l4l Carreira-Perpinan, M. A., 7L7 Carralho, C., 401 Ceri, S., 400 Chakrabarti, S., 14 Chan, P. K., 16, 313 Chang, L., 680 Chatterjee, S., 646 Chaudhary, A.,677 Chaudhuri, S., 141 Chawla, N. V., 312, 677 Cheeseman, P.,645 Chen, B., 402 Chen, C., 677 Chen, M.-S., 14, 40L, 472 Chen, Q. , 398,472,680 Chen, S., 400 Chen, S.-C., 680 Cheng, C. H., 397 Cheng, H. ,471 Cherkassky, V., 15, 796,312 Cheung, D. C., 398 Chiu, B., 678 Choudhary, A.,646 Chuang , 4 ,677 Chung, S. M., 399 Clark, P., 312 Clifton, C., 15, 402 Coatney, M.,40I,472 Cochran, W. G., 87 Codd, E. F. , 141 Codd, S. B. , 141 Cohen, P. R., 196 Cohen, W. W., 312 Cook, D. J . ,646 Cook, R. D. ,677 Cooley, R., 398 Cost , S. , 312 Couto, J . ,397 Cover, T. M., 312 Cristianini, N., 313
Dash, M., 87 Datta, S., 16 Davies, L. ,677 Dayal, U., 398, 472,559
Author Index 75L
Demmel, J. W., 87, 700,717 Dhillon, L S., 557 Diday, E., 87 Diederich, J ., 3L2 Dietterich, T. G., 313, 314 Ding, C., 403 Dokas, P., 398 Domingos, P., 15, 196, 313 Dong, G., 398 Donoho, D. L. ,7I7 Doster, W., 198 Dougherty, J., 87 Drummond, C., 313 Dubes, R. C., 87, 558 Duda, R. O. , 15, 196, 313, 557 Duin, R. P. W., 196, 315 DuMouchel, W., 398 Dunagan, J . ,677 Dunham, M. H., 15, 313 Dunkel, 8., 398
Efron, B., 196 Elkan, C., 313, 557 Elomaa, T., 87 Erhart, M., 646 Ertoz, L.,398, 645, 679 Eskin, E. , 677,679 Esposito, F., 196 Ester, M., 557, 558 Everitt, B. S., 557
Fiirnkranz, J., 313 Fabris, C. C., 398 Faloutsos, C., 16, 88,717 Fan, W., 313 Fawcett, T.,3L4 Fayyad, U. M., 15, 87,l4l, 403,557,645 Feng, L., 398,402 Ferri, C., 313 Fisher, D., 557, 645 Fisher, N. I., 398 Fisher, R. A., 196 Flach, P., 313 Flannick, J., 47L Flynn, P. J., 558 Fodor, I . K. ,717 Fovino, I. N., 16 Fox, A. J . ,678 Fraley, C.,645
752 Author Index
FYank, E. , 16,315 Fbawley W., 401 FYeeman, D., 645 Freitas, A. A., 398 Fleund, Y., 313 Fliedman, J. H., 15, 196, 313, 398, 558 Fliendly, M., 141 Fu, A., 397, 399 F\r, Y., 399,47t Fukuda, T., 398, 400,47I Fukunaga, K., 196, 313 F\rruichi, E., 401
Gada, D., 87 Ganti, V., 196, 645 Gaohua Gu, F. H., 87 Garofalakis, M. N., 471 Gather , U. ,677 Geatz, M., 16 Gehrke, J., L4, L6, L4l, L96, 471, 644, 645 Gersema, 8., L97 Gersho, A., 645 Ghosh, A., 678 Ghosh, J . ,557,645,647 Giannella, C., 15 Gibson, D., 645 Glymour, C., 15 Gnanadesikan, R., 678 Goil, S., 646 Golub, G. H., 700 Goodman, R. M., 315 Gowda, K. C. ,645 Grama, A., 16 Gray, J., 141 Gray R. M., 645 Grimes, C. ,7t7 Grinstein, G. G., 15, 141 Groenen, P., 87 Grossman, R. L., 15, 646 Grubbs, F., 678 Guan, Y., 557 Guha, S., 15,645 Gunopulos, D., 398, 644 Guntzer, U., 399
Haight, R.,402 Halic, M., 197 Halkidi, M., 557 Hall, D., 557
Hall, L. O., 312 Hamerly, G., 557 Hamilton, H. J., 399 Han, E.-H., 197, 313, 398, 399, 47I,558,
645,646 llan, J., 14, 15, 313, 398-403, 477, 472,
558, 646 Hand, D. J., 15, 87, 313, 397 Hardin, J., 678 Hart , P. E. , 15, 196,3I2,313, 557 Hartigan, J., 558 Hastie, T., 15, 196, 313, 558 Hatonen, K.,402 Hawkins, D. M., 678 Hawkins, S., 678 He, H., 678 He, X., 403 He ,Y . ,4O2 Hearst, M., 313 Heath, D., 196 Heckerman, D., 314 Hernandez-Orallo, J., 313 Hidber, C., 399 Hilderman, R. J., 399 Hinneburg, A., 646 Hipp, J., 399 Ho, C.-T. , 16 Hoaglin, D., 141 Hochberg, Y., 397 Hodge, V. J., 678 Hofmann, H., 399 Holbrook, S. R., 403 Holder, L. 8., 646 Holt, J. D., 399 Holte, R. C., 313, 314 Hong, J., 314 Hornick, M. F., 15 Houtsma, M., 399 Hsieh, M. J . ,472 Hsu, M., 398, 472,559 Hsu, W., 400 Huang, T. S., 646 Huang, Y., 399 Hubert, L., 557, 558 Hubert, M., 679 Hulten, G., 15 Hussain, F., 87 Hoppner, F., 646
Iba, W., 314 Imielinski, T., 397, 399 Inokuchi, 4.,399, 47I Irani, K. B., 87
Jagadish, H. V., 678 Jain, A. K., 16, 87, 196, 558 Jajodia, S., 397 Janardan, R.,7I7 Japkowicz, N., 312, 314,677,678 Jardine, N., 558 Jaroszewicz, S.,399 Jarvis, R. A., 646 Jensen, D., 88, 196 Jeudy, B., 471 John, G. H., 87 Johnson, T., 678 Jol l i f fe , I . T. ,87,717 Jonyer, L, 646 Joshi, A., 15 Joshi , M. V. , 196, I97,3I4,47L,678
Kail ing, K.,646
Author Index 753
Klooster, S., 401, 402,647 Knorr, E. M., 678, 679 Kogan, J., 557 Kohavi, R., 87, 197 Kohonen, T.,646 KoIcz, 4. ,3L2,677 Kong, E. B:, 314 Koperski, K., 399 Kosters, W. A., 399 Koudas, N., 678 Krciger, P.,646 Krantz, D., 87, 88 Kriegel, H.-P., 557, 558,646,677 Krishna, G., 645 Kruse, R., 646 Kruskal, J. 8., 87, 717 Kubat, M., 314 Kuhara, S., 401 Kulkarni, S. R., 197 Kumar, V., 15, L96, 197,313, 314, 398-
403, 47r, 472, 558, 559, 645- 647 ,678 ,679 ,7L7
Kuok, C. M., 399 Kuramochi , M. ,400,471 Kwok; I., 678 Kwong, W. W., 397
Lakhal , L . ,40L Lakshmanan, L. V. S., 400 Lambert, D., 16 Landau, S., 557 Landeweerd, G., 197 Landgrebe, D., 197, 198 Lane, T., 679 Langford, J. C., 315, 717 Langley. P., 86, 314, 645 Larsen, 8., 558 Lavrac, N., 314 Law, M. H. C., 16 Layman, 4., L4L Lazarevic, A., 398, 679 Lee, S. D., 398 Lee, W., 400, 679 Lee , Y . W. ,88 Leese, M., 557 Lent, B., 472 Leroy, A. M., 679 Lewis, D. D., 314 Lewis, T., 677
, 471, 472, 558, 559, 645,646
Kasif, S., 796, I97 Kass, G. V., 196 Kaufman, L., 87, 558 Kegelmeyer, P., 15, 646 Kegelmeyer, W. P., 312 Keim, D. A., 646 Kelly, J., 645 Keogh, E., 678 Keogh, E. J . ,87 Kettenring, J. R., 678 Khardon, R., 398 Kifer, D., 16 Kim, B. , 197 Kitsuregawa, M., 401 Klawonn, F.,646 Kleinberg, J. M., 558, 645 Klemettinen, M., 399, 402
754 Author Index
