Prof. Drs. T. Basaruddin, Ph.D.

Video ini membahas teknik penyelesaian umum dalam optimasi nonlinier menggunakan metode Gradient Descent. Konsep dasar pencarian titik terendah fungsi objektif diilustrasikan seperti mencari titik terendah pada permukaan. Dengan menggunakan skema iteratif, kita mengikuti langkah-langkah menuju titik terendah dengan menentukan arah perjalanan dan panjang langkah. Gradient Descent merupakan teknik populer dalam optimasi nonlinier, di antaranya adalah metode steepest descent yang mengikuti arah tercuram dari gradient fungsi. Dalam metode ini, arah perjalanan ditentukan sebagai minus dari gradient fungsi untuk mencapai titik minimum.

Mencari titik optimum, dalam hal ini titik minimum dari suatu fungsi objektif itu bagaikan kita mencari suatu titik terendah pada suatu permukaan.

Jadi kita akan menggunakan prinsip-prinsip dasar dalam mencari titik terendah dari suatu surface atau permukaan

dengan cara mengenerate suatu iteratif skema atau skema iteratif yang akan mengiring kita secara tahap demi tahap menuju titik terendah tersebut.

Saya kasih ilustrasi, misalkan ini adalah titik terendah yang ingin kita tuju.

Ini adalah titik terendahnya, bisa dibayangkan ini surface permukaan.

Saya katakanlah berdiri di sini dan saya ingin menuju titik ini.

Posisi saya berdiri ini saya katakan namanya X0.

Sekarang apa yang harus saya kembangkan adalah saya membutuhkan cara untuk menuju titik ini, tapi saya tidak tahu titik ini berada di mana.

Yang saya tahu adalah di sekitar saya berdiri, bahwa kalau saya ingin mencari titik minimizer, titik terendah,

mestinya saya hanya akan scan di sekitar saya, kemudian cari saya yang arahnya turun.

Tapi setelah saya menemukan arah turun tersebut, saya juga harus menetapkan seberapa jauh saya berjalan ke arah turun tersebut.

Misalkan di sekitar sini sebetulnya arah turunnya ke arah sana.

Ini adalah arah yang turun waktu tempat saya berdiri di sini, karena permukaan itu tidak harus selalu seperti mangkok.

Bisa saja dia berubah-ubah dari konturnya.

Sehingga dari titik ini saya sudah pilih arah saya berjalan.

Nah, arah ini saya akan namakan search direction kita sebut sebagai P.

Jadi ada arah perjalanan atau arah pencarian dari X0, saya akan bergerak ke arah vektor P.

Tapi searah ini saya harus tetapkan mau berapa langkah atau berapa panjang, berapa jauh saya berjalan searah P.

Nah, ini akan saya sebut sebagai alfa, yaitu panjang langkah yang harus saya ambil searah P.

Jadi secara keseluruhan saya akan mendapatkan, oh kalau begitu X1 itu akan sama dengan X0 ditambah alfa kali P.

Jadi saya berada di titik X0, bergerak searah P, jadi P ini menentukan arah saya bergerak, tapi pada arah P tersebut saya harus melangkah sejauh alfa.

Nah, inilah prinsip atau pola umum yang akan kita kembangkan dan ini sama sekali tidak membutuhkan hessian.

Jadi matrik hessian tidak kita butuhkan, karena setiap saat saya hanya akan menentukan arahnya kemana dan berapa panjang langkah menuju ke sana.

Di machine learning, alfa ini kita seringkali sebut sebagai learning rate atau laju pembelajaran yang kita tetapkan sebagai konstan.

Nah, tapi sebetulnya kalau sebentar lagi akan kita lihat bahwa alfa itu mestinya tidak konstan, akan tergantung pada kontur dari permukaan yang ingin kita telusuri dan kita cari titik minimumnya.

Kadang-kadang kita bisa jalan agak jauh, kadang-kadang cukup pendek, dia mestinya adaptif, tidak mungkin kita tetapkan secara konstan.

Nah, teknik ini kemudian akan kita kembangkan menjadi teknik yang disebut dengan gradient descent.

Jadi saya akan mencari arah turun, itu saja.

Nah, di antara gradient descent ini yang paling populer antara lain adalah yang disebut dengan steepest descent.

Arah yang paling curam, jadi kalau kita berada di permukaan maka arah yang paling curam itu adalah negatif dari arah gradient.

Jadi kalau saya punya fungsi untuk memudahkan ilustrasi saja, misalnya saya punya fungsi skalar seperti ini.

Saya berada di sini, saya ingin mencari titik ini sebagai titik minimum.

Saya berada di sini ingin mencapai titik minimum ini.

Coba perhatikan, pada titik ini saya punya grad.

Kalau kita lihat gambar ini, maka di titik ini gradientnya adalah negatif karena fungsinya turun, minus.

Turunan pertamanya itu jadi coefficient arah atau tangan dari kiri singgung ini pasti negatif.

Karena dia negatif, maka saya harus ke arah kanan, berarti arah positif.

Saya melawan arah dari gradient, jadi minusnya.

Sebaliknya kalau saya berada di sini, perhatikan di sini dia naik, berarti ini positif, gradientnya positif.

Kalau gradientnya positif, maka saya harus ke kiri malah.

Jadi lagi-lagi kalau positif saya ke kiri, kalau negatif saya ke kanan.

Jadi arah dari yang turun itu pasti, yang tercuram turunnya adalah minus dari gradient.

Berarti kita sudah dapatkan sekarang P sama dengan minus dari grad F.

Dan ini yang kita akan coba untuk kembangkan sebagai metode yang pertama.