.. _sec_convexity:

Dışbükeylik
===========


Dışbükeylik optimizasyon algoritmalarının tasarımında hayati bir rol
oynamaktadır. Bunun nedeni, algoritmaları böyle bir bağlamda analiz
etmenin ve test etmenin çok daha kolay olmasından kaynaklanmaktadır.
Başka bir deyişle, algoritma dışbükey ayarda bile kötü başarım
gösteriyorsa, genellikle başka türlü harika sonuçlar görmeyi
ummamalıyız. Dahası, derin öğrenmedeki optimizasyon problemleri
çoğunlukla dışbükey olmamasına rağmen, genellikle yerel minimumun
yakınında dışbükey olanların bazı özelliklerini sergilerler. Bu,
:cite:`Izmailov.Podoprikhin.Garipov.ea.2018` çalışmasındaki gibi
heyecan verici yeni optimizasyon türlerine yol açabilir.



.. raw:: html

     <div class="mdl-tabs mdl-js-tabs mdl-js-ripple-effect"><div class="mdl-tabs__tab-bar code"><a href="#mxnet-1-0" onclick="tagClick('mxnet'); return false;" class="mdl-tabs__tab is-active">mxnet</a><a href="#pytorch-1-1" onclick="tagClick('pytorch'); return false;" class="mdl-tabs__tab ">pytorch</a><a href="#tensorflow-1-2" onclick="tagClick('tensorflow'); return false;" class="mdl-tabs__tab ">tensorflow</a></div>



.. raw:: html

     <div class="mdl-tabs__panel is-active" id="mxnet-1-0">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    %matplotlib inline
    from mpl_toolkits import mplot3d
    from d2l import mxnet as d2l
    from mxnet import np, npx
    
    npx.set_np()



.. raw:: html

     </div>



.. raw:: html

     <div class="mdl-tabs__panel " id="pytorch-1-1">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    %matplotlib inline
    import numpy as np
    import torch
    from mpl_toolkits import mplot3d
    from d2l import torch as d2l



.. raw:: html

     </div>



.. raw:: html

     <div class="mdl-tabs__panel " id="tensorflow-1-2">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    %matplotlib inline
    import numpy as np
    from mpl_toolkits import mplot3d
    import tensorflow as tf
    from d2l import tensorflow as d2l



.. raw:: html

     </div>



.. raw:: html

     </div>

Tanımlar
--------

Dışbükey analizden önce, *dışbükey kümeleri* ve *dışbükey fonksiyonları*
tanımlamamız gerekir. Makine öğrenmesinde yaygın olarak uygulanan
matematiksel araçlara yön verirler.

Dışbükey Kümeler
~~~~~~~~~~~~~~~~

Kümeler dışbükeyliğin temelini oluşturur. Basitçe söylemek gerekirse,
bir vektör uzayında bir :math:`\mathcal{X}` kümesi,
:math:`a, b \in \mathcal{X}` için :math:`a` ve :math:`b`'yi bağlayan
doğru parçası da :math:`\mathcal{X}`'de ise *dışbüküm* olur.
Matematiksel anlamda bu, tüm :math:`\lambda \in [0, 1]` için aşağıdaki
ifadeye sahip olduğumuz anlamına gelir

.. math:: \lambda  a + (1-\lambda)  b \in \mathcal{X} \text{ ne zaman ki } a, b \in \mathcal{X}.

Kulağa biraz soyut geliyor. :numref:`fig_pacman` figürünü düşünün.
İçinde tamamı kapsanmayan doğru parçaları bulunduğundan ilk küme
dışbükey değildir. Diğer iki kümede böyle bir sorun yaşanmaz.

.. _fig_pacman:

.. figure:: ../img/pacman.svg

   İlk küme dışbükey değildir ve diğer ikisi dışbükeydir.


Onlarla bir şeyler yapamazsanız, kendi başlarına tanımlar özellikle
yararlı değildir. Bu durumda :numref:`fig_convex_intersect` şeklinde
gösterildiği gibi kesişimlere bakabiliriz. :math:`\mathcal{X}` ve
:math:`\mathcal{Y}`'nin dışbükey kümeler olduğunu varsayalım. O halde
:math:`\mathcal{X} \cap \mathcal{Y}` de dışbükeydir. Bunu görmek için
herhangi bir :math:`a, b \in \mathcal{X} \cap \mathcal{Y}`'yi düşünün.
:math:`\mathcal{X}` ve :math:`\mathcal{Y}` dışbükey olduğundan :math:`a`
ve :math:`b`'yi bağlayan doğru parçaları hem :math:`\mathcal{X}` hem de
:math:`\mathcal{Y}`'de bulunur. Bu göz önüne alındığında,
:math:`\mathcal{X} \cap \mathcal{Y}`'de de yer almaları gerekiyor,
böylece teoremimizi kanıtlıyor.

