Шаг градиентного спуска. Решение СНУ

@ppasha · Регистрация: 05.03.2021

Author24 — интернет-сервис помощи студентам

Здравствуйте, разбираюсь с методами спуска. В данном примере решаю СНУ градиентным спуском (простейшая реализация). Возникло непонимание с выбором шага сходимости. Если его считать по формулам №1 и №2 или вообще сделать не изменяющимся, то корни находятся верно. При использовании формулы №3 возникают проблемы. Почему так ? Есть какая-то общая формула для выбора шага или совет, которым нужно придерживаться?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import numpy as np
 
 
  # Функция 
def F(x1, x2):
  return ((np.sin(x1-1) + x2 - 0.1)**2)  + ((x1 - np.sin(x2 + 1) - 0.8)**2)
 
   
         
 # Градиент
def Grad(x1, x2):
  return np.array([ 2 * x1 + 2* (x2 + np.sin(x1-1)-0.1)*np.cos(x1-1)-2*np.sin(x2+1) - 1.6, 
                2 * x2 - 2 *(x1 - np.sin(x2+1) - 0.8)*np.cos(x2+1) + 2*np.sin(x1-1) - 0.2])
  
 
   # сам метод 
 
def Gr_m(x1, x2):
 
  alpha = 0.1     # Шаг сходимости
 
  eps = 0.000001   # точность  
 
  X_prev = np.array([x1, x2])   
  
  X = X_prev - alpha * Grad(X_prev[0], X_prev[1])
 
 
  t = 50   # Необходимый параметр, если выбрать  шаг №1
  k = 0
 
  l, s, p = 0.1, 1, 0.5     # Необходимые параметры для варианта шага №2
  
 
 
  while np.linalg.norm(X - X_prev) > eps:
  
    
    X_prev = X.copy()
 
   
   # alpha = 1/min(k+1,t)     # Шаг №1
   # k = k + 1
 
   # alpha = l * ((s/(s+k))**p)   # Шаг №2
 
    alpha =F( X_prev[0] - alpha * Grad(X_prev[0], X_prev[1])[0],
            X_prev[1] - alpha * Grad(X_prev[0], X_prev[1])[1] )
   # Шаг №3. Не рабочий
       
    X = X_prev - alpha * Grad(X_prev[0], X_prev[1])         # Формула
 
  return X
    
 
 
result = Gr_m(0, 6)
 
print(result)

@Gdez · 18.10.2021, 11:49

ppasha, этот ответ?
[ 1.43071757 -0.31752263]

@ppasha · 18.10.2021, 12:06 **[ТС]**

Да, такой

Добавлено через 3 минуты
Gdez, да

@Gdez · 18.10.2021, 12:07

ppasha, для третьего варианта alpha не рассчитывается - она постоянна (в коде == 0.1)
Закомментируй строчки 47-48

@ppasha · 18.10.2021, 12:17 **[ТС]**

Gdez,Да, я пробовал. Так все работает, но разве третий вариант не должен предполагает наиболее быструю сходимость? Я хотел ускорить алгоритм, сделав alpha изменяющимся. Формула же вроде правильная. Или я что-то не понимаю?

@Gdez · 18.10.2021, 12:55

ppasha, извиняюсь

, вспомнил - этот (3) переменный шаг чувствителен к выбору начальной точки в зависимости от функции -> в Вашей функции при начальных "хо" или "уо" больше 1 первое же "дробление" шага приводит к его кратному увеличению -> формула содержит квадраты аргументов.
Поэтому начальную точку желательно брать с аргументами < 1.
И второе -> обычно вводят ограничение на счетчик "к" (чтобы долго не считало) -> в коде -> cnt (при выводе пишет количество циклов; можно убрать из "return'a")

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import numpy as np
 
 
  # Функция 
def F(x1, x2):
  return ((np.sin(x1-1) + x2 - 0.1)**2)  + ((x1 - np.sin(x2 + 1) - 0.8)**2)
 
   
         
 # Градиент
