Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/ium/postscript/f12/nesterov-Lect5_Econ.pdf Äàòà èçìåíåíèÿ: Fri Sep 7 23:12:32 2012 Äàòà èíäåêñèðîâàíèÿ: Mon Feb 4 19:30:39 2013 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: dark nebula

Lecture 5: Algorithmic models of human behavior
Yurii Nesterov, CORE/INMA (UCL)

March 14, 2012


Main problem with the Rational Choice
Rational choice assumption is introduced for better understanding and predicting the human behavior. It forms the basis of Neoclassical Economics (1900). The player (Homo Economicus HE) wants to maximize his utility function by an appropriate adjustment of the consumption pattern. As a consequence, we can speak about equilibrium in economical systems. Existing literature is immense. It concentrates also on ethical, moral, religious, social, and other consequences of rationality. (HE = super-powerful aggressively selfish immoral individualist.) NB: The only missing topic is the Algorithmic Aspects of rationality.


What do we know now?

Starting from 1977 (Complexity Theory, Nemirovski & Yudin), we know that optimization problems in general are unsolvable. They are very difficult (and will be always difficult) for computers, independently on their speed. How they can be solved by us, taking into account our natural weakness in arithmetics? NB: Mathematical consequences of unreasonable assumptions can be disastrous. Perron paradox: The maximal integer is equal to one. Pro of: Denote by N the maximal integer. Then 1 N N2 N. Hence, N = 1.


What we do not know

In which sense the human beings can solve the optimization problems? What is the accuracy of the solution? What is the convergence rate? Main question: What are the optimization methods? NB: Forget about Simplex Algorithm and Interior Point Methods! Be careful with gradients (dimension, non-smoothness).


Outline

1 Intuitive optimization (Random Search)

2 Rational activity in sto chastic environment

(Stochastic Optimization)

3 Mo dels and algorithms of rational b ehavior


Intuitive Optimization

Problem:

x R

min f (x ), n

where x is the consumption pattern.

Main difficulties: High dimension of x (difficult to evaluate/observe). Possible non-smoothness of f (x ). Theoretical advice: apply gradient method xk +1 = xk - hf (xk ). (In the space of all available products!) Hint: we live in an uncertain world.


Gaussian smoothing
Let f : E R be differentiable along any direction at any x E . Let us form its Gaussian approximation fµ ( x ) = where =
def E 1

f (x + µu )e
E n/2

1 -2 u

2

du ,

e

-

1 2

u

2

du = (2 )

.

In this definition, µ 0 plays a role of the smoothing parameter. Why this is interesting? Define y = x + µu . Then fµ (x ) = fµ (x ) =
1 µ 1 µ
n+2

1 µn

f (y )e
E -
1 2µ2

-

1 2µ2 2

y -x

2

dy . Hence,



f (y )e
E -
1 2

y -x

(y - x ) dy
f (x +µu )-f (x ) - e µ
1 2 2

=

f (x + µu )e
E

u

2

u du =

(!) 1

u

u du .

E


Properties of Gaussian smoothing

If f is convex, then fµ is convex and fµ (x ) f (x ). If f C If f C
0,0 0,0

, then fµ C

0,0

and L0 (fµ ) L0 (f ).
1/2

(E ), then, |fµ (x ) - f (x )| µL0 (f )n

.

Random gradient-free oracle: Generate random u E . Return gµ (x ) = If f C
0,0 f (x +µu )-f (x ) µ

· u.

(E ), then Eu ( gµ (x ) 2 ) L2 (f )(n + 4)2 . 0


Random intuitive optimization
Problem: f
def =

x Q

min f (x ) , where Q E is a closed convex .

set, and f is a nonsmooth convex function. Let us choose a sequence of positive steps {hk } Metho d RS µ : Choose x0 Q . For k 0: a). Generate uk .
1 b). Compute k = µ [f (xk + µuk ) - f (xk )]. k 0

c). Compute xk NB: µ can be arbitrary small.

+1

= Q (xk - hk k uk ).


Convergence results

N

This method generates random {xk }

k 0

. Denote SN =
k =0 U
k -1

hk ,

Uk = (u0 , . . . , uk ), 0 = f (x0 ), and k = E Theorem: Let {xk }
N k =0 hk SN k 0

def

(f (xk )), k 1.

be generated by RS µ with µ > 0. Then,
1/2

(k - f ) µL0 (f )n

+

1 2SN

x0 - x

2

+

(n+4)2 2 2SN L0

N

(f )
k =0

2 hk .

In order to guarantee E µ=
2L0 (f )n
1/2

U

N -1

(f (xN )) - f , we choose ^ , N=
4(n+4)2 2 L0 2

,

hk =

R (n+4)(N +1)1/2 L0 (f )

(f )R 2 .


Interpretation

Disturbance µuk may be caused by external random factors. For small µ, the sign and the value of k can be treated as an intuition. We use a random experience accumulated by a very small shift along a random direction. The reaction steps hk are big. (Emotions?) The dimension of x slows down the convergence. Main ability: to implement an action, which is absolutely opposite to the proposed one. (Needs training.) NB: Optimization method has a form of emotional reaction. It is efficient in the absence of stable coordinate system.