.. _fig_convex_intersect:

.. figure:: ../img/convex-intersect.svg

   İki dışbükey kümenin kesişimi dışbükeydir.


Bu sonucu az çaba ile güçlendirebiliriz: Dışbükey kümeler
:math:`\mathcal{X}_i` göz önüne alındığında, kesişmeleri
:math:`\cap_{i} \mathcal{X}_i` dışbükeydir. Tersinin doğru olmadığını
görmek için, iki ayrık küme
:math:`\mathcal{X} \cap \mathcal{Y} = \emptyset` düşünün. Şimdi
:math:`a \in \mathcal{X}` ve :math:`b \in \mathcal{Y}`'yi seçin.
:math:`a` ve :math:`b`'yi birbirine bağlayan :numref:`fig_nonconvex`
içindeki doğru parçasının, :math:`\mathcal{X}`'da veya
:math:`\mathcal{Y}`'da olmayan bir kısım içermesi gerekir, çünkü
:math:`\mathcal{X} \cap \mathcal{Y} = \emptyset` olduğunu varsaydık.
Dolayısıyla doğru parçası :math:`\mathcal{X} \cup \mathcal{Y}`'da da
değildir, bu da genel olarak dışbükey kümelerin birleşimlerinin dışbükey
olması gerekmediğini kanıtlar.

.. _fig_nonconvex:

.. figure:: ../img/nonconvex.svg

   İki dışbükey kümenin birleşiminin dışbükey olması gerekmez.


Derin öğrenmedeki problemler genellikle dışbükey kümeler üzerinde
tanımlanır. Örneğin, :math:`\mathbb{R}^d`, gerçek sayıların :math:`d`
boyutlu vektörleri kümesi, bir dışbükey kümedir (sonuçta,
:math:`\mathbb{R}^d` içindeki herhangi iki nokta arasındaki çizgi
:math:`\mathbb{R}^d` içinde kalır). Bazı durumlarda
:math:`\{\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \text{ ve } \|\mathbf{x}\| \leq r\}`
tarafından tanımlanan :math:`r` yarıçap topları gibi sınırlanmış
uzunlukta değişkenlerle çalışırız.

Dışbükey İşlevler
~~~~~~~~~~~~~~~~~

Artık dışbükey kümelere sahip olduğumuza göre *dışbükey fonksiyonları*
:math:`f`'yi tanıtabiliriz. Bir dışbükey :math:`\mathcal{X}` kümesi
verildiğinde, eğer tüm :math:`x, x' \in \mathcal{X}` için ve elimizdeki
tüm :math:`\lambda \in [0, 1]` için aşağıdaki ifade tutarsa
:math:`f: \mathcal{X} \to \mathbb{R}` işlevi *dışbükeydir*:

.. math:: \lambda f(x) + (1-\lambda) f(x') \geq f(\lambda x + (1-\lambda) x').

Bunu göstermek için birkaç işlev çizelim ve hangilerinin gereksinimi
karşıladığını kontrol edelim. Aşağıda hem dışbükey hem de dışbükey
olmayan birkaç fonksiyon tanımlıyoruz.



.. raw:: html

     <div class="mdl-tabs mdl-js-tabs mdl-js-ripple-effect"><div class="mdl-tabs__tab-bar code"><a href="#mxnet-3-0" onclick="tagClick('mxnet'); return false;" class="mdl-tabs__tab is-active">mxnet</a><a href="#pytorch-3-1" onclick="tagClick('pytorch'); return false;" class="mdl-tabs__tab ">pytorch</a><a href="#tensorflow-3-2" onclick="tagClick('tensorflow'); return false;" class="mdl-tabs__tab ">tensorflow</a></div>



.. raw:: html

     <div class="mdl-tabs__panel is-active" id="mxnet-3-0">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    f = lambda x: 0.5 * x**2  # Dışbükey
    g = lambda x: np.cos(np.pi * x)  # Dışbükey olmayan
    h = lambda x: np.exp(0.5 * x)  # Dışbükey
    
    x, segment = np.arange(-2, 2, 0.01), np.array([-1.5, 1])
    d2l.use_svg_display()
    _, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
    for ax, func in zip(axes, [f, g, h]):
        d2l.plot([x, segment], [func(x), func(segment)], axes=ax)



.. figure:: output_convexity_94e148_15_0.svg




.. raw:: html

     </div>



.. raw:: html

     <div class="mdl-tabs__panel " id="pytorch-3-1">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    f = lambda x: 0.5 * x**2  # Dışbükey
    g = lambda x: torch.cos(np.pi * x)  # Dışbükey olmayan
    h = lambda x: torch.exp(0.5 * x)  # Dışbükey
    
    x, segment = torch.arange(-2, 2, 0.01), torch.tensor([-1.5, 1])
    d2l.use_svg_display()
    _, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
    for ax, func in zip(axes, [f, g, h]):
        d2l.plot([x, segment], [func(x), func(segment)], axes=ax)