def Grad(x1, x2):
  return np.array([ 2 * x1 + 2* (x2 + np.sin(x1-1)-0.1)*np.cos(x1-1)-2*np.sin(x2+1) - 1.6, 
                2 * x2 - 2 *(x1 - np.sin(x2+1) - 0.8)*np.cos(x2+1) + 2*np.sin(x1-1) - 0.2])
  
 
   # сам метод 
 
def Gr_m(x1, x2, cnt=10000):
 
  alpha = 0.1    # Шаг сходимости
 
  eps = 0.000001   # точность  
 
  X_prev = np.array([x1, x2])   
  
  X = X_prev - alpha * Grad(X_prev[0], X_prev[1])
  
 
  t = 50   # Необходимый параметр, если выбрать  шаг №1
  k = 0
 
  l, s, p = 0.1, 1, 0.5     # Необходимые параметры для варианта шага №2
  
 
 
  while np.linalg.norm(X - X_prev) > eps and k < cnt:
  
    
    X_prev = X.copy()
 
   
    #alpha = 1/min(k+1,t)     # Шаг №1
    k = k + 1
 
    #alpha = l * ((s/(s+k))**p)   # Шаг №2
 
    alpha =F( X_prev[0] - alpha * Grad(X_prev[0], X_prev[1])[0],
            X_prev[1] - alpha * Grad(X_prev[0], X_prev[1])[1] )
    
   # Шаг №3. Не рабочий
       
    X = X_prev - alpha * Grad(X_prev[0], X_prev[1])         # Формула
    
  return X, k
    
 
 
result = Gr_m(0, 0)
 
print(result)

Добавлено через 11 минут
ppasha, добавил вычисление функции в конечной точке

Python
1
return X, k, F(*X)

Самый быстрый и самый точный - при постоянном alpha

@ppasha · 18.10.2021, 12:59 **[ТС]**

Gdez, Да, действительно. Если взять (0, 0), (0.3, 0.3), (0.4, 0.2), ... , то более-менее на корни правильно определяет, хотя если брать, к примеру, (0.3, 0.6), то уже перестаёт работать. Не знал об этом. Где можно подробнее все эти тонкости изучить? Есть какая-нибудь универсальная формула для переменного шага? Как его на практике обычно вычисляют ?

Добавлено через 1 минуту
Gdez, а разве на практике это не губит скорость?

@Gdez · 18.10.2021, 13:13

ppasha, http://www.machinelearning.ru/... ого_спуска
Глава "Градиентный метод с дроблением шага".
Там описывается доп условие для выбора alpha[k]

@ppasha · 18.10.2021, 13:15 **[ТС]**

Gdez, спасибо

@u235 · 18.10.2021, 15:07

ppasha, у вас функция содержит гармонические функции. Не удивительно, что у нее может быть множество локальных экстремумов. В какой экстремум попадет - зависит от начальной точки.