Optimization in Stochastic Environment

Problem: min [ (x ) = E (f (x , ))
x Q

f (x , ) p ( ) d ], where

f (x , ) is convex in x for any R m , Q is a closed convex set in R n , p ( ) is the density of random variable . Assumption: We can generate a sequence of random events {i }:
1 N N N

f (x , i )
i =1



E (f (x , )),

x Q.

Goal: For

> 0 and = min (x ) find x Q : (x ) - . ¯ ¯
x Q

Main trouble: For finding -approximation to (x ), we need m O1 computations of f (x , ) .


Stochastic subgradients (Ermoliev, Wetz, 70's)
Metho d: Fix some x0 Q and h > 0. For k 0, repeat: generate k and update x Output: x = ¯
1 N +1 N k +1

= Q (xk - h · f (xk , k )).

xk .
k =0

Interpretation: Learning process in stochastic environment. Theorem: For h =
R L N +1

we get

E ((x )) - ¯

LR N +1

.

NB: This is an estimate for the average performance. Hint: For us, it is enough to ensure a Confidence Level (0, 1]: Prob [ (x ) + V ] 1 - , ¯ where V = max (x ) - .
x Q

In the real world, we always apply solutions with < 1.


What do we have now?
After N -steps we observe a single implementation of the random variable x with E ((x )) - LR . ¯ ¯ N +1 What ab out the level of confidence? 1. For random 0 and T > 0 we have E ( ) = = +
T and
T · Prob [ T ].

2. With = (x ) - ¯
1 V

T = V we need
LR V N +1
2

[E ((x )) - ] ¯ N +1=
2

1 - .
2

Thus, we can take

1 (1- )

LR V

.

NB: 1. For personal needs, this may be OK. What about 1? 2. How we increase the confidence level in our life? Ask for advice as many persons as we can!


Pooling the experience

Individual learning process (Forms opinion of one expert) Choose x0 Q and h > 0. For k = 0, . . . , N repeat generate k , and set xk +1 = Q (xk - hf (xk , k )). Compute x = ¯
1 N +1 N

xk .
k =0

Pool the experience: For j = 1, . . . , K compute xj . Generate the output x = ¯ ^ Note: All learning processes start from the same x0 .
1 K K

xj . ¯
j =1


Probabilistic analysis

Theorem. Let Zj [0, V ], j = 1, . . . , K be independent random ^ variables with the same average µ. Then for ZK = ^ Prob Zk µ + ^ exp - Corollary.
1 Let us choose K = 2 ln 1- , N = 4 LR , and h = 2 2 V Then the pooling process implements an ( , )-solution. 2 R L N +1 2^2 K V2 1 K K

Zj
j =1

.

.

Note: Each 9 in = 0.9 · · · 9 costs

4.6
2

experts.


Comparison ( is not too small Q is reasonable)
Denote = LR V Number of experts Length of life Computational efforts Single Expert (SE) Pooling Experience (PE) 2 1 1 2 ln 1-
2 2

2 (1- )2 2 (1- )2

4 8
2 4

2

2

ln

1 1-

Reasonable computational expenses (for Multi-D Integrals) Number of experts does not depend on dimension. Differences For low level of confidence, SE may be enough. High level of confidence needs independent expertise. Average experience of young population has much higher level of confidence than the experience of a long-life wizard. In PE, the confidence level of "experts" is only
1 2

(!).


Why this can be useful?

Understanding of the actual role of existing social an political phenomena (education, medias, books, movies, theater, elections, etc.) Future changes (Internet, telecommunications) Development of new averaging instruments (Theory of expertise: mixing opinion of different experts, competitions, etc.)


Conscious versus subconscious

NB: Conscious behavior can be irrational. Subconscious behavior is often rational. Animals. Children education: First level of knowledge is subconscious. Training in sport (optimal technique subconscious level). Examples of sub conscious estimates: Mental "image processing". Tracking the position of your body in space. Regular checking of your status in the society (?) Our mo del: Conscious behavior based on dynamically updated subconscious estimates.


Model of consumer: What is easy for us?
Question 1: Question 2: 123 456 = ? How often it rains in Belgium?

Easy questions: average salary, average gas consumption of your car, average consumption of different food, average commuting time, and many other (survey-type) questions. Main abilities of anybo dy: 1. Remember the past experience (often by averages). 2. Estimate probabilities of some future events, taking into account their frequencies in the past. Guess: We are Statistical Homo Economicus? (SHE)


Main features of SHE

Main passion: Observations. Main abilities: Can select the best variant from several possibilities. Can compute average characteristics for some actions. Can compute frequencies of some events in the past. Can estimate the "faire" prices for products. As compared with HE: A huge step back in the computational power and informational support. Theorem: SHE can be rational. (The proof is constructive.)


Consumption model
Market There are n products with unitary prices pj . Each product is described by the vector of qualities aj R m . (i ) Thus, aj is the volume of quality i in the unit of product j . Consumer SHE Forms and updates the personal prices y R
m

for qualities.

Can estimate the personal quality/price ratio for product j : 1 j (y ) = pj aj , y .
m

Has standard i for consumption of quality i ,
i =1

i yi = 1.

Denote A = (a1 , . . . , an ), = (1 , . . . , m )T , (y ) = max j (y ).
1j n


Consumption algorithm (CA) for k th weekend

For Friday night, SHE has personal prices yk , budget k , and cumulative consumption vector of qualities sk R m , s0 = 0.
1

Define the set Jk = {j : j (yk ) = (yk )}, containing the products with the best quality/price ratio.
n

2

Form partition xk 0:
j =1

x

(j ) k

= 1, and x
(j )

(j ) k

= 0 for j Jk .

3 4 5

Buy all products in volumes Xk = k · x Consume the bought products: s
k +1

(j ) k

/pj , j = 1, . . . , n.

= sk + AXk .

During the next week, SHE watches the results and forms the personal prices for the next shopping.

NB: Only Item 5 is not defined.


Updating the personal prices for qualities
Define i = i y
(i ) k m

, the relative importance of quality i ,
i =1

i = 1.

1 Denote by ^k = k sk the average consumption. s

Assumption. 1. During the week, SHE performs regular detections (i ) of the most deficient quality by computing k = min ^k /i . s
1i m

2. This detection is done with random additive errors. Hence, we observe E
1i m

min

^k s i

(i )

+

i

.

Thus, any quality has a chance to be detected as the worst one. 3. We define i as the frequency of detecting the quality i as the most deficient one with respect to ^k . s This is it. Where is Optimization? Objective Function, etc.?


Algorithmic aspects

1. If

i

are doubly-exponentially i.i.d. with variance µ, then yk =
(i ) 1 i

exp -

sk k i µ

(i )

m

/
j =1

exp -

sk k j µ

(j )

Therefore, yk = arg min { sk , y + d (y )} ,
,y =1 m i =1

where = k µ, d (y ) = 2. AXk = k A
xk p

i y

(i )

ln(i y

(i )

) (prox-function).

k gk , where gk (yk ) (subgradient).

3. Hence, sk is an accumulated model of function (y ). Hence, CA is a primal-dual method for solving the (dual) problem min (y ) max
y 0 1 1i m pi

ai , y : , y = 1 .


Comments
1. The primal problem is max{ : Au , u 0, p , u = 1}.
u ,

We set uk = [xk /p ] and approximate u by averaging {uk }. 2. No "computation" of subgradients (we just buy). Model is updated implicitly (we just eat). 3. CA is an example of unintentional optimization. (Other examples in the nature: Fermat principle, etc.) 4. SHE does not recognize the objective. However, it exists. SHE is rational by behavior, not by the goal (which is absent?). 5. Function (y ) measures the positive appreciation of the market. By minimizing it, we develop a pessimistic vision of the world. (With time, everything becomes expensive.) 6. For a better life, allow a bit of irrationality. (Smooth objective, faster convergence.)


Conclusion

1. Optimization patterns are widely presented in the social life. Examples: Forming the traditions (Inaugural Lecture) Efficient collaboration between industry, science and government (Lecture 1) Local actions in problems of unlimited size (Lecture 3). 2. The winning social systems give better possibilities for rational behavior of people. (Forget about ants and bees!) 3. Our role could be the discovering of such patterns and helping to improve them by an appropriate mathematical analysis.


References
Lecture 1: Intrinsic complexity of Black-Box Optimization Yu. Nesterov. Introductory Lectures on Convex Optimization. Chapters 2, 3. Kluwer, Boston, 2004. Yu. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence O ( k12 ). Doklady AN SSSR (translated as Soviet Math. Dokl.), 1983, v.269, No. 3, 543-547. Lecture 2: Looking into the Black Box Yu. Nesterov. "Smooth minimization of non-smooth functions", Mathematical Programming (A), 103 (1), 127-152 (2005). Yu. Nesterov. "Excessive gap technique in nonsmooth convex minimization". SIAM J. Optim. 16 (1), 235-249 (2005). Yu.Nesterov. Gradient methods for minimizing composite functions. Accepted by Mathematical Programming.


References

Lecture 3: Huge-scale optimization problems Yu.Nesterov. Efficiency of coordinate descent methods on large scale optimization problems. Accepted by SIAM. Yu.Nesterov. Subgradient methods for huge-scale optimization problems. CORE DP 2012/02. Lecture 4: Nonlinear analysis of combinatorial problems. Yu.Nesterov. Semidefinite Relaxation and Nonconvex Quadratic Optimization. Optimization Methods and Software, vol.9, 1998, pp.141­160. Yu.Nesterov. Simple bounds for boolean quadratic problems. EUROPT Newsletters, 18, 19-23 (December 2009).


References

Lecture 5: Yu.Nesterov, J.-Ph.Vial. Confidence level solutions for stochastic programming. Auromatica, 44(6), 1559-1568 (2008) Yu.Nesterov. Algorithmic justification of intuitive rationality in consumer behavior. CORE DP.


Thank you for your attention!