.. figure:: output_convexity_94e148_18_0.svg




.. raw:: html

     </div>



.. raw:: html

     <div class="mdl-tabs__panel " id="tensorflow-3-2">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    f = lambda x: 0.5 * x**2  # Dışbükey
    g = lambda x: tf.cos(np.pi * x)  # Dışbükey olmayan
    h = lambda x: tf.exp(0.5 * x)  # Dışbükey
    
    x, segment = tf.range(-2, 2, 0.01), tf.constant([-1.5, 1])
    d2l.use_svg_display()
    _, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
    for ax, func in zip(axes, [f, g, h]):
        d2l.plot([x, segment], [func(x), func(segment)], axes=ax)



.. figure:: output_convexity_94e148_21_0.svg




.. raw:: html

     </div>



.. raw:: html

     </div>

Beklendiği gibi kosinüs fonksiyonu *dışbükey* olmayan\*, parabol ve
üstel fonksiyon ise dışbükeydir. :math:`\mathcal{X}`'in dışbükey bir
küme olması koşulunun anlamlı olması için gerekli olduğunu unutmayın.
Aksi takdirde :math:`f(\lambda x + (1-\lambda) x')`'in sonucu iyi
tanımlanmış olmayabilir.

Jensen'ın Eşitsizliği
~~~~~~~~~~~~~~~~~~~~~

Bir dışbükey :math:`f` fonksiyonu göz önüne alındığında, en kullanışlı
matematiksel araçlardan biri *Jensen eşitsizliği*\ dir. Dışbükeylik
tanımının genelleştirilmesi anlamına gelir:

.. math:: \sum_i \alpha_i f(x_i)  \geq f\left(\sum_i \alpha_i x_i\right)    \text{ ve }    E_X[f(X)]  \geq f\left(E_X[X]\right),
   :label: eq_jensens-inequality

burada :math:`\alpha_i` negatif olmayan gerçel sayılar
:math:`\sum_i \alpha_i = 1` ve :math:`X` rasgele bir değişkenlerdir.
Başka bir deyişle, dışbükey bir fonksiyonun beklentisi, ikincisinin
genellikle daha basit bir ifade olduğu bir beklentinin dışbükey
işlevinden daha az değildir. İlk eşitsizliği kanıtlamak için,
dışbükeylik tanımını her seferinde toplamdaki bir terime tekrar tekrar
uygularız.

Jensen'in eşitsizliğinin yaygın uygulamalarından biri daha karmaşık bir
ifadeyi daha basit bir ifadeyle bağlamaktır. Örneğin, uygulaması kısmen
gözlenen rastgele değişkenlerin log olabilirliği ile ilgili olabilir.
Yani, kullandığımız

.. math:: E_{Y \sim P(Y)}[-\log P(X \mid Y)] \geq -\log P(X),

çünkü :math:`\int P(Y) P(X \mid Y) dY = P(X)`. Bu, varyasyonel
yöntemlerde kullanılabilir. Burada :math:`Y` tipik olarak gözlemlenmeyen
rastgele değişkendir, :math:`P(Y)` bunun nasıl dağılabileceğine dair en
iyi tahmindir ve :math:`P(X)`, :math:`Y`'nin integral uygulandığı
dağılımdır. Örneğin, öbeklemede :math:`Y` küme etiketleri olabilir ve
:math:`P(X \mid Y)` öbek etiketleri uygularken üretici modeldir.

Özellikler
----------

Dışbükey işlevler birçok yararlı özelliğe sahiptir. Aşağıda yaygın
olarak kullanılan birkaç tanesini tanımlıyoruz.

Yerel Minimum Küresel Minimum Olduğunda
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Her şeyden önce, dışbükey işlevlerin yerel minimumu da küresel
minimumdur. Bunu aşağıdaki gibi tezatlıklarla kanıtlayabiliriz.

Bir dışbükey küme :math:`\mathcal{X}` üzerinde tanımlanmış bir dışbükey
fonksiyon :math:`f` düşünün. :math:`x^{\ast} \in \mathcal{X}`'ın yerel
bir minimum olduğunu varsayalım: Küçük bir pozitif :math:`p` değeri
vardır, öyle ki :math:`x \in \mathcal{X}` için
:math:`0 < |x - x^{\ast}| \leq p` elimizde :math:`f(x^{\ast}) < f(x)`.

Yerel minimum :math:`x^{\ast}`'in :math:`f`'nin küresel minimumu
olmadığını varsayalım: :math:`f(x') < f(x^{\ast})` için
:math:`x' \in \mathcal{X}` vardır. Ayrıca :math:`\lambda \in [0, 1)`
vardır, örneğin :math:`\lambda = 1 - \frac{p}{|x^{\ast} - x'|}` öyle ki
:math:`0 < |\lambda x^ {\ast} + (1-\lambda) x' - x^{\ast}| \leq p`.