Новые блоги и статьи Все статьи Все блоги /
Чем асинхронная логика (схемотехника) лучше тактируемой, как я думаю, что помимо энергоэффективности - ещё и безопасность. Hrethgir 14.05.2025 Помимо огромного плюса в энергоэффективности, асинхронная логика - тотальный контроль над каждым совершённым тактом, а значит - безусловная безопасность, где безконтрольно не совершится ни одного. . .	Многопоточные приложения на C++ bytestream 14.05.2025 C++ всегда был языком, тесно работающим с железом, и потому особеннно эффективным для многопоточного программирования. Стандарт C++11 произвёл революцию, добавив в язык нативную поддержку потоков,. . .	Stack, Queue и Hashtable в C# UnmanagedCoder 14.05.2025 Каждый опытный разработчик наверняка сталкивался с ситуацией, когда невинный на первый взгляд List<T> превращался в узкое горлышко всего приложения. Причина проста: универсальность – это прекрасно,. . .	Как использовать OAuth2 со Spring Security в Java Javaican 14.05.2025 Протокол OAuth2 часто путают с механизмами аутентификации, хотя по сути это протокол авторизации. Представьте, что вместо передачи ключей от всего дома вашему другу, который пришёл полить цветы, вы. . .	Анализ текста на Python с NLTK и Spacy AI_Generated 14.05.2025 NLTK, старожил в мире обработки естественного языка на Python, содержит богатейшую коллекцию алгоритмов и готовых моделей. Эта библиотека отлично подходит для образовательных целей и. . .
Реализация DI в PHP Jason-Webb 13.05.2025 Когда я начинал писать свой первый крупный PHP-проект, моя архитектура напоминала запутаный клубок спагетти. Классы создавали другие классы внутри себя, зависимости жостко прописывались в коде, а о. . .	Обработка изображений в реальном времени на C# с OpenCV stackOverflow 13.05.2025 Объединение библиотеки компьютерного зрения OpenCV с современным языком программирования C# создаёт симбиоз, который открывает доступ к впечатляющему набору возможностей. Ключевое преимущество этого. . .	POCO, ACE, Loki и другие продвинутые C++ библиотеки NullReferenced 13.05.2025 В C++ разработки существует такое обилие библиотек, что порой кажется, будто ты заблудился в дремучем лесу. И среди этого многообразия POCO (Portable Components) – как маяк для тех, кто ищет. . .	Паттерны проектирования GoF на C# UnmanagedCoder 13.05.2025 Вы наверняка сталкивались с ситуациями, когда код разрастается до неприличных размеров, а его поддержка становится настоящим испытанием. Именно в такие моменты на помощь приходят паттерны Gang of. . .	Создаем CLI приложение на Python с Prompt Toolkit py-thonny 13.05.2025 Современные командные интерфейсы давно перестали быть черно-белыми текстовыми программами, которые многие помнят по старым операционным системам. CLI сегодня – это мощные, интуитивные и даже. . .

@Gdez 8815 / 4468 / 1862 Регистрация: 27.03.2020 Сообщений: 7,287
	18.10.2021, 11:49
	ppasha, этот ответ? [ 1.43071757 -0.31752263] 0

@ppasha 1 / 1 / 0 Регистрация: 05.03.2021 Сообщений: 50
	18.10.2021, 12:06 [ТС]
	Да, такой Добавлено через 3 минуты Gdez, да 0

@Gdez 8815 / 4468 / 1862 Регистрация: 27.03.2020 Сообщений: 7,287
	18.10.2021, 12:07
	ppasha, для третьего варианта alpha не рассчитывается - она постоянна (в коде == 0.1) Закомментируй строчки 47-48 0

@ppasha 1 / 1 / 0 Регистрация: 05.03.2021 Сообщений: 50
	18.10.2021, 12:17 [ТС]
	Gdez,Да, я пробовал. Так все работает, но разве третий вариант не должен предполагает наиболее быструю сходимость? Я хотел ускорить алгоритм, сделав alpha изменяющимся. Формула же вроде правильная. Или я что-то не понимаю? Миниатюры 0

@ppasha 1 / 1 / 0 Регистрация: 05.03.2021 Сообщений: 50
	18.10.2021, 12:59 [ТС]
	Gdez, Да, действительно. Если взять (0, 0), (0.3, 0.3), (0.4, 0.2), ... , то более-менее на корни правильно определяет, хотя если брать, к примеру, (0.3, 0.6), то уже перестаёт работать. Не знал об этом. Где можно подробнее все эти тонкости изучить? Есть какая-нибудь универсальная формула для переменного шага? Как его на практике обычно вычисляют ? Добавлено через 1 минуту Gdez, а разве на практике это не губит скорость? 0

@Gdez 8815 / 4468 / 1862 Регистрация: 27.03.2020 Сообщений: 7,287
	18.10.2021, 13:13
	ppasha, http://www.machinelearning.ru/... ого_спуска Глава "Градиентный метод с дроблением шага". Там описывается доп условие для выбора alpha[k] 1

@ppasha 1 / 1 / 0 Регистрация: 05.03.2021 Сообщений: 50
	18.10.2021, 13:15 [ТС]
	Gdez, спасибо 0

@u235 5454 / 2818 / 566 Регистрация: 07.11.2019 Сообщений: 4,648
	18.10.2021, 15:07
	ppasha, у вас функция содержит гармонические функции. Не удивительно, что у нее может быть множество локальных экстремумов. В какой экстремум попадет - зависит от начальной точки. 1

Опции темы