Ancak, dışbükey fonksiyonların tanımına göre,

.. math::

   \begin{aligned}
       f(\lambda x^{\ast} + (1-\lambda) x') &\leq \lambda f(x^{\ast}) + (1-\lambda) f(x') \\
       &< \lambda f(x^{\ast}) + (1-\lambda) f(x^{\ast}) \\
       &= f(x^{\ast}),
   \end{aligned}

bu :math:`x^{\ast}`'in yerel bir minimum olduğu ifadesinde
çelişmektedir. Bu nedenle, :math:`x' \in \mathcal{X}` için
:math:`f(x') < f(x^{\ast})` yok. Yerel minimum :math:`x^{\ast}` da
küresel minimum değerdir.

Örneğin, dışbükey işlev :math:`f(x) = (x-1)^2` yerel minimum :math:`x=1`
değerine sahiptir ve bu da küresel minimum değerdir.



.. raw:: html

     <div class="mdl-tabs mdl-js-tabs mdl-js-ripple-effect"><div class="mdl-tabs__tab-bar code"><a href="#mxnet-5-0" onclick="tagClick('mxnet'); return false;" class="mdl-tabs__tab is-active">mxnet</a><a href="#pytorch-5-1" onclick="tagClick('pytorch'); return false;" class="mdl-tabs__tab ">pytorch</a><a href="#tensorflow-5-2" onclick="tagClick('tensorflow'); return false;" class="mdl-tabs__tab ">tensorflow</a></div>



.. raw:: html

     <div class="mdl-tabs__panel is-active" id="mxnet-5-0">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    f = lambda x: (x - 1) ** 2
    d2l.set_figsize()
    d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')



.. figure:: output_convexity_94e148_27_0.svg




.. raw:: html

     </div>



.. raw:: html

     <div class="mdl-tabs__panel " id="pytorch-5-1">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    f = lambda x: (x - 1) ** 2
    d2l.set_figsize()
    d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')



.. figure:: output_convexity_94e148_30_0.svg




.. raw:: html

     </div>



.. raw:: html

     <div class="mdl-tabs__panel " id="tensorflow-5-2">

.. raw:: latex

   \diilbookstyleinputcell

.. code:: python

    f = lambda x: (x - 1) ** 2
    d2l.set_figsize()
    d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')



.. figure:: output_convexity_94e148_33_0.svg




.. raw:: html

     </div>



.. raw:: html

     </div>

Dışbükey fonksiyonlar için yerel minimum da küresel minimum olması çok
uygundur. Fonksiyonları en aza indirirsek “takılıp kalmayız” anlamına
gelir. Bununla birlikte, bunun birden fazla küresel minimum olamayacağı
veya bir tane bile var olabileceği anlamına gelmediğini unutmayın.
Örneğin, :math:`f(x) = \mathrm{max}(|x|-1, 0)` işlevi :math:`[-1, 1]`
aralığında minimum değerini alır. Tersine, :math:`f(x) = \exp(x)` işlevi
:math:`\mathbb{R}` üzerinde minimum bir değere ulaşmaz:
:math:`x \to -\infty` için :math:`0`'da asimtota dönüşür, ancak
:math:`x` için :math:`f(x) = 0` yoktur.

Dışbükey Fonksiyonların Aşağı Kümeleri Dışbükey Fonksiyonlardır
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Dışbükey fonksiyonların *aşağıdaki kümeleri* aracılığıyla dışbükey
kümeleri rahatça tanımlayabiliriz. Somut olarak, dışbükey bir
:math:`\mathcal{X}` kümesi üzerinde tanımlanan dışbükey bir :math:`f`
fonksiyonu verildiğinde, herhangi bir aşağı küme

.. math:: \mathcal{S}_b := \{x | x \in \mathcal{X} \text{ ve } f(x) \leq b\}

dışbükeydir.

Bunu çabucak kanıtlayalım. Herhangi bir :math:`x, x' \in \mathcal{S}_b`
için :math:`\lambda \in [0, 1]` oldukça
:math:`\lambda x + (1-\lambda) x' \in \mathcal{S}_b` olduğunu
göstermemiz gerektiğini hatırlayın. :math:`f(x) \leq b` ve
:math:`f(x') \leq b`'den dolayı, dışbükeyliğin tanımı gereği aşağıdaki
ifadeye sahip oluruz:

.. math:: f(\lambda x + (1-\lambda) x') \leq \lambda f(x) + (1-\lambda) f(x') \leq b.

Dışbükeylik ve İkinci Türevler
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

:math:`f: \mathbb{R}^n \rightarrow \mathbb{R}` fonksiyonunun ikinci
türevi varsa, :math:`f`'in dışbükey olup olmadığını kontrol etmek çok
kolaydır. Tek yapmamız gereken :math:`f`'ın Hessian'ının pozitif
yarı-kesin olup olmadığını kontrol etmektir:
:math:`\nabla^2f \succeq 0`, yani, :math:`\nabla^2f` Hessian matrisini
:math:`\mathbf{H}` ile ifade edersek
:math:`\mathbf{x}^\top \mathbf{H} \mathbf{x} \geq 0`
:math:`\mathbf{x} \in \mathbb{R}^n`. Örneğin,
:math:`f(\mathbf{x}) = \frac{1}{2} \|\mathbf{x}\|^2` işlevi
:math:`\nabla^2 f = \mathbf{1}`'ten dolayı dışbükeydir, yani Hessian bir
birim matrisdir.

Biçimsel olarak, çift türevlenebilen tek boyutlu bir fonksiyon
:math:`f: \mathbb{R} \rightarrow \mathbb{R}`, sadece ve sadece ikinci
türevi :math:`f'' \geq 0` ise dışbükeydir. Herhangi bir çift
türevlenebilen çok boyutlu fonksiyon
:math:`f: \mathbb{R}^{n} \rightarrow \mathbb{R}`, sadece ve sadece
Hessian :math:`\nabla^2f \succeq 0` ise dışbükey olur.

İlk olarak, tek boyutlu durumu kanıtlamamız gerekiyor. :math:`f`'nin
dışbükeyliğinin :math:`f'' \geq 0`'ı ima ettiğini görmek için

.. math:: \frac{1}{2} f(x + \epsilon) + \frac{1}{2} f(x - \epsilon) \geq f\left(\frac{x + \epsilon}{2} + \frac{x - \epsilon}{2}\right) = f(x).

İkinci türev sonlu farklar üzerindeki limitle verildiğinde:

.. math:: f''(x) = \lim_{\epsilon \to 0} \frac{f(x+\epsilon) + f(x - \epsilon) - 2f(x)}{\epsilon^2} \geq 0.

:math:`f'' \geq 0`'ı görmek :math:`f`'nin dışbükey olduğu anlamına
gelir, burada :math:`f'' \geq 0`'in :math:`f'`'nin monoton olarak
azalmayan bir işlev olduğunu gösterdiğini kullandık. :math:`a < x < b`
:math:`\mathbb{R}`'de üç nokta olsun, öyleki
:math:`x = (1-\lambda)a + \lambda b` ve :math:`\lambda \in (0, 1)`
olsun. Ortalama değer teoremine göre, öyle :math:`\alpha \in [a, x]` ve
:math:`\beta \in [x, b]` vardır ki:

.. math:: f'(\alpha) = \frac{f(x) - f(a)}{x-a} \text{ and } f'(\beta) = \frac{f(b) - f(x)}{b-x}.

Monotonluktan dolayı :math:`f'(\beta) \geq f'(\alpha)`, dolayısıyla

.. math:: \frac{x-a}{b-a}f(b) + \frac{b-x}{b-a}f(a) \geq f(x).

Çünkü :math:`x = (1-\lambda)a + \lambda b`,

.. math:: \lambda f(b) + (1-\lambda)f(a) \geq f((1-\lambda)a + \lambda b),

böylece dışbükeyliği kanıtlıyoruz.

İkincisi, çok boyutlu durumu kanıtlamadan önce bir önsava (lemma)
ihtiyacımız var: :math:`f: \mathbb{R}^n \rightarrow \mathbb{R}`, sadece
ve sadece :math:`\mathbf{x}, \mathbf{y} \in \mathbb{R}^n`

.. math:: g(z) \stackrel{\mathrm{def}}{=} f(z \mathbf{x} + (1-z)  \mathbf{y}) \text{ öyle ki } z \in [0,1]

dışbükey ise dışbükeydir.

:math:`f`'nin dışbükeyliğinin :math:`g`'nin dışbükey olduğunu ima
ettiğini kanıtlamak için, tüm :math:`a, b, \lambda \in [0, 1]` için
(böylece :math:`0 \leq \lambda a + (1-\lambda) b \leq 1`)

.. math::

   \begin{aligned} &g(\lambda a + (1-\lambda) b)\\
   =&f\left(\left(\lambda a + (1-\lambda) b\right)\mathbf{x} + \left(1-\lambda a - (1-\lambda) b\right)\mathbf{y} \right)\\
   =&f\left(\lambda \left(a \mathbf{x} + (1-a)  \mathbf{y}\right)  + (1-\lambda) \left(b \mathbf{x} + (1-b)  \mathbf{y}\right) \right)\\
   \leq& \lambda f\left(a \mathbf{x} + (1-a)  \mathbf{y}\right)  + (1-\lambda) f\left(b \mathbf{x} + (1-b)  \mathbf{y}\right) \\
   =& \lambda g(a) + (1-\lambda) g(b).
   \end{aligned}

Tersini kanıtlamak için, tüm :math:`\lambda \in [0, 1]` ise şunu
gösterebiliriz:

.. math::

   \begin{aligned} &f(\lambda \mathbf{x} + (1-\lambda) \mathbf{y})\\
   =&g(\lambda \cdot 1 + (1-\lambda) \cdot 0)\\
   \leq& \lambda g(1)  + (1-\lambda) g(0) \\
   =& \lambda f(\mathbf{x}) + (1-\lambda) g(\mathbf{y}).
   \end{aligned}

Son olarak, yukarıdaki önsav ve tek boyutlu durumun sonucunu kullanarak,
çok boyutlu durum aşağıdaki gibi kanıtlanabilir. Çok boyutlu bir
fonksiyon :math:`f: \mathbb{R}^n \rightarrow \mathbb{R}`, sadece ve
sadece :math:`\mathbf{x}, \mathbf{y} \in \mathbb{R}^n`
:math:`g(z) \stackrel{\mathrm{def}}{=} f(z \mathbf{x} + (1-z) \mathbf{y})`,
burada :math:`z \in [0,1]`, dışbükey ise dışbükey olur. Tek boyutlu
duruma göre, bu sadece ve sadece
:math:`g'' = (\mathbf{x} - \mathbf{y})^\top \mathbf{H}(\mathbf{x} - \mathbf{y}) \geq 0`
(:math:`\mathbf{H} \stackrel{\mathrm{def}}{=} \nabla^2f`) tüm
:math:`\mathbf{x}, \mathbf{y} \in \mathbb{R}^n` için
(:math:`\mathbf{H} \stackrel{\mathrm{def}}{=} \nabla^2f`) olursa tutar,
ki bu da pozitif yarı-kesin matrislerin tanımı
:math:`\mathbf{H} \succeq 0` ile eşdeğerdir.

Kısıtlamalar
------------

Dışbükey optimizasyonun güzel özelliklerinden biri, kısıtlamaları
verimli bir şekilde ele almamıza izin vermesidir. Yani, *kısıtlı
optimizasyon* biçimdeki sorunlarını çözmemize izin verir:

.. math::

   \begin{aligned} \mathop{\mathrm{minimize~et~}}_{\mathbf{x}} & f(\mathbf{x}) \\
       \text{ tabi } & c_i(\mathbf{x}) \leq 0 \text{ her } i \in \{1, \ldots, n\} \text{ için },
   \end{aligned}

burada :math:`f` amaç işlevi ve :math:`c_i` fonksiyonları kısıtlama
işlevleridir. Bunun ne yaptığını görmek için
:math:`c_1(\mathbf{x}) = \|\mathbf{x}\|_2 - 1` durumunu düşünün. Bu
durumda :math:`\mathbf{x}` parametreleri birim topla sınırlıdır. İkinci
bir kısıtlama :math:`c_2(\mathbf{x}) = \mathbf{v}^\top \mathbf{x} + b`
ise, bu yarı uzayda yatan :math:`\mathbf{x}`'lerin tümüne karşılık
gelir. Her iki kısıtlama da aynı anda tatmin etmek, bir topun bir
diliminin seçilmesi anlamına gelir.

Lagrangian
~~~~~~~~~~

Genel olarak, kısıtlı bir optimizasyon problemini çözmek zordur. Bunu
ele almanın bir yolu fizikten kaynaklanan basit bir sezgidir. Bir
kutunun içinde bir topu hayal edin. Top en düşük yere yuvarlanacak ve
yerçekimi kuvvetleri, kutunun kenarlarının topa uygulayabileceği
kuvvetlerle dengelenecektir. Kısacası, amaç fonksiyonun gradyanı (yani,
yerçekimi), kısıtlama fonksiyonunun gradyanı ile dengelenecektir (topun
duvarlarca “geri iterek” kutunun içinde kalması gerekir). Bazı
kısıtlamaların aktif olmayabileceğini unutmayın: Topun dokunmadığı
duvarlar topa herhangi bir güç uygulayamayacaktır.

*Lagrangian* :math:`L`'nin türetilmesi es geçersek, yukarıdaki akıl
yürütme, aşağıdaki eyer noktası optimizasyonu problemi ile ifade
edilebilir:

.. math:: L(\mathbf{x}, \alpha_1, \ldots, \alpha_n) = f(\mathbf{x}) + \sum_{i=1}^n \alpha_i c_i(\mathbf{x}) \text{ burada } \alpha_i \geq 0.

Burada :math:`\alpha_i` (:math:`i=1,\ldots,n`) değişkenleri,
kısıtlamaların doğru şekilde uygulanmasını sağlayan *Lagrange
çarpanları* olarak adlandırılır. Tüm :math:`i`'lerde
:math:`c_i(\mathbf{x}) \leq 0` sağlamak için yeterince büyük seçilir.
Örneğin, :math:`c_i(\mathbf{x}) < 0`'ın doğal olarak
:math:`c_i(\mathbf{x}) < 0`'ın :math:`\alpha_i = 0`'ı seçtiği herhangi
bir :math:`\mathbf{x}` için. Üstelik, bu, :math:`L`'nin tüm
:math:`\alpha_i`'ya göre *maksimize edilmek* ve aynı anda
:math:`\mathbf{x}`'a göre *minimize edilmek* istendiği bir eyer noktası
optimizasyon problemidir.
:math:`L(\mathbf{x}, \alpha_1, \ldots, \alpha_n)` fonksiyonuna nasıl
ulaşılacağını açıklayan zengin bir yazın birikimi vardır. Amacımız için,
asıl kısıtlı optimizasyon probleminin en iyi şekilde çözüldüğü :math:`L`
eyer noktasının nerede olduğunu bilmek yeterlidir.

Cezalar
~~~~~~~

Kısıtlı optimizasyon sorunlarını en azından *yaklaşık* tatmin etmenin
bir yolu Lagrangian :math:`L`'yi uyarlamaktır.
:math:`c_i(\mathbf{x}) \leq 0`'ı tatmin etmek yerine
:math:`\alpha_i c_i(\mathbf{x})`'i amaç fonksiyonu :math:`f(x)`'e
ekliyoruz. Bu, kısıtlamaların aşırı ihlal edilmemesini sağlar.

Aslında, başından beri bu hileyi kullanıyorduk.
:numref:`sec_weight_decay` içindeki ağırlık sönümünü düşünün. İçinde
:math:`\frac{\lambda}{2} \|\mathbf{w}\|^2`'i amaç işlevine
:math:`\mathbf{w}`'nin çok büyük olmamasını sağlamak için ekliyoruz.
Kısıtlı optimizasyon bakış açısından bunun bize bazı :math:`r` yarıçapı
için :math:`\|\mathbf{w}\|^2 - r^2 \leq 0` sağlayacağını görebilirsiniz.
:math:`\lambda` değerinin ayarlanması, :math:`\mathbf{w}`'nin boyutunu
değiştirmemize izin verir.

Genel olarak, ceza eklemek, yaklaşık kısıtlama tatminini sağlamanın iyi
bir yoludur. Pratikte bunun tam tatminden çok daha gürbüz olduğu ortaya
çıkıyor. Dahası, dışbükey olmayan problemler için, dışbükey durumdaki
(örn., eniyilik) kesin yaklaşımı çok çekici hale getiren özelliklerin
çoğu artık tutmuyor.

İzdüşümler
~~~~~~~~~~

Kısıtlamaları tatmin etmek için alternatif bir strateji izdüşümlerdir.
Yine, daha önce onlarla karşılaştık, örneğin,
:numref:`sec_rnn_scratch` içinde gradyan kırpma ile uğraşırken. Orada
bir gradyan :math:`\theta` ile sınırlanmış uzunluğa sahip olmasını
sağladık

.. math:: \mathbf{g} \leftarrow \mathbf{g} \cdot \mathrm{min}(1, \theta/\|\mathbf{g}\|).

Bu, :math:`\theta` yarıçaplı top üzerine :math:`\mathbf{g}`'nin bir
*izdüşümü* olduğu ortaya çıkarıyor. Daha genel olarak, bir dışbükey
kümedeki bir izdüşüm :math:`\mathcal{X}` şöyle tanımlanır:

.. math:: \mathrm{Proj}_\mathcal{X}(\mathbf{x}) = \mathop{\mathrm{argmin}}_{\mathbf{x}' \in \mathcal{X}} \|\mathbf{x} - \mathbf{x}'\|,

ki buda :math:`\mathcal{X}` içinde :math:`\mathbf{x}`'e en yakın
noktadır.

.. _fig_projections:

.. figure:: ../img/projections.svg

   Dışbükey izdüşümler.


İzdüşümlerin matematiksel tanımı biraz soyut gelebilir.
:numref:`fig_projections` bunu biraz daha net bir şekilde açıklıyor.
İçinde iki dışbükey küme, bir daire ve bir elmas var. Her iki kümedeki
noktalar (sarı) izidüşümler esnasında değişmeden kalır. Her iki kümenin
(siyah) dışındaki noktalar, asıl noktalara (siyah) yakın olan kümelerin
içindeki (kırmızı) noktalara yansıtılır. :math:`L_2` topları için yön
değişmeden kalırken, elmas durumunda görülebileceği gibi genel olarak
böyle olması gerekmez.

Dışbükey izdüşümlerin kullanımlarından biri seyrek ağırlık vektörlerini
hesaplamaktır. Bu durumda ağırlık vektörlerini :math:`L_1` topuna
izdüşürüyoruz, bu da :numref:`fig_projections` içinde elmas durumunun
genelleştirilmiş bir versiyonu olan bir :math:`L_1` topuna
izdüşürüyoruz.

Özet
----

Derin öğrenme bağlamında dışbükey fonksiyonların temel amacı
optimizasyon algoritmalarını özendirmek ve bunları ayrıntılı olarak
anlamamıza yardımcı olmaktır. Sonrasında gradyan iniş ve rasgele gradyan
iniş buna göre nasıl türetilebilir göreceksiniz.

-  Dışbükey kümelerin kesişimleri dışbükeydir. Birleşimleri değil.
-  Dışbükey bir fonksiyonun beklentisi, bir beklentinin dışbükey
   işlevinden daha az değildir (Jensen eşitsizliği).
-  İki kez türevlenebilen bir fonksiyon, sadece ve sadece Hessian
   (ikinci türevlerin bir matrisi) pozitif yarı kesin ise dışbükeydir.
-  Dışbükey kısıtlamalar Lagrangian aracılığıyla eklenebilir.
   Uygulamada, onları sadece amaç işlevine bir ceza ile ekleyebiliriz.
-  İzdüşümler, orijinal noktaları dışbükey kümedeki en yakın noktalarla
   eşleştirirler.

Alıştırmalar
------------

1. Kümedeki noktalar arasındaki tüm çizgileri çizerek ve çizgilerin
   içerilip içerilmediğine kontrol ederek bir kümenin dışbükeyliğini
   doğrulamak istediğimizi varsayalım.

   1. Sadece sınırdaki noktaları kontrol etmenin yeterli olduğunu
      kanıtlayın.
   2. Sadece kümenin köşelerini kontrol etmenin yeterli olduğunu
      kanıtlayın.

2. :math:`p`-normunu kullanarak
   :math:`\mathcal{B}_p[r] \stackrel{\mathrm{def}}{=} \{\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \text{ ve } \|\mathbf{x}\|_p \leq r\}`
   yarıçap topu :math:`r` ile belirtin. Tüm :math:`p \geq 1` için
   :math:`\mathcal{B}_p[r]`'in dışbükey olduğunu kanıtlayın.
3. Verilen dışbükey fonksiyonlar :math:`f` ve :math:`g` için,
   :math:`\mathrm{max}(f, g)`'nin de dışbükey olduğunu gösterin.
   :math:`\mathrm{min}(f, g)`'nin dışbükey olmadığını kanıtlayın.
4. Softmax fonksiyonunun normalleştirilmesinin dışbükey olduğunu
   kanıtlayın. Daha özel olarak :math:`f(x) = \log \sum_i \exp(x_i)`'in
   dışbükeyliğini kanıtlayın.
5. Doğrusal alt uzayların, yani
   :math:`\mathcal{X} = \{\mathbf{x} | \mathbf{W} \mathbf{x} = \mathbf{b}\}`'nin
   dışbükey kümeler olduğunu kanıtlayın.
6. :math:`\mathbf{b} = \mathbf{0}` ile doğrusal alt uzaylarda
   :math:`\mathrm{Proj}_\mathcal{X}` izdüşümünün bazı :math:`\mathbf{M}`
   matrisi için :math:`\mathbf{M} \mathbf{x}` olarak yazılabileceğini
   kanıtlayın.
7. İki kez türevlenebilir dışbükey :math:`f` fonksiyonları için, bazı
   :math:`\xi \in [0, \epsilon]` için
   :math:`f(x + \epsilon) = f(x) + \epsilon f'(x) + \frac{1}{2} \epsilon^2 f''(x + \xi)`
   yazabileceğimizi gösterin.
8. Verilen :math:`\mathbf{w} \in \mathbb{R}^d` vektörü ve
   :math:`\|\mathbf{w}\|_1 > 1` ile :math:`L_1` birim topu üzerindeki
   izdüşümü hesaplayın.

   1. Bir ara adım olarak
      :math:`\|\mathbf{w} - \mathbf{w}'\|^2 + \lambda \|\mathbf{w}'\|_1`
      cezalandırılmış hedefini yazın ve belirli bir :math:`\lambda > 0`
      için çözümü hesaplayın.
   2. :math:`\lambda`'nin “doğru” değerini çok fazla deneme yanılma
      olmadan bulabilir misiniz?

9. Bir dışbükey küme :math:`\mathcal{X}` ve iki vektör
   :math:`\mathbf{x}` ve :math:`\mathbf{y}` göz önüne alındığında,
   izdüşümlrin mesafeleri asla artırmadığını kanıtlayın, yani
   :math:`\|\mathbf{x} - \mathbf{y}\| \geq \|\mathrm{Proj}_\mathcal{X}(\mathbf{x}) - \mathrm{Proj}_\mathcal{X}(\mathbf{y})\|`.

`Tartışmalar <https://discuss.d2l.ai/t/350>`__