Category: Алгоритмы

06
Июл
2021

В Бельгии искусственный интеллект стыдит политиков, которые используют телефон на заседаниях. И это пугает

Бельгийский художник Дрис Депортер изобрел искусственный интеллект, который автоматически помечает политиков, которые используют телефоны на работе.
— Читать дальше «В Бельгии искусственный интеллект стыдит политиков, которые используют телефон на засе…

05
Июл
2021

🤖 Вариационные автоэнкодеры (VAE) для чайников – пошаговое руководство

Практическое руководство в стиле “сделай сам” с работающим кодом создания и обучения VAE для лиц знаменитостей на Keras.

Текст публикуется в переводе, автор статьи – Мишель Кана.

Эта статья познакомит вас со всем необходимым для начала работы с генеративными моделями. Мы предоставим пошаговое руководство по обучению условных VAE на наборах данных с большими изображениями и их применению для генерации новых размеченных изображений.

Мотивация

Зачем нужно генерировать новые данные, если в мире и так огромное количество данных? Согласно IDC, в мире более 18 зеттабайтов данных.

Большинство задач машинного обучения требуют размеченных данных, а получить высококачественные размеченные данные сложно. Если мы генерируем данные сами, мы всегда можем сделать их столько, сколько потребуется. Новые данные могут натолкнуть вас на новые идеи и предоставить новые возможности.

Как сгенерировать изображения, которых никто не видел?

Прочитав эту статью, вы узнаете, что такое Вариационный Автоэнкодер, и как создать ваш собственный для генерации новых изображений, которые никто никогда не видел. Мы объясним идеи и концепции, лежащие в его основе, без какой-либо математики.

Пример изображения и его реконструкции с помощью нашего кода VAE
Пример изображения и его реконструкции с помощью нашего кода VAE

Данные

Мы используем подмножество широко известного набора данных Знаменитостей, который поможет нам создать модель генерации лиц. Этот набор можно скачать с сайта CelebFacesA. Он предоставляет большой набор атрибутов лиц, содержащий более 200 тысяч изображений знаменитостей, для каждого из которых указано значение 40 атрибутов.

  • 10.177 личностей;
  • 202.599 изображений;
  • 5 важнейших локаций;
  • 40 бинарных атрибутов для каждого изображения.
        import pandas as pd

df_celeb = pd.read_csv('list_attr_celeba.csv')
df_celeb.head()
    

Ниже мы выбираем случайные лица и выводим их метаданные (атрибуты). Изображения имеют высоту 218 пикселей, ширину 178 пикселей и 3 цветовых канала.

        import matplotlib.pyplot as plt
import random
from skimage.io import imread

def show_sample_image(nb=3, df=df_celeb, verbose=True):
    f, ax = plt.subplots(1, nb, figsize=(10,5))
    for i in range(nb):
        idx = random.randint(0, df.shape[0]-1)
        img_id = df.loc[idx].image_id
        img_uri = 'img_align_celeba/' + img_id
        img = skimage.io.imread(img_uri)  
        if verbose:
            label = img_id
            for col in df.columns:
                if df.loc[idx][col]==1:
                    label = label + '\n' + col  
            if nb > 1:
                ax[i].imshow(img)
                ax[i].set_title(label)
            else:
                ax.imshow(img) 
                ax.set_title(label)
        
    return img, list(df.loc[idx][1:df.shape[1]])
  
sample_img, sample_img_meta = show_sample_image()
    

Что такое автоэнкодер (AE)?

Просмотрев лица тысяч знаменитостей, нейронная сеть может научиться генерировать лица людей, которых не существует.

Нейронные сети – это один из множества возможных методов, которые мы можем использовать для аппроксимации (приближения) функции. Причина их популярности – их способность усваивать представления. Нейронные сети могут изучить те представления, которые имеют значение для того, чтобы различать изображения кошек и собак, если мы предоставим им правильно размеченные данные. Это обучение с учителем.

Иногда этих меток у нас нет. Тем не менее, мы можем обучить две нейронные сети – одна будет усваивать представление, а вторая – восстанавливать исходное изображение из этого представления, минимизируя функцию потерь реконструкции. Это автоэнкодер (автокодировщик). Он так называется потому, что автоматически находит лучший способ закодировать данные так, чтобы декодированная версия была как можно ближе к исходной.

Автоэнкодер состоит из двух соединенных нейронных сетей: модели энкодера (кодировщика) и модели декодера (декодировщика). Его цель – нахождение метода кодирования лиц знаменитостей в сжатую форму (скрытое пространство) таким образом, чтобы восстановленная версия была как можно ближе к входной.

Как работают компоненты автоэнкодера
Как работают компоненты автоэнкодера
  • Модель энкодера переводит входное значение X в маленькое плотное представление Z, примерно так же, как работает сверточная нейронная сеть, используя фильтры для усвоения представлений.
  • Модель декодера можно считать генеративной моделью, способной генерировать специфические признаки X’.
  • Энкодер и декодер обычно обучаются вместе. Функция потерь штрафует объединенную сеть за создание выходных лиц, отличающихся от входных лиц.

Таким образом, энкодер обучается сохранять как можно больше полезной информации в скрытом пространстве и разумно отбрасывать неважную информацию – например, шум. Декодер обучается превращать сжатую информацию в скрытом пространстве в целое лицо знаменитости.

Автоэнкодеры также могут быть полезными для сокращения размерности и удаления шумов, и могут очень успешно проводить машинный перевод без учителя.

Что такое вариационный автоэнкодер (VAE)?

Как правило, скрытое пространство Z, создаваемое энкодером, редко заселено, то есть трудно предсказать, распределение значений в этом пространстве. Значения разбросаны, и пространство обычно хорошо визуализируется в двухмерном представлении.

Это очень полезная особенность для систем сжатия (компрессии). Однако для генерации новых изображений знаменитостей эта разреженность – проблема, поскольку найти скрытое значение, для которого декодер будет знать, как произвести нормальное изображение, почти невозможно.

Более того, если в пространстве есть промежутки между кластерами, и декодер получит вариацию из такого промежутка, ему не хватит знаний, чтобы сгенерировать что-нибудь полезное.

Вариационный автоэнкодер делает внутреннее пространство более предсказуемым, более непрерывным и менее разреженным. Заставляя скрытые переменные соответствовать нормальному распределению, VAE получают контроль над скрытым пространством.

Переход от AE к VAE, используя случайные переменные
Переход от AE к VAE, используя случайные переменные

Вместо прямой передачи скрытых значений декодеру, VAE используют их для расчета средних значений и стандартных отклонений. Затем вход декодера собирается из соответствующего нормального распределения.

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

Условные вариационные автоэнкодеры позволяют моделировать вход на основе не только скрытой переменной z, но и дополнительной информации вроде метаданных изображения (улыбка, очки, цвет кожи и т.п.)

Генератор данных изображений

Давайте создадим (условный) VAE, который сможет обучаться на лицах знаменитостей. Мы используем пользовательский эффективный по памяти генератор Keras, чтобы справиться с нашим большим набором данных (202599 изображений, примерно по 10Кб каждое). Его цель – получать пакеты изображений на лету в процессе обучения.

        import numpy as np

class CustomCelebrityFaceGenerator(Sequence):
    # инициализируем пользовательский генератор
    def __init__(self, df, batch_size, target_height, target_width, conditioning_dim=0):
        self.df = df
        self.batch_size = batch_size
        self.target_height = target_height
        self.target_width = target_width
        self.conditioning_dim = conditioning_dim
        
    # перетасуем данные после каждой эпохи 
    def on_epoch_end(self):
        self.df = self.df.sample(frac=1)
    
    # выберем пакет в виде тензора
    def __getitem__(self, index):
        cur_files = self.df.iloc[index*self.batch_size:(index+1)*self.batch_size]
        X, y = self.__data_generation(cur_files)
        return X, y
    
    # 
    def __data_generation(self, cur_files):
        # инициализируем пустые тензоры для хранения изображений  
        X = np.empty(shape=(self.batch_size, self.target_height, self.target_width, 3))
        Y = np.empty(shape=(self.batch_size, self.target_height, self.target_width, 3))
        # инициализируем пустой тензор для хранения условных переменных
        if self.conditioning_dim > 0:
            C = np.empty(shape=(self.batch_size, self.conditioning_dim))
        
        # проходим циклом по текущему пакету и создаем тензоры 
        for i in range(0, self.batch_size):
            # читаем изображение
            file = cur_files.iloc[i]
            img_uri = 'img_align_celeba/' + file.image_id
            img = skimage.io.imread(img_uri)
            # изменяем размеры изображения
            if img.shape[0] != self.target_height or img.shape[1] != self.target_width:
                img = skimage.transform.resize(img, (self.target_height, self.target_width)) 
            # сохраняем изображение в тензорах 
            img = img.astype(np.float32) / 255.
            X[i] = img
            Y[i] = img
            # сохраняем условные параметры в тензорах
            if self.conditioning_dim > 0:
                C[i] = list(file[1:file.shape[0]])
            
        if self.conditioning_dim > 0:
            return [X, C], Y
        else:
            return X, Y
    
    # получить количество пакетов
    def __len__(self):
        return int(np.floor(self.df.shape[0] / self.batch_size))
    

Нейронная сеть VAE

Мы хотим, чтобы наш энкодер был сверточной нейронной сетью, принимающей изображение и выдающей параметры распределения Q(z | [x,c]), где x – входное изображение лица, c – условная переменная (атрибуты лица), а z – скрытая переменная. В этой статье мы используем простую архитектуру, состоящую из двух сверточных слоев и слоя группировки (pooling).

Декодер – это сверточная нейронная сеть, построенная по-другому. Это генеративная нейронная сеть, выдающая параметры распределения похожести P([x,z] | c).

        from keras.layers import Conv2D, MaxPooling2D, UpSampling2D

def get_encoder_network(x, num_filters):  
    x = Conv2D(num_filters, 3, activation='relu', padding='same', kernel_initializer='he_normal')(x)
    x = Conv2D(num_filters, 3, activation='relu', padding='same', kernel_initializer='he_normal')(x)
    x = MaxPooling2D()(x)
    return x

def get_decoder_network(x, num_filters):
    x = UpSampling2D()(x)
    x = Conv2D(num_filters, 3, activation='relu', padding = 'same', kernel_initializer = 'he_normal')(x)
    x = Conv2D(num_filters, 3, activation='relu', padding = 'same', kernel_initializer = 'he_normal')(x)
    return x
    

Вот так выглядит архитектура всей сети VAE:

        from keras.layers import Input, Dense, Reshape, Concatenate, Flatten, Lambda, Reshape
from keras.models import Model
from keras import backend as K
from keras.optimizers import Adam

# функция для создания нейронной сети автоэнкодера 
def get_vae(height, width, batch_size, latent_dim, 
            is_variational=True, conditioning_dim=0,
            start_filters=8, nb_capacity=3, 
            optimizer=Adam(lr=0.001)):
    
    # ВХОД ##
    
    # создаем слой для входного изображения 
    # объединяем метаданные изображений 
    inputs = Input((height, width, 3))
    if conditioning_dim > 0:
        condition = Input([conditioning_dim])
        condition_up = Dense(height * width)(condition)
        condition_up = Reshape([height, width, 1])(condition_up)
        inputs_new = Concatenate(axis=3)([inputs, condition_up])
    else:
        inputs_new = inputs
    
    
    # ЭНКОДЕР ##
    
    # создаем кодирующие слои 
    # дублируем кодирующие слои, увеличивая фильтры 
    eblock = get_encoder_network(inputs_new, start_filters)
    for i in range(1, nb_capacity+1):
        eblock = get_encoder_network(eblock, start_filters*(2**i))
        
    # создаем слой скрытого пространства
    _, *shape_spatial = eblock.get_shape().as_list()
    eblock_flat = Flatten()(eblock)    
    if not is_variational:
        z = Dense(latent_dim)(eblock_flat)
    else:
        # выборка скрытых значений из нормального распределения
        def sampling(args):
            z_mean, z_log_sigma = args
            epsilon = K.random_normal(shape=(batch_size, latent_dim), mean=0., stddev=1.)
            return z_mean + K.exp(z_log_sigma) * epsilon
        
        z_mean = Dense(latent_dim)(eblock_flat)
        z_log_sigma = Dense(latent_dim)(eblock_flat)
        z = Lambda(sampling, output_shape=(latent_dim,))([z_mean, z_log_sigma])
    
    if conditioning_dim > 0:
        z_ext = Concatenate()([z, condition])

        
    ## ДЕКОДЕР ##
    
    # создаем декодирующие статьи
    inputs_embedding = Input([latent_dim + conditioning_dim])
    embedding = Dense(np.prod(shape_spatial), activation='relu')(inputs_embedding)
    embedding = Reshape(eblock.shape.as_list()[1:])(embedding)
    
    # дублируем кодирующие слои, увеличивая фильтры 
    dblock = get_decoder_network(embedding, start_filters*(2**nb_capacity))
    for i in range(nb_capacity-1, -1, -1):
        dblock = get_decoder_network(dblock, start_filters*(2**i))
        
    output = Conv2D(3, 1, activation = 'tanh')(dblock)
    
    ## VAE ##
    
    # объединяем энкодер с декодером 
    decoder = Model(input = inputs_embedding, output = output)
    if conditioning_dim > 0:
        encoder_with_sampling = Model(input = [inputs, condition], output = z)
        encoder_with_sampling_ext = Model(input = [inputs, condition], output = z_ext)
        vae_out = decoder(encoder_with_sampling_ext([inputs, condition]))
        vae = Model(input = [inputs, condition], output = vae_out)
    else:
        encoder_with_sampling = Model(input = inputs, output = z)
        vae_out = decoder(encoder_with_sampling(inputs))
        vae = Model(input = inputs, output = vae_out)
    
    # определяем потери VAE как сумму MSE and потерь расстояния Кульбака-Лейблера
    def vae_loss(x, x_decoded_mean):
        mse_loss = K.mean(mse(x, x_decoded_mean), axis=(1,2)) * height * width
        kl_loss = - 0.5 * K.mean(1 + z_log_sigma - K.square(z_mean) - K.exp(z_log_sigma), axis=-1)
        return mse_loss + kl_loss
        
    if is_variational:
        vae.compile(loss=vae_loss, optimizer=optimizer)
    else:
        vae.compile(loss='mse', optimizer=optimizer)    
        
    return vae, encoder_with_sampling, decoder

# гиперпараметры
VARIATIONAL = True
HEIGHT = 128 
WIDTH = 128 
BATCH_SIZE = 16 
LATENT_DIM = 16
START_FILTERS = 32 
CAPACITY = 3 
CONDITIONING = True 
OPTIMIZER = Adam(lr=0.01)

vae, encoder, decoder = get_vae(is_variational=VARIATIONAL,
                                   height=HEIGHT, 
                                   width=WIDTH, 
                                   batch_size=BATCH_SIZE, 
                                   latent_dim=LATENT_DIM,
                                   conditioning_dim=df_celeb.shape[1]-1, 
                                   start_filters=START_FILTERS,
                                   nb_capacity=CAPACITY,
                                   optimizer=OPTIMIZER)
    

Обучение

Ниже представлен процесс обучения моделей VAE на наборе данных celebA. Этот код выполнялся около 8 часов на инстансе AWS с использованием 1 GPU.

        # делим изображения на тренировочный набор и набор валидации
msk = np.random.rand(len(df_celeb)) < 0.5
df_celeb_train = df_celeb[msk]
df_celeb_val = df_celeb[~msk]

# создаем генераторы изображений для обучения
gen = CustomCelebrityFaceGenerator(df_celeb_train, 
                          batch_size=BATCH_SIZE, 
                          target_height=HEIGHT, 
                          target_width=WIDTH, 
                          conditioning_dim=df_celeb.shape[1]-1)

# создаем генераторы изображений для валидации
gen_val = CustomCelebrityFaceGenerator(df_celeb_val, 
                          batch_size=BATCH_SIZE, 
                          target_height=HEIGHT, 
                          target_width=WIDTH, 
                          conditioning_dim=df_celeb.shape[1]-1)

# обучаем вариационный автоэнкодер
vae.fit_generator(gen, verbose=1, epochs=20, validation_data=gen_val)
    

Визуализируем скрытые представления

После обучения мы можем выбрать случайное изображение из нашего набора данных и использовать обученный энкодер для создания скрытого представления изображения.

        # выбираем случайное изображение
sample_img, sample_img_meta = show_sample_image(nb=1)

# функция для кодирования одного изображения, возвращающая его скрытое представление
def encode_image(img, conditioning, encoder, height, width, batch_size):
    # изменяем размеры изображения
    if img.shape[0] != height or img.shape[1] != width:
        img = skimage.transform.resize(img, (height, width))
    # заполняем изображение, чтобы оно соответствовало размеру пакета
    img_single = np.expand_dims(img, axis=0)
    img_single = img_single.astype(np.float32)
    img_single = np.repeat(img_single, batch_size, axis=0)
    # используем энкодер для вычисления представления в скрытом пространстве
    if conditioning is None:
        z = encoder.predict(img_single)
    else:
        z = encoder.predict([img_single, np.repeat(np.expand_dims(conditioning, axis=0), batch_size, axis=0)])
    return z

# выводим представление в скрытом пространстве, созданное энкодером
z = encode_image(sample_img.astype(np.float32) / 255., 
                 np.array(sample_img_meta), 
                 encoder, HEIGHT, WIDTH, BATCH_SIZE)
print('latent sample:\n', z[0])
    


Используя это скрытое представление, вектор из 16 действительных чисел, мы можем визуализировать, как декодер восстановил исходное изображение.

        def decode_embedding(z, conditioning, decoder):
    if z.ndim < 2:
        z = np.expand_dims(z, axis=0)
    if conditioning is not None:
        z = np.concatenate((z, np.repeat(np.expand_dims(conditioning, axis=0), z.shape[0], axis=0)), axis=1)
    return decoder.predict(z)

# восстановим исходное изображение, используя представление скрытого пространства 
ret = decode_embedding(z, sample_img_meta, decoder)
plt.imshow(ret[0])
plt.show()
    

Хотя реконструированное изображение и размыто, мы можем заметить, что оно очень похоже на исходное изображение: пол, цвет одежды, волосы, улыбка, цвет кожи.

Генерируем новые лица

Условные VAE могут изменять скрытое пространство, чтобы генерировать новые данные. А это значит, что мы можем сгенерировать случайное количество новых изображений с помощью декодера, определяя разные значения заданных атрибутов.

        def generate_new_images_vae(nb=16, smiling=None, male=None, no_beard=None, attractive=None, 
                        bald=None, chubby=None, eyeglasses=None, young = None):
    sample_training_img, sample_training_img_meta = show_sample_image(nb=1, verbose=False)
    plt.clf();
    f, ax = plt.subplots(2, nb//2, figsize=(20,7));
    for i in range(nb):
        meta=2*np.random.rand(meta_cols.shape[0])-1
        meta[2] = attractive if attractive else meta[2]
        meta[4] = bald if bald else meta[4]
        meta[13] = chubby if chubby else meta[13]
        meta[15] = eyeglasses if eyeglasses else meta[15]
        meta[20] = male if male else meta[20]
        meta[24] = no_beard if no_beard else meta[24]
        meta[31] = smiling if smiling else meta[31]
        meta[39] = young if young else meta[39]
        z1 = np.random.rand(LATENT_DIM, LATENT_DIM)
        ret = decode_embedding(z1, meta, decoder)
        ax[i%2][i//2].imshow(ret[0])
        ax[i%2][i//2].set_title('generated img {}'.format(i))
    ax[0][0].imshow(sample_training_img)
    ax[0][0].set_title('training img')
    
 generate_new_images_vae()
    

Хотя наш вариационный автоэнкодер выдает размытые изображения, не похожие на реалистичные фотографии, мы можем распознать на этих изображениях пол, цвет кожи, улыбку, очки и цвет волос людей, которые никогда не существовали.

От улыбки станет мир светлей

Условные VAE могут проводить интерполяцию между атрибутами, то есть они способны заставить лицо улыбаться или добавить очки, если их не было прежде. Сейчас мы выберем лицо случайной знаменитости из нашего набора данных и воспользуемся преимуществом изменений скрытого представления, чтобы превратить женское лицо в мужское. Мы также изменим лица, добавив на них улыбку, которой прежде там не было.

        # интерполяция скрытого пространства, чтобы изменить исходное изображение
def display_manifold(decoder, height, width, base_vec, 
                     bound_x=15, bound_y=15, 
                     axis_x=0, axis_y=1, n=15,
                     desc_x = 'x', desc_y = 'y', 
                     file_out=None):
 
    figure = np.zeros((height * (n if bound_y > 0 else 1), width * (n if bound_x > 0 else 1), 3))
    grid_x = np.linspace(-bound_x, bound_x, n) if bound_x > 0 else [0]
    grid_y = np.linspace(-bound_y, bound_y, n) if bound_y > 0 else [0]
    individual_outputs = []

    for i, yi in enumerate(grid_y):
        for j, xi in enumerate(grid_x):
            z_sample = base_vec.copy()
            z_sample[axis_x] = xi 
            z_sample[axis_y] = yi 

            x_decoded = decoder.predict(np.expand_dims(z_sample, axis=0))
            sample = np.clip(x_decoded[0], 0, 1)
            figure[i * height: (i + 1) * height, j * width: (j + 1) * width] = sample
            individual_outputs.append(sample)

    plt.figure(figsize=(10, 10))
    plt.imshow(figure)
    plt.xlabel(desc_x)
    plt.ylabel(desc_y)
    if file_out is not None:
        plt.savefig(file_out, dpi=200, bbox_inches='tight')
    return figure, individual_outputs

# доступные атрибуты
meta_cols = df_celeb.columns[1:].values

# изменяемые атрибуты
dim1 = 'Male'
dim2 = 'Smiling'

# используемое скрытое пространство 
base_vec = np.array(list(z[0]) + sample_img_meta)

# создаем изменения
rendering, _ = display_manifold(
                                decoder, 
                                HEIGHT, 
                                WIDTH, 
                                base_vec, 
                                bound_x=15, 
                                bound_y=15, 
                                axis_x=LATENT_DIM + np.where(meta_cols==dim1)[0][0], 
                                axis_y=LATENT_DIM + np.where(meta_cols==dim2)[0][0], 
                                n=10,
                                desc_x = dim1,
                                desc_y = dim2,
                                file_out = 'rendering_celeba_' + dim1.lower() + '_' + dim2.lower() + '.png'
                                )
    

Заключение

В этой статье мы представили условные вариационные автоэнкодеры и продемонстрировали, как их можно обучить генерации новых размеченных данных. Мы предоставили код на Python для обучения VAE на больших наборах данных изображений знаменитостей. Этот подход и код можно использовать и для многих других задач.

Генеративные состязательные сети (GAN), как правило, выдают изображения, которые выглядят еще лучше, поскольку они обучаются распознавать, что люди считают фотореалистичным, а что нет.

Этический аспект использования технологий VAE/GAN для создания фейковых изображений, видео и новостей следует рассматривать серьезно, и они должны применяться ответственно.

Огромное спасибо Винсенту Кассеру (Vincent Casser) за его замечательный код, содержащий более продвинутый подход к реализации сверточных автоэнкодеров для обработки изображений, приведенный в его блоге. Винсент разрешил мне адаптировать его код VAE для этой статьи. Создание работающего VAE с нуля довольно сложно, так что за код следует благодарить Винсента.

Если вы хотите узнать больше об автоэнкодерах, читайте статью Джозефа Рокка «Разбираемся с вариационными автоэнкодерами (VAE)».

07
Июн
2021

Опубликован список из 10 максимально полезных GitHub-репозиториев

Он будет интересен как начинающим разработчикам, так и тем, кто готовится к интервью в крупнейших IT-компаниях.
— Читать дальше «Опубликован список из 10 максимально полезных GitHub-репозиториев»

31
Май
2021

🎥 Делаем DeepFake на коленке: пошаговое практическое руководство

Хотите собственноручно сделать видеоролик DeepFake с помощью простых инструментов? Наше пошаговое практическое руководство позволит вам пошутить над друзьями или создать забавный ролик для соцсетей, не углубляясь в программирование.

14
Апр
2021

Курс «PHP + MySQL за 1,5 месяца»

12 занятий, практика на каждом уроке, сертификат об окончании курса и возможность попасть в команду BrainForce. Старт в любой день.
— Читать дальше «Курс «PHP + MySQL за 1,5 месяца»»

30
Мар
2021

🤖 Применение искусственного интеллекта для общественного блага

Рассказываем о том, как использование технологий искусственного интеллекта в различных областях приносит пользу обществу и способствует решению глобальных социальных проблем.

Что…

29
Мар
2021

Муравей Лэнгтона — загадочный клеточный автомат

Одна из нерешённых задач математики с простейшей формулировкой и необъяснимым поведением. Попробуйте поэкспериментировать.
— Читать дальше «Муравей Лэнгтона — загадочный клеточный автомат»

19
Мар
2021

Видео: девушка-разработчик написала программу на Python для создания необычных портретов

Один из тех проектов, которые поначалу кажутся простыми, но в процессе вызывают боль и страдание.
— Читать дальше «Видео: девушка-разработчик написала программу на Python для создания необычных портретов»

12
Мар
2021

🤖📊 Как машинное обучение упорядочивает большие данные

Когда в работу с большими данными вступает машинное обучение, игра выходит на новый уровень. Рассказываем, как и зачем методы Machine Learning применяется в сфере Big Data.

Что такое большие данные?

Big Data – область, в которой рассматриваются различные способы систематического извлечения полезных для решения бизнес-задач знаний из больших объемов данных. Для этого существуют различные механические или алгоритмические процессы получения оперативной информации. Специалисты по Big Data работают с сырыми неструктурированными данными, результаты анализа которых используются для поддержки принятия решений. Аналитика включает проверку, преобразование, очистку и моделирование данных.

Анализ больших данных – относительно новая, но довольно востребованная сфера рынка труда. Спрос на специалистов в этой области постоянно растет.

Big Data – это наборы данных очень больших размеров, которые также характеризуются многообразием и высокой скоростью обновления.

Аналитик Big Data – специалист, который выявляет и исследует закономерности в данных с помощью специальных программных средств.

5V больших данных


Работа с большими данными строится вокруг пяти основных принципов (c англ. V’s of Big Data: Volume, Velocity, Variety, Veracity, Value):

  1. Объем: количество собираемой компаниями информации действительно огромно, поэтому ее объем становится критическим фактором в аналитике.
  2. Скорость: практически все происходящее вокруг нас (поисковые запросы, социальные сети и т. д.) очень быстро генерирует новые данные, многие из которых могут быть использованы в бизнес-решениях.
  3. Разнообразие: генерируемая информация неоднородна и может быть представлена в различных форматах, таких, например, как видео, текст, базы данных, числа, сенсорные данные и т. д. Понимание типов больших данных является ключевым фактором для раскрытия их ценности.
  4. Достоверность: данные высокой достоверности содержат много записей, которые ценны для анализа и которые вносят значимый вклад в общие результаты. Данные с низкой достоверностью содержат высокий процент бессмысленной информации, которая называется шумом.
  5. Ценность: возможность трансформировать большие данные в бизнес-решения.

Откуда получают большие данные


Информация собирается из самых разных источников. Рядовые пользователи осуществляют в онлайне множество действий, от деловых коммуникаций до покупок и общения в социальных сетях. Миллиарды подключенных устройств и встроенных систем по всему миру также ежедневно создают, собирают и совместно используют данные Интернета вещей.

Некоторые из основных источников Big Data:

  • Социальные сети;
  • Облачные Хранилища;
  • Веб-страницы;
  • Интернет вещей.

Интеллектуальный анализ и аналитика – два ключевых метода работы с большими данными. Интеллектуальный анализ включает сбор информации и применение к ней логических рассуждений. Сортировка и аналитика данных позволяют выявить скрытые закономерности и идеи, которые могут стать источником инсайтов для принятия решений практически в каждой отрасли. Например, с помощью идентификации паттернов и прогнозной аналитики.

Что такое машинное обучение?


Машинное обучение исследует построение и оптимизацию алгоритмов, задача которых – прогнозирование непредвиденных/будущих данных. В сочетании с возможностями облачных вычислений оно обеспечивает гибкость обработки и интеграции больших объемов данных вне зависимости от источника.

Алгоритмы машинного обучения могут быть применены к каждому этапу работы с большими данными, включая следующие:

  • Сегментацию данных;
  • Анализ данных;
  • Моделирование.

Пройдя эти этапы, можно получить общую картину с инсайтами и паттернами, которые позже классифицируются и упаковываются в понятный формат. Слияние машинного обучения и больших данных – бесконечный цикл. Созданные алгоритмы отслеживаются и совершенствуются в течение времени по мере поступления информации в систему. Подробнее о том, как с помощью теории вероятностей и статистики, математического анализа и линейной алгебры создаются и развиваются новые алгоритмы машинного обучения мы уже писали.

Как машинное обучение применяется в Big Data?

В контексте больших данных машинное обучение используется, чтобы идти в ногу с постоянно растущим и меняющимся потоком информации. Алгоритмы машинного обучения определяют поступающие данные и выявляют связанные с ними закономерности, которые впоследствии преобразуются в ценные идеи и могут быть внедрены в бизнес-операции для автоматизации некоторых аспектов процесса принятия решений.

Примеры применения алгоритмов МО для больших данных

Автоматизация Маркетинга

Автоматизировать работу с клиентами, сделать ее более гибкой, устранить болевые точки и создать бесшовную связь между всеми каналами, будь то обмен сообщениями или брендинг – основная ценность применения машинного обучения в маркетинге.

Целевая аудитория – это краеугольный камень любого бизнеса. Каждое предприятие должно понимать рынок, на который оно хочет ориентироваться. Машинное обучение использует контролируемые и неконтролируемые алгоритмы для точной интерпретации потребительских паттернов и поведения. Опираясь на машинное обучение и большие данные, автоматизация маркетинга может использовать анализ тональности текста, сегментацию клиентов и прямой маркетинг, с помощью персонализированных сообщений для удовлетворения потребностей клиентов. СМИ и индустрия развлечений используют машинное обучение, чтобы понять симпатии и антипатии аудитории и предложить ей подходящий контент.

Анализ тональности текста


Анализ тональности текста – мощный инструмент для запуска нового продукта или внедрения новых функций. Тренированные на больших данных модели машинного обучения позволяют с высокой точностью предсказать реакцию клиентов: полюбят ли они продукт или полностью проигнорируют его. Предсказание результатов возможно в самом начале разработки продукта! Это позволяет изменить дизайн или маркетинговую стратегию в соответствии с потребностями рынка.

Рекомендательные системы

Составление обоснованных рекомендаций по продукту сопоставимо с искусством: оно требует тонкости и надежной комбинации методов машинного обучения с большими данными.

Машинное обучение на больших данных лучше всего использовать в рекомендательных механизмах: для воздействия на пользовательский опыт оно сочетает контекст с прогнозами поведения, давая компаниям возможность формировать эффективные предложения для клиентов

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

Регулирование рисков

Благодаря быстрому развитию сбора данных и вычислительной мощности, машинное обучение становится неотъемлемой частью принятия бизнес-решений. Его применение в управлении рисками, заложило основы для нового поколения более совершенных моделей прогнозирования.

Регулирование рисков – одна из самых востребованных областей применения машинного обучения и больших данных. К примеру, их использование для автоматизации банковского скоринга и цифровизации ключевых этапов создания стоимости кредита могут значительно снизить затраты финансовой организации. Наиболее полезными методами машинного обучения в этой области являются регрессии, деревья решений и нейронные сети.

Расшифровка паттернов

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

Прогнозная аналитика


Алгоритмы машинного обучения используют большие данные для изучения будущих тенденций и их прогнозирования для бизнеса. Прогнозная аналитика широко используется в автомобильной промышленности: она позволяет производителям отслеживать поломки и обмениваться важной информацией о неисправностях автомобилей.

***

Мы рассмотрели возможности и сферы применения машинного обучения в больших данных. Если вы еще не определились со специализацией, начните с базового онлайн-курса «Библиотеки программиста» по математике в Data Science. Без царицы наук в этой области обойтись не получится, а с помощью опытных преподавателей из ведущих вузов страны получить знания намного проще, чем самостоятельно по книгам. Также ведется запись и на продвинутый курс. Удачи в освоении востребованной профессии!

02
Мар
2021

🤖 Современные рекомендательные системы

Сегодня мы поглубже нырнем в особенности работы алгоритмов искусственного интеллекта, на которых построили бизнес Facebook, Google и другие ИТ-гиганты.

Не далее чем в мае 2019 Facebook выложил в открытый доступ исходный код некоторых своих подходов к рекомендациям и представил DLRM (Deep-Learning Recommendation Model – рекомендательную модель глубокого обучения). Эта статья попробует объяснить, как и почему DLRM и другие современные подходы к рекомендациям работают настолько хорошо, посредством анализа их происхождения от прежних результатов в данной области и детального объяснения внутренних деталей их работы и заложенных в них идей.


Персонализированная реклама, основанная на ИИ, сегодня царствует в онлайн-маркетинге, и такие компании, как Facebook, Google, Amazon, Netflix и прочие – короли джунглей этого онлайн-маркетинга, поскольку они не просто усвоили этот тренд, а фактически сами воплотили его в жизнь и построили на нем всю свою бизнес-стратегию. Netflix’овские “другие фильмы, которые могут вам понравиться” и Amazon’овские “люди, купившие это, купили также…” – всего лишь несколько примеров из реального мира.

Само собой, будучи постоянным пользователем Facebook и Google, в какой-то момент я спросил себя:

КАК ИМЕННО ЭТА ШТУКА РАБОТАЕТ?

И, разумеется, мы все уже видели базовый пример рекомендации фильмов, объясняющий, как работают коллаборативная фильтрация и факторизация матриц. Я также не говорю о подходе обучения простого классификатора для каждого пользователя, который будет выдавать вероятность того, что этому пользователю понравится тот или иной продукт. Эти два подхода, называемые коллаборативной фильтрацией и рекомендацией, основанной на контексте, наверняка более-менее эффективны и выдают предсказания, которые можно использовать, но у Google, Facebook и прочих наверняка должно быть что-нибудь получше, какой-нибудь “туз в рукаве”, иначе они бы не были там, где они находятся сейчас.

Чтобы понять, откуда происходят современные передовые рекомендательные системы, нам придется взглянуть на два основных подхода к задаче

предсказания, насколько данному пользователю понравится данный продукт,

которая в мире онлайнового маркетинга складывается в предсказание показателя кликабельности (click-through rate, CTR) для возможных рекламных объявлений, основанное как на явной обратной связи (рейтинги, лайки и т.п.), так и на неявной (клики, истории поиска, комментарии или посещения веб-сайтов).

Коллаборативная фильтрация против фильтрации на основе содержимого

1. Фильтрация на основе содержимого (content-based filtering)

Грубо говоря, рекомендация на основе содержимого пытается предсказать, понравится ли пользователю некоторый продукт, используя его онлайновую историю. Это включает, помимо всего прочего, поставленные пользователем лайки (например, на Facebook), ключевые слова, которые он искал (например, в Google), а также простые клики и посещения определенных веб-сайтов. В конечном счете она концентрируется на собственных предпочтениях каждого пользователя. Мы можем, например, построить простой бинарный классификатор (или регрессор), предсказывающий ожидаемый уровень кликабельности (или рейтинг) определенной группы рекламных объявлений для данного пользователя.

2. Коллаборативная фильтрация

Коллаборативная фильтрация пытается предсказать, может ли пользователю понравиться определенный продукт, путем анализа предпочтений похожих пользователей. Здесь мы можем подумать об уже привычном для нас (по примеру рекомендации фильмов) подходе факторизации матриц (matrix factorization – MF), при котором матрица рейтингов приводится к одной матрице, описывающей пользователей и другой, описывающей фильмы.

Недостаток классической MF в том, что мы не можем использовать никакие признаки, кроме пользовательских оценок – например, жанр фильма, год выхода и т.д. – MF приходится догадываться обо всем этом из имеющихся оценок. Кроме того, MF страдает от так называемой “проблемы холодного старта”: новый фильм, который еще никто не оценил, не может быть рекомендован. Фильтрация на основе содержимого справляется с этими двумя проблемами, но ей не хватает предсказательной мощности просмотра предпочтений других пользователей.

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

1. Машина Факторизации (Factorization Machine)

Одна из идей гибридной модели, предложенная Стеффеном Рендлом в 2010-м – это Машина Факторизации. Она придерживается базового математического подхода, комбинируя факторизацию матриц с регрессией:

y^(x):=w0+∑i=0nwixi⏟regressionpart+∑i=1n∑j=i+1n⟨vi,vj⟩xixj⏟MFpartw0∈R;w∈Rn;V∈Rn∗k;vi,vj∈Rk

Здесь <vi, vj> – произведение векторов, которые можно рассматривать как строки матрицы V.

Понять смысл этого уравнения довольно просто, если посмотреть на пример представления данных x, попадающих в эту модель. Давайте рассмотрим пример, представленный Стеффеном в его статье о Машине Факторизации.

Предположим, у нас есть следующие данные об обзорах фильмов, где пользователи ставят фильмам оценки в определенное время:

  • пользователь u из множества U = {Alice (A), Bob (B),…}
  • фильм i из множества I = {“Титаник” (TN), “Ноттинг Хилл” (NH), “Звездные Войны” (SW), “Стар Трек” (ST),…}
  • оценка r из {1, 2, 3, 4, 5}, поставленная во время t.
Рис.1. С. Рендл, "Машины факторизации", Международная конференция IEEE по Data Mining, 2010.
Рис.1. С. Рендл, “Машины факторизации”, Международная конференция IEEE по Data Mining, 2010.

Посмотрев на приведенный выше рисунок, мы увидим представление данных в гибридной рекомендательной модели. Как разреженные признаки, представляющие пользователя и оцениваемый объект, так и любая другая дополнительная информация об объекте или мета-информация (в этом примере – Time и Last Movie Rated) попадают в вектор признаков x, который соответствует значению целевой переменной y. Теперь главное – то, как они обрабатываются моделью.

  • Регрессионая часть FM обрабатывает и разреженные, и плотные данные (например, Time), как обычная задача линейной регрессии, и, таким образом, может считаться подходом фильтрации на основе содержимого в составе FM.
  • Часть MF отвечает за взаимодействие между блоками признаков (например, взаимодействие между “Пользователем” и “Фильмом”), где матрицу V можно рассматривать как встроенную матрицу, используемую в подходах коллаборативной фильтрации. Эти отношения пользователь-фильм предоставляют нам догадки вроде:

Пользователю i, которому соответствует вектор vi (представляющий его предпочтения к параметрам фильмов), похожий на вектор vj пользователя j, скорее всего, понравятся те же фильмы, что и пользователю j.

Сложение вместе предсказаний регрессионной части и части MF и одновременное обучение их параметров в одной функции потерь приводит к гибридной модели FM, которая теперь использует подход “лучшее из обоих миров” для выдачи рекомендации пользователю.

Однако, несмотря на то, что подход Машины Факторизации с первого взгляда кажется “лучшей моделью из обоих миров”, многие области ИИ, такие, как обработка естественного языка или машинное зрение, давно доказали, что

если взять нейронную сеть, то будет еще лучше!

2. Широкие и глубокие: нейронная коллаборативная фильтрация (NCF) и Глубокие Машины Факторизации (DeepFM)

Для начала бросим взгляд на то, как можно реализовать коллаборативную фильтрацию с помощью нейронных сетей, просмотрев статью об NCF. В конце концов это приведет нас к Глубоким Машинам Факторизации (DeepFM), представляющим собой нейросетевую версию машин факторизации. Мы увидим, почему они превосходят обычные машины факторизации, и как можно интерпретировать архитектуру этих нейронных сетей. Мы увидим, что DeepFM была разработана как улучшение вышедшей до этого модели Wide&Deep от Google, которая была одним из первых крупных прорывов в области глубокого обучения рекомендательных систем. В конце концов это приведет нас к упомянутой выше статье по DLRM, опубликованной Facebook’ом в 2019-м, которую можно считать упрощением и небольшим усовершенствованием DeepFM.

NCF

В 2017-м группа исследователей опубликовала свою работу о Нейронной Коллаборативной Фильтрации (NCF). Она содержит обобщенный фреймворк для изучения нейронных зависимостей, моделируемых факторизацией матриц при коллаборативной фильтрации с помощью нейронной сети. Авторы также объяснили, как получить зависимости высшего порядка (MF имеет порядок всего лишь 2), и как объединить оба эти подхода.

Общая идея заключается в том, что нейронная сеть может (теоретически) усвоить любую функциональную зависимость. Это значит, что зависимость, которую модель коллаборативной фильтрации выражает матричной факторизацией, может быть усвоена нейронной сетью. NCF предлагает простой слой представления сразу для пользователей и объектов (похожий на классическую факторизацию матриц), за которым следует простая нейронная сеть вроде многослойного перцептрона, которая должна усвоить зависимость между представлениями пользователя и объекта, аналогичную произведению факторизованных матриц.

Рис. 2. Из статьи "Нейронная коллаборативная фильтрация" Кс. Хе, Л. Ляо, Х. Жанг, Л. Ни, Кс. Ху, Ц. Чуа – Материалы 26-й международной конференции по World-Wide Web, 2017.
Рис. 2. Из статьи “Нейронная коллаборативная фильтрация” Кс. Хе, Л. Ляо, Х. Жанг, Л. Ни, Кс. Ху, Ц. Чуа – Материалы 26-й международной конференции по World-Wide Web, 2017.

Преимущество этого подхода заключается в нелинейности многослойного перцептрона. Простое произведение матриц, используемое при матричной факторизации, всегда будет ограничивать модель взаимодействиями 2-й степени, тогда как нейронная сеть с X слоями в теории может усвоить взаимодействия гораздо более высоких степеней. Представьте себе, например, три качественные переменные, все имеющие взаимодействия друг с другом – например, мужской пол, подростковый возраст и ролевые компьютерные игры.

В реальных задачах мы не просто используем двоичные векторы, соответствующие пользователю и объекту в качестве необработанных данных для их представления, но, очевидно, включаем и прочую дополнительную или мета-информацию, которая может представлять ценность (например, возраст, страну, аудио- и текстовые записи, метки времени,…), так что в реальности у нас получается набор данных очень высокой размерности, сильно разреженный и содержащий смесь качественных переменных с количественными. К этому моменту представленную на рис. 2 нейронную сеть можно считать и рекомендацией на основе содержимого в виде простого нейронного бинарного классификатора прямого прохода. И эта интерпретация – ключевая для понимания того, почему этот подход в конце концов оказывается гибридным между коллаборативной фильтрацией и рекомендациями на основе содержимого. Эта нейронная сеть может усвоить любые функциональные зависимости – например, взаимодействия 3-й степени и выше, вроде x1 * x2 * x3, или любые нелинейные трансформации в классическом понимании, используемом в нейронных классификаторах – в виде sigma(.. sigma(w1x1+w2x2+w3x3+b)).

Вооружившись мощью изучения зависимостей высшего порядка, мы можем использовать простой способ изучения зависимостей 1-го и 2-го порядков, скомбинировав нейронную сеть с широко известной моделью для их изучения, Машиной Факторизации. Именно это авторы DeepFM предложили в своей статье. Идея этой комбинации – параллельно изучать зависимости между признаками низких и высоких порядков – ключевая часть многих современных рекомендательных систем, и в том или ином виде ее можно найти почти в каждой архитектуре нейронной сети, предлагаемой в этой области.

DeepFM

DeepFM – это смешанный подход, включающий факторизацию матриц и глубокую нейронную сеть, причем оба используют один и тот же входной слой представления (embedding). Необработанные признаки трансформируются, чтобы закодировать категориальные признаки унитарным кодом (one-hot encoding). Итоговое предсказание (показатель кликабельности), выдаваемое последним словом нейронной сети, определяется так:

y^=sigmoid(yFM+yDNN)

То есть, это сумма предсказаний матричной факторизации и нейронной сети, пропущенная через сигмоидную функцию активации.

Компонент факторизации матриц – это обычная Машина Факторизации, оформленная в стиле архитектуры нейронной сети:

Рис. 3. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 3. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Часть сложения (Addition) этого слоя матричной факторизации получает вектор входных данных x от слоя разреженных признаков (Sparse Features) и умножает каждый элемент на его вес (Normal Connection) перед суммированием. Часть перемножения векторов (Inner Product) также получает вектор x, но только после его прохождения через слой представления и просто перемножает представленные векторы без весов (“Weight-1 Connection”). Сложение обеих частей вместе приводит к вышеупомянутому уравнению для Машины Факторизации:

yFM:=w0+∑i=0nwixi+∑i=1n∑j=i+1n⟨vi,vj⟩xixj

В этом уравнении перемножение xixj нужно только для записи суммы от 1 до n. Оно не является частью вычислений нейронной сети. Нейронная сеть автоматически знает, произведение каких векторов vi и vj потребуется, благодаря архитектуре слоя представления.

Архитектура слоя представления выглядит следующим образом:

Рис. 4. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 4. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Здесь Vp – матрица представлений для каждого поля p={1,2…,m} c k столбцами и количеством строк, соответствующим количеству элементов поля, закодированных двоичным образом. Выход этого слоя представления определяется как

a(0)=[e1,e2,…em]

и важно отметить, что этот слой не полносвязный, а именно – нет связей между необработанным входом любого поля и представлением любого другого поля. Представьте это следующим образом: вектор значений для пола (например, (0, 1)), закодированный унитарным кодом, не может иметь ничего общего с вектором представлений для дня недели (например, вектором (0, 1, 0, 0, 0, 0, 0), закодированный “Вторник”, или его вектором представления, например, для k=4, (12, 4, 5, 9).

Компонент FM – это Машина Факторизации, отражающая высокую важность взаимодействий 1 и 2 порядка, которые прямо складываются с выходом глубокого компонента и передаются в сигмоидную функцию активации последнего слоя.

Глубоким компонентом, как предполагается, теоретически может быть нейронная сеть любой архитектуры. Авторы рассмотрели стандартный многоуровневый перцептрон прямого прохода (а также так называемую PNN). Стандартный многоуровневый перцептрон изображен на следующем рисунке:

Рис. 5. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 5. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Нейронная сеть на основе стандартного многослойного перцептрона со слоем представления между необработанными данными (сильно разреженными после унитарного кодирования категориальных переменных) и следующими слоями нейронной сети описывается следующей формулой:

a(l+1)=σ(W(l)a(l)+b(l))

где sigma – функция активации, W – матрица весов, a – результат функции активации предыдущего слоя, а b – порог.

Это приводит к общей архитектуре нейронной сети DeepFM:

Рис. 6. Общая архитектура DeepFM
Рис. 6. Общая архитектура DeepFM

со следующими параметрами:

  • Скрытый вектор Vi для измерения влияния взаимодействий признака i с другими признаками (слой представления).
  • Vi передается в компонент FM для моделирования взаимодействий 2 порядка (компонент FM).
  • wi взвешивает важность необработанного признака i 1-го порядка (компонент FM).
  • Vi также передается в Глубокий компонент для моделирования всех взаимодействий высших порядков (>2)(Глубокий компонент).
  • WI и bI – веса и пороги нейронной сети (Глубокий компонент).

Ключ к одновременному получению взаимодействий высших и низших порядков – это одновременное обучение всех параметров под одной функцией потерь, используя один и тот же слой представления как для компонента FM, так и для Глубокого компонента.

Сравнение с Wide&Deep и NeuMF

Есть много вариаций, о которых можно задуматься, чтобы “отполировать” эту архитектуру и сделать ее еще лучше. Однако в основном все они сходятся в своем гибридном подходе, заключающемся в одновременной обработке взаимодействий высших и низших порядков. Авторы DeepFM также предложили замену многоуровневого перцептрона на так называемую PNN, глубокую нейронную сеть, получающую в качестве входных данных выводы FM и слоя представления.

Авторы статьи про NCF также предложили похожую архитектуру, которую они назвали NeuMF (Neural Matrix Factorization – нейронная факторизация матриц). Вместо использования FM в качестве компонента низшего порядка они используют обычную факторизацию матриц, результаты которой передаются в функцию активации. Этому подходу, однако, не хватает взаимодействий 1 порядка, моделируемых линейной частью FM. Авторы также указали, что модель имеет различные представления пользователя и объекта для матричной факторизации и многослойного перцептрона.

Как упомянуто выше, команда исследователей Google была одной из первых, предложивших нейронные сети для гибридного подхода к рекомендации. DeepFM можно рассматривать как дальнейшеее развитие алгоритма Wide&Deep от Google, который выглядит примерно так:

Рис. 7. Х-Т Ченг, Л. Кос, Дж. Хармсен, Т. Шакед, Т. Чандра, Х. Арадхье, Г. Андерсон, Г. Коррадо, В. Чаи, М. Испир, Р. Анил, З. Хак, Л. Хонг, В. Джейн, Кс. Лю и Х. Шах. "Широкое и глубокое обучение для рекомендательных систем" – Материалы 1 семинара по глубокому обучению для рекомендательных систем, стр. 7-10, 2016.
Рис. 7. Х-Т Ченг, Л. Кос, Дж. Хармсен, Т. Шакед, Т. Чандра, Х. Арадхье, Г. Андерсон, Г. Коррадо, В. Чаи, М. Испир, Р. Анил, З. Хак, Л. Хонг, В. Джейн, Кс. Лю и Х. Шах. “Широкое и глубокое обучение для рекомендательных систем” – Материалы 1 семинара по глубокому обучению для рекомендательных систем, стр. 7-10, 2016.

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

ϕk(x)=∏i=1dxickicki∈{0,1}

Это выражает взаимодействие между d признаками (с предшествующим представлением признаков или без него), умножая их друг на друга (показатель степени равен 1, если xi является частью k-й трансформации).

Легко видеть, что DeepFM является развитием этой модели, поскольку она не требует никакого предварительного конструирования признаков и может обучиться взаимодействиям низкого и высокого порядка на основе одних и тех же входных данных, разделяющих один и тот же слой представления. DeepFM действительно содержит Машину Факторизации как часть основной сети, тогда как Wide&Deep не выполняет произведение векторов в какой-либо части сети, а делает это предварительно на шаге конструирования признаков.

3. DLRM – рекомендационная модель глубокого обучения

Ну что ж, рассмотрев различные варианты от Google, Huawei (команда исследователей, стоящая за архитектурой DeepFM) и прочих, давайте познакомимся с видением исследователей Facebook. Они опубликовали свою статью о DLRM в 2019-м, и она в основном фокусируется на практической реализации этих моделей. Решения с параллельным обучением, переложение расчетов на GPU, а также различная обработка постоянных и категориальных признаков.

Архитектура DLRM описана на следующем рисунке и работает следующим образом: каждый категориальный признак представлен вектором представления, а постоянные признаки обрабатываются многослойным перцептроном таким образом, чтобы на выходе получались векторы такого же размера, как и векторы представления. На второй стадии рассчитываются взаимные произведения всех векторов представления и выходных векторов перцептрона. После этого произведения соединяются вместе и передаются в другой многослойный перцептрон, а в конце концов – в функцию сигмоиды, выдающую вероятность.

Нейронная сеть DLRM, как описано в <a href="http://arxiv.org/abs/1906" target="_blank" rel="noopener noreferrer nofollow">статье про DLRM</a>. Рисунок Макса Беккерса
Нейронная сеть DLRM, как описано в статье про DLRM. Рисунок Макса Беккерса

Предложение DLRM – это нечто вроде упрощенной и модифицированной версии DeepFM в том смысле, что оно также использует произведение векторов, но намеренно пытается держаться подальше от взаимодействий высших порядков, не обязательно прогоняя представленные категориальные признаки через многослойный перцептрон. Такой дизайн предназначен для копирования подхода, используемого в Машине Факторизации, когда она рассчитывает взаимодействия второго порядка между представлениями. Мы можем рассматривать всю DLRM как отдельную часть DeepFM, компонент FM. Можно считать, что классический Глубокий компонент DeepFM, вывод которого складывается с выводом компонента FM в финальном слое DeepFM (а потом передается в функцию сигмоиды) в DLRM полностью отсутствует. Теоретические преимущества DeepFM очевидны, поскольку ее дизайн намного лучше приспособлен для изучения взаимодействий высших порядков, однако, по мнению специалистов Facebook:

“взаимодействия выше второго порядка, используемые в других сетях, не обязательно стоят дополнительных затрат вычислительной мощности и памяти”.

4. Обзор и кодирование

Представив различные подходы к глубокой рекомендации, их теоретические основы, преимущества и недостатки, я был просто вынужден взглянуть на предлагаемую реализацию DLRM на PyTorch на GitHub-странице Facebook.

Я изучил детали реализации и протестировал предлагаемые специальные API наборов данных, которые авторы создали для прямой обработки различных наборов данных. Как соревнование по рекламе дисплеев на Kaggle от Criteo, так и их набор данных Terabyte имеют готовые реализации API, их можно загрузить и впоследствии использовать для обучения полной DLRM всего одной командой bash (инструкции см. в репозитории DLRM). Затем я расширил API модели DLRM от Facebook, добавив шаги загрузки и предварительной обработки для другого набора данных, “Предсказание показателя кликабельности для рекламы DIGIX в 2020”. Результат можно найти здесь.

Примерно так же, как и для приведенных авторами примеров, после загрузки и распаковки данных DIGIX, вы также сможете обучить модель на этом наборе данных одной командой bash. Все шаги предварительной обработки, размеры представлений и параметры архитектуры нейронной сети были настроены на обработку набора данных DIGIX. Блокнот, который проведет вас по этим шагам, можно найти здесь. Эта модель выдает приличные результаты, и я продолжаю над ней работать с целью улучшения производительности посредством лучшего понимания необработанных данных и процесса работы с рекламными объявлениями, используемого в DIGIX. Специализированная очистка данных, настройка гиперпараметров и конструирование признаков – все это вещи, над которыми я хотел бы еще поработать, и они упомянуты в блокноте. Моей первой целью было технически рациональное расширение API модели DLRM, способное использовать необработанные данные DIGIX в качестве входных данных.

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

Ссылки

Стеффен Рендл, “Машины факторизации”, Международная конференция IEEE по Data Mining, стр. 995-1000, 2010.

Ксианьян Хе, Лизи Ляо, Ханванг Жанг, Ликианг Ли, Ксиа Ху и Тат-Сенг Чуа. “Нейронная коллаборативная фильтрация”, Материалы 26-й международной конференции по World-Wide Web, стр. 173-182, 2017.

Хуифенг Гуо, Руиминг Тэнг, Юнминь Е, Женгуо Ли и Ксиукианг Хе. “DeepFM: нейронная сеть для предсказания показателя кликабельности, основанная на машине факторизации”, препринт arXiv:1703.04247, 2017.

Джианксун Лиан, Ксиаохуан Жоу, Фуженг Жанг, Жонгксиа Чен, Ксинг Кси и Гуангжонг Сун. “xDeepFM: комбинируем явные и неявные взаимодействия признаков для рекомендательных систем”, в Материалах 24-й международной конференции ACM SIGKDD по исследованию знаний и Data Mining, стр. 1754–1763. ACM, 2018.

Хенг-Це Ченг, Левент Коц, Джеремия Хармсен, Тал Шакед, Тушар Чандра, Хриши Арадхье, Глен Андерсон, Грег Коррадо, Вей Чай, Мустафа Испир, Рохан Анил, Закария Хак, Личан Хонг, Вихан Джайн, Ксяобинг Лю и Хемаль Шах. “Широкое и глубокое обучение для рекомендательных систем”, в материалах 1-го семинара по глубокому обучению рекомендательных систем”, стр. 7-10, 2016.

М. Наумов, Д. Мудигер, Х.М. Ши, Дж. Хуанг, Н. Сундараман, Дж. Парк, Кс. Ванг, У. Гупта, Ц. Ву, А.Г. Аццолини, Д. Джулгаков, А. Малевич, И. Чернавский, Ю. Лю, Р. Кришнамурти, А. Ю, В. Кондратенко, С. Перейра, Кс. Чен, В. Чен, В. Рао, Б. Джиа, Л. Ксионг и М. Смелянский “Рекомендационная модель глубокого обучения для систем персонализации и рекомендации”, CoRR, vol. abs/1906.00091, 2019. [Онлайн]. Доступна здесь.

02
Мар
2021

🤖 Как устроены современные рекомендательные системы?

Сегодня мы глубоко погрузимся в особенности работы алгоритмов искусственного интеллекта, на которых построили бизнес Facebook, Google и другие ИТ-гиганты. Внимание: статья рассчитана на специалистов.

Современные рекомендательные системы

Не далее чем в мае 2019 Facebook выложил в открытый доступ исходный код некоторых своих подходов к рекомендациям и представил DLRM (Deep-Learning Recommendation Model – рекомендательную модель глубокого обучения). Эта статья попробует объяснить, как и почему DLRM и другие современные подходы к рекомендациям работают настолько хорошо, посредством анализа их происхождения от прежних результатов в данной области и детального объяснения внутренних деталей их работы и заложенных в них идей.


Персонализированная реклама, основанная на ИИ, сегодня царствует в онлайн-маркетинге, и такие компании, как Facebook, Google, Amazon, Netflix и прочие – короли джунглей этого онлайн-маркетинга, поскольку они не просто усвоили этот тренд, а фактически сами воплотили его в жизнь и построили на нем всю свою бизнес-стратегию. Netflix’овские “другие фильмы, которые могут вам понравиться” и Amazon’овские “люди, купившие это, купили также…” – всего лишь несколько примеров из реального мира.

Само собой, будучи постоянным пользователем Facebook и Google, в какой-то момент я спросил себя:

КАК ИМЕННО ЭТА ШТУКА РАБОТАЕТ?

И, разумеется, мы все уже видели базовый пример рекомендации фильмов, объясняющий, как работают коллаборативная фильтрация и факторизация матриц. Я также не говорю о подходе обучения простого классификатора для каждого пользователя, который будет выдавать вероятность того, что этому пользователю понравится тот или иной продукт. Эти два подхода, называемые коллаборативной фильтрацией и рекомендацией, основанной на контексте, наверняка более-менее эффективны и выдают предсказания, которые можно использовать, но у Google, Facebook и прочих наверняка должно быть что-нибудь получше, какой-нибудь “туз в рукаве”, иначе они бы не были там, где они находятся сейчас.

Чтобы понять, откуда происходят современные передовые рекомендательные системы, нам придется взглянуть на два основных подхода к задаче

предсказания, насколько данному пользователю понравится данный продукт,

которая в мире онлайнового маркетинга складывается в предсказание показателя кликабельности (click-through rate, CTR) для возможных рекламных объявлений, основанное как на явной обратной связи (рейтинги, лайки и т.п.), так и на неявной (клики, истории поиска, комментарии или посещения веб-сайтов).

Коллаборативная фильтрация против фильтрации на основе содержимого

1. Фильтрация на основе содержимого (content-based filtering)

Грубо говоря, рекомендация на основе содержимого пытается предсказать, понравится ли пользователю некоторый продукт, используя его онлайновую историю. Это включает, помимо всего прочего, поставленные пользователем лайки (например, на Facebook), ключевые слова, которые он искал (например, в Google), а также простые клики и посещения определенных веб-сайтов. В конечном счете она концентрируется на собственных предпочтениях каждого пользователя. Мы можем, например, построить простой бинарный классификатор (или регрессор), предсказывающий ожидаемый уровень кликабельности (или рейтинг) определенной группы рекламных объявлений для данного пользователя.

2. Коллаборативная фильтрация

Коллаборативная фильтрация пытается предсказать, может ли пользователю понравиться определенный продукт, путем анализа предпочтений похожих пользователей. Здесь мы можем подумать об уже привычном для нас (по примеру рекомендации фильмов) подходе факторизации матриц (matrix factorization – MF), при котором матрица рейтингов приводится к одной матрице, описывающей пользователей и другой, описывающей фильмы.

Недостаток классической MF в том, что мы не можем использовать никакие признаки, кроме пользовательских оценок – например, жанр фильма, год выхода и т.д. – MF приходится догадываться обо всем этом из имеющихся оценок. Кроме того, MF страдает от так называемой “проблемы холодного старта”: новый фильм, который еще никто не оценил, не может быть рекомендован. Фильтрация на основе содержимого справляется с этими двумя проблемами, но ей не хватает предсказательной мощности просмотра предпочтений других пользователей.

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

1. Машина Факторизации (Factorization Machine)

Одна из идей гибридной модели, предложенная Стеффеном Рендлом в 2010-м – это Машина Факторизации. Она придерживается базового математического подхода, комбинируя факторизацию матриц с регрессией:

y^(x):=w0+∑i=0nwixi⏟regressionpart+∑i=1n∑j=i+1n⟨vi,vj⟩xixj⏟MFpartw0∈R;w∈Rn;V∈Rn∗k;vi,vj∈Rk

Здесь <vi, vj> – произведение векторов, которые можно рассматривать как строки матрицы V.

Понять смысл этого уравнения довольно просто, если посмотреть на пример представления данных x, попадающих в эту модель. Давайте рассмотрим пример, представленный Стеффеном в его статье о Машине Факторизации.

Предположим, у нас есть следующие данные об обзорах фильмов, где пользователи ставят фильмам оценки в определенное время:

  • пользователь u из множества U = {Alice (A), Bob (B),…}
  • фильм i из множества I = {“Титаник” (TN), “Ноттинг Хилл” (NH), “Звездные Войны” (SW), “Стар Трек” (ST),…}
  • оценка r из {1, 2, 3, 4, 5}, поставленная во время t.
Рис.1. С. Рендл, "Машины факторизации", Международная конференция IEEE по Data Mining, 2010.
Рис.1. С. Рендл, “Машины факторизации”, Международная конференция IEEE по Data Mining, 2010.

Посмотрев на приведенный выше рисунок, мы увидим представление данных в гибридной рекомендательной модели. Как разреженные признаки, представляющие пользователя и оцениваемый объект, так и любая другая дополнительная информация об объекте или мета-информация (в этом примере – Time и Last Movie Rated) попадают в вектор признаков x, который соответствует значению целевой переменной y. Теперь главное – то, как они обрабатываются моделью.

  • Регрессионая часть FM обрабатывает и разреженные, и плотные данные (например, Time), как обычная задача линейной регрессии, и, таким образом, может считаться подходом фильтрации на основе содержимого в составе FM.
  • Часть MF отвечает за взаимодействие между блоками признаков (например, взаимодействие между “Пользователем” и “Фильмом”), где матрицу V можно рассматривать как встроенную матрицу, используемую в подходах коллаборативной фильтрации. Эти отношения пользователь-фильм предоставляют нам догадки вроде:

Пользователю i, которому соответствует вектор vi (представляющий его предпочтения к параметрам фильмов), похожий на вектор vj пользователя j, скорее всего, понравятся те же фильмы, что и пользователю j.

Сложение вместе предсказаний регрессионной части и части MF и одновременное обучение их параметров в одной функции потерь приводит к гибридной модели FM, которая теперь использует подход “лучшее из обоих миров” для выдачи рекомендации пользователю.

Однако, несмотря на то, что подход Машины Факторизации с первого взгляда кажется “лучшей моделью из обоих миров”, многие области ИИ, такие, как обработка естественного языка или машинное зрение, давно доказали, что

если взять нейронную сеть, то будет еще лучше!

2. Широкие и глубокие: нейронная коллаборативная фильтрация (NCF) и Глубокие Машины Факторизации (DeepFM)

Для начала бросим взгляд на то, как можно реализовать коллаборативную фильтрацию с помощью нейронных сетей, просмотрев статью об NCF. В конце концов это приведет нас к Глубоким Машинам Факторизации (DeepFM), представляющим собой нейросетевую версию машин факторизации. Мы увидим, почему они превосходят обычные машины факторизации, и как можно интерпретировать архитектуру этих нейронных сетей. Мы увидим, что DeepFM была разработана как улучшение вышедшей до этого модели Wide&Deep от Google, которая была одним из первых крупных прорывов в области глубокого обучения рекомендательных систем. В конце концов это приведет нас к упомянутой выше статье по DLRM, опубликованной Facebook’ом в 2019-м, которую можно считать упрощением и небольшим усовершенствованием DeepFM.

NCF

В 2017-м группа исследователей опубликовала свою работу о Нейронной Коллаборативной Фильтрации (NCF). Она содержит обобщенный фреймворк для изучения нейронных зависимостей, моделируемых факторизацией матриц при коллаборативной фильтрации с помощью нейронной сети. Авторы также объяснили, как получить зависимости высшего порядка (MF имеет порядок всего лишь 2), и как объединить оба эти подхода.

Общая идея заключается в том, что нейронная сеть может (теоретически) усвоить любую функциональную зависимость. Это значит, что зависимость, которую модель коллаборативной фильтрации выражает матричной факторизацией, может быть усвоена нейронной сетью. NCF предлагает простой слой представления сразу для пользователей и объектов (похожий на классическую факторизацию матриц), за которым следует простая нейронная сеть вроде многослойного перцептрона, которая должна усвоить зависимость между представлениями пользователя и объекта, аналогичную произведению факторизованных матриц.

Рис. 2. Из статьи "Нейронная коллаборативная фильтрация" Кс. Хе, Л. Ляо, Х. Жанг, Л. Ни, Кс. Ху, Ц. Чуа – Материалы 26-й международной конференции по World-Wide Web, 2017.
Рис. 2. Из статьи “Нейронная коллаборативная фильтрация” Кс. Хе, Л. Ляо, Х. Жанг, Л. Ни, Кс. Ху, Ц. Чуа – Материалы 26-й международной конференции по World-Wide Web, 2017.

Преимущество этого подхода заключается в нелинейности многослойного перцептрона. Простое произведение матриц, используемое при матричной факторизации, всегда будет ограничивать модель взаимодействиями 2-й степени, тогда как нейронная сеть с X слоями в теории может усвоить взаимодействия гораздо более высоких степеней. Представьте себе, например, три качественные переменные, все имеющие взаимодействия друг с другом – например, мужской пол, подростковый возраст и ролевые компьютерные игры.

В реальных задачах мы не просто используем двоичные векторы, соответствующие пользователю и объекту в качестве необработанных данных для их представления, но, очевидно, включаем и прочую дополнительную или мета-информацию, которая может представлять ценность (например, возраст, страну, аудио- и текстовые записи, метки времени,…), так что в реальности у нас получается набор данных очень высокой размерности, сильно разреженный и содержащий смесь качественных переменных с количественными. К этому моменту представленную на рис. 2 нейронную сеть можно считать и рекомендацией на основе содержимого в виде простого нейронного бинарного классификатора прямого прохода. И эта интерпретация – ключевая для понимания того, почему этот подход в конце концов оказывается гибридным между коллаборативной фильтрацией и рекомендациями на основе содержимого. Эта нейронная сеть может усвоить любые функциональные зависимости – например, взаимодействия 3-й степени и выше, вроде x1 * x2 * x3, или любые нелинейные трансформации в классическом понимании, используемом в нейронных классификаторах – в виде sigma(.. sigma(w1x1+w2x2+w3x3+b)).

Вооружившись мощью изучения зависимостей высшего порядка, мы можем использовать простой способ изучения зависимостей 1-го и 2-го порядков, скомбинировав нейронную сеть с широко известной моделью для их изучения, Машиной Факторизации. Именно это авторы DeepFM предложили в своей статье. Идея этой комбинации – параллельно изучать зависимости между признаками низких и высоких порядков – ключевая часть многих современных рекомендательных систем, и в том или ином виде ее можно найти почти в каждой архитектуре нейронной сети, предлагаемой в этой области.

DeepFM

DeepFM – это смешанный подход, включающий факторизацию матриц и глубокую нейронную сеть, причем оба используют один и тот же входной слой представления (embedding). Необработанные признаки трансформируются, чтобы закодировать категориальные признаки унитарным кодом (one-hot encoding). Итоговое предсказание (показатель кликабельности), выдаваемое последним словом нейронной сети, определяется так:

y^=sigmoid(yFM+yDNN)

То есть, это сумма предсказаний матричной факторизации и нейронной сети, пропущенная через сигмоидную функцию активации.

Компонент факторизации матриц – это обычная Машина Факторизации, оформленная в стиле архитектуры нейронной сети:

Рис. 3. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 3. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Часть сложения (Addition) этого слоя матричной факторизации получает вектор входных данных x от слоя разреженных признаков (Sparse Features) и умножает каждый элемент на его вес (Normal Connection) перед суммированием. Часть перемножения векторов (Inner Product) также получает вектор x, но только после его прохождения через слой представления и просто перемножает представленные векторы без весов (“Weight-1 Connection”). Сложение обеих частей вместе приводит к вышеупомянутому уравнению для Машины Факторизации:

yFM:=w0+∑i=0nwixi+∑i=1n∑j=i+1n⟨vi,vj⟩xixj

В этом уравнении перемножение xixj нужно только для записи суммы от 1 до n. Оно не является частью вычислений нейронной сети. Нейронная сеть автоматически знает, произведение каких векторов vi и vj потребуется, благодаря архитектуре слоя представления.

Архитектура слоя представления выглядит следующим образом:

Рис. 4. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 4. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Здесь Vp – матрица представлений для каждого поля p={1,2…,m} c k столбцами и количеством строк, соответствующим количеству элементов поля, закодированных двоичным образом. Выход этого слоя представления определяется как

a(0)=[e1,e2,…em]

и важно отметить, что этот слой не полносвязный, а именно – нет связей между необработанным входом любого поля и представлением любого другого поля. Представьте это следующим образом: вектор значений для пола (например, (0, 1)), закодированный унитарным кодом, не может иметь ничего общего с вектором представлений для дня недели (например, вектором (0, 1, 0, 0, 0, 0, 0), закодированный “Вторник”, или его вектором представления, например, для k=4, (12, 4, 5, 9).

Компонент FM – это Машина Факторизации, отражающая высокую важность взаимодействий 1 и 2 порядка, которые прямо складываются с выходом глубокого компонента и передаются в сигмоидную функцию активации последнего слоя.

Глубоким компонентом, как предполагается, теоретически может быть нейронная сеть любой архитектуры. Авторы рассмотрели стандартный многоуровневый перцептрон прямого прохода (а также так называемую PNN). Стандартный многоуровневый перцептрон изображен на следующем рисунке:

Рис. 5. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 5. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Нейронная сеть на основе стандартного многослойного перцептрона со слоем представления между необработанными данными (сильно разреженными после унитарного кодирования категориальных переменных) и следующими слоями нейронной сети описывается следующей формулой:

a(l+1)=σ(W(l)a(l)+b(l))

где sigma – функция активации, W – матрица весов, a – результат функции активации предыдущего слоя, а b – порог.

Это приводит к общей архитектуре нейронной сети DeepFM:

Рис. 6. Общая архитектура DeepFM
Рис. 6. Общая архитектура DeepFM

со следующими параметрами:

  • Скрытый вектор Vi для измерения влияния взаимодействий признака i с другими признаками (слой представления).
  • Vi передается в компонент FM для моделирования взаимодействий 2 порядка (компонент FM).
  • wi взвешивает важность необработанного признака i 1-го порядка (компонент FM).
  • Vi также передается в Глубокий компонент для моделирования всех взаимодействий высших порядков (>2)(Глубокий компонент).
  • WI и bI – веса и пороги нейронной сети (Глубокий компонент).

Ключ к одновременному получению взаимодействий высших и низших порядков – это одновременное обучение всех параметров под одной функцией потерь, используя один и тот же слой представления как для компонента FM, так и для Глубокого компонента.

Сравнение с Wide&Deep и NeuMF

Есть много вариаций, о которых можно задуматься, чтобы “отполировать” эту архитектуру и сделать ее еще лучше. Однако в основном все они сходятся в своем гибридном подходе, заключающемся в одновременной обработке взаимодействий высших и низших порядков. Авторы DeepFM также предложили замену многоуровневого перцептрона на так называемую PNN, глубокую нейронную сеть, получающую в качестве входных данных выводы FM и слоя представления.

Авторы статьи про NCF также предложили похожую архитектуру, которую они назвали NeuMF (Neural Matrix Factorization – нейронная факторизация матриц). Вместо использования FM в качестве компонента низшего порядка они используют обычную факторизацию матриц, результаты которой передаются в функцию активации. Этому подходу, однако, не хватает взаимодействий 1 порядка, моделируемых линейной частью FM. Авторы также указали, что модель имеет различные представления пользователя и объекта для матричной факторизации и многослойного перцептрона.

Как упомянуто выше, команда исследователей Google была одной из первых, предложивших нейронные сети для гибридного подхода к рекомендации. DeepFM можно рассматривать как дальнейшеее развитие алгоритма Wide&Deep от Google, который выглядит примерно так:

Рис. 7. Х-Т Ченг, Л. Кос, Дж. Хармсен, Т. Шакед, Т. Чандра, Х. Арадхье, Г. Андерсон, Г. Коррадо, В. Чаи, М. Испир, Р. Анил, З. Хак, Л. Хонг, В. Джейн, Кс. Лю и Х. Шах. "Широкое и глубокое обучение для рекомендательных систем" – Материалы 1 семинара по глубокому обучению для рекомендательных систем, стр. 7-10, 2016.
Рис. 7. Х-Т Ченг, Л. Кос, Дж. Хармсен, Т. Шакед, Т. Чандра, Х. Арадхье, Г. Андерсон, Г. Коррадо, В. Чаи, М. Испир, Р. Анил, З. Хак, Л. Хонг, В. Джейн, Кс. Лю и Х. Шах. “Широкое и глубокое обучение для рекомендательных систем” – Материалы 1 семинара по глубокому обучению для рекомендательных систем, стр. 7-10, 2016.

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

ϕk(x)=∏i=1dxickicki∈{0,1}

Это выражает взаимодействие между d признаками (с предшествующим представлением признаков или без него), умножая их друг на друга (показатель степени равен 1, если xi является частью k-й трансформации).

Легко видеть, что DeepFM является развитием этой модели, поскольку она не требует никакого предварительного конструирования признаков и может обучиться взаимодействиям низкого и высокого порядка на основе одних и тех же входных данных, разделяющих один и тот же слой представления. DeepFM действительно содержит Машину Факторизации как часть основной сети, тогда как Wide&Deep не выполняет произведение векторов в какой-либо части сети, а делает это предварительно на шаге конструирования признаков.

3. DLRM – рекомендационная модель глубокого обучения

Ну что ж, рассмотрев различные варианты от Google, Huawei (команда исследователей, стоящая за архитектурой DeepFM) и прочих, давайте познакомимся с видением исследователей Facebook. Они опубликовали свою статью о DLRM в 2019-м, и она в основном фокусируется на практической реализации этих моделей. Решения с параллельным обучением, переложение расчетов на GPU, а также различная обработка постоянных и категориальных признаков.

Архитектура DLRM описана на следующем рисунке и работает следующим образом: каждый категориальный признак представлен вектором представления, а постоянные признаки обрабатываются многослойным перцептроном таким образом, чтобы на выходе получались векторы такого же размера, как и векторы представления. На второй стадии рассчитываются взаимные произведения всех векторов представления и выходных векторов перцептрона. После этого произведения соединяются вместе и передаются в другой многослойный перцептрон, а в конце концов – в функцию сигмоиды, выдающую вероятность.

Нейронная сеть DLRM, как описано в <a href="http://arxiv.org/abs/1906" target="_blank" rel="noopener noreferrer nofollow">статье про DLRM</a>. Рисунок Макса Беккерса
Нейронная сеть DLRM, как описано в статье про DLRM. Рисунок Макса Беккерса

Предложение DLRM – это нечто вроде упрощенной и модифицированной версии DeepFM в том смысле, что оно также использует произведение векторов, но намеренно пытается держаться подальше от взаимодействий высших порядков, не обязательно прогоняя представленные категориальные признаки через многослойный перцептрон. Такой дизайн предназначен для копирования подхода, используемого в Машине Факторизации, когда она рассчитывает взаимодействия второго порядка между представлениями. Мы можем рассматривать всю DLRM как отдельную часть DeepFM, компонент FM. Можно считать, что классический Глубокий компонент DeepFM, вывод которого складывается с выводом компонента FM в финальном слое DeepFM (а потом передается в функцию сигмоиды) в DLRM полностью отсутствует. Теоретические преимущества DeepFM очевидны, поскольку ее дизайн намного лучше приспособлен для изучения взаимодействий высших порядков, однако, по мнению специалистов Facebook:

“взаимодействия выше второго порядка, используемые в других сетях, не обязательно стоят дополнительных затрат вычислительной мощности и памяти”.

4. Обзор и кодирование

Представив различные подходы к глубокой рекомендации, их теоретические основы, преимущества и недостатки, я был просто вынужден взглянуть на предлагаемую реализацию DLRM на PyTorch на GitHub-странице Facebook.

Я изучил детали реализации и протестировал предлагаемые специальные API наборов данных, которые авторы создали для прямой обработки различных наборов данных. Как соревнование по рекламе дисплеев на Kaggle от Criteo, так и их набор данных Terabyte имеют готовые реализации API, их можно загрузить и впоследствии использовать для обучения полной DLRM всего одной командой bash (инструкции см. в репозитории DLRM). Затем я расширил API модели DLRM от Facebook, добавив шаги загрузки и предварительной обработки для другого набора данных, “Предсказание показателя кликабельности для рекламы DIGIX в 2020”. Результат можно найти здесь.

Примерно так же, как и для приведенных авторами примеров, после загрузки и распаковки данных DIGIX, вы также сможете обучить модель на этом наборе данных одной командой bash. Все шаги предварительной обработки, размеры представлений и параметры архитектуры нейронной сети были настроены на обработку набора данных DIGIX. Блокнот, который проведет вас по этим шагам, можно найти здесь. Эта модель выдает приличные результаты, и я продолжаю над ней работать с целью улучшения производительности посредством лучшего понимания необработанных данных и процесса работы с рекламными объявлениями, используемого в DIGIX. Специализированная очистка данных, настройка гиперпараметров и конструирование признаков – все это вещи, над которыми я хотел бы еще поработать, и они упомянуты в блокноте. Моей первой целью было технически рациональное расширение API модели DLRM, способное использовать необработанные данные DIGIX в качестве входных данных.

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

Ссылки

Стеффен Рендл, “Машины факторизации”, Международная конференция IEEE по Data Mining, стр. 995-1000, 2010.

Ксианьян Хе, Лизи Ляо, Ханванг Жанг, Ликианг Ли, Ксиа Ху и Тат-Сенг Чуа. “Нейронная коллаборативная фильтрация”, Материалы 26-й международной конференции по World-Wide Web, стр. 173-182, 2017.

Хуифенг Гуо, Руиминг Тэнг, Юнминь Е, Женгуо Ли и Ксиукианг Хе. “DeepFM: нейронная сеть для предсказания показателя кликабельности, основанная на машине факторизации”, препринт arXiv:1703.04247, 2017.

Джианксун Лиан, Ксиаохуан Жоу, Фуженг Жанг, Жонгксиа Чен, Ксинг Кси и Гуангжонг Сун. “xDeepFM: комбинируем явные и неявные взаимодействия признаков для рекомендательных систем”, в Материалах 24-й международной конференции ACM SIGKDD по исследованию знаний и Data Mining, стр. 1754–1763. ACM, 2018.

Хенг-Це Ченг, Левент Коц, Джеремия Хармсен, Тал Шакед, Тушар Чандра, Хриши Арадхье, Глен Андерсон, Грег Коррадо, Вей Чай, Мустафа Испир, Рохан Анил, Закария Хак, Личан Хонг, Вихан Джайн, Ксяобинг Лю и Хемаль Шах. “Широкое и глубокое обучение для рекомендательных систем”, в материалах 1-го семинара по глубокому обучению рекомендательных систем”, стр. 7-10, 2016.

М. Наумов, Д. Мудигер, Х.М. Ши, Дж. Хуанг, Н. Сундараман, Дж. Парк, Кс. Ванг, У. Гупта, Ц. Ву, А.Г. Аццолини, Д. Джулгаков, А. Малевич, И. Чернавский, Ю. Лю, Р. Кришнамурти, А. Ю, В. Кондратенко, С. Перейра, Кс. Чен, В. Чен, В. Рао, Б. Джиа, Л. Ксионг и М. Смелянский “Рекомендационная модель глубокого обучения для систем персонализации и рекомендации”, CoRR, vol. abs/1906.00091, 2019. [Онлайн]. Доступна здесь.

19
Фев
2021

10 вопросов на позицию специалиста по Data Science

По 5 вопросов с собеседований из двух обязательных для Data Scientist областей знаний — теории вероятности и машинного обучения
— Читать дальше «10 вопросов на позицию специалиста по Data Science»

29
Янв
2021

Задача на собеседовании: провести прямую через набор точек

Ищем наиболее вероятные положения автономного автомобиля, который едет прямо по дороге и отслеживается по GPS.
— Читать дальше «Задача на собеседовании: провести прямую через набор точек»

19
Янв
2021

Как муравьи решают проблемы коммивояжёров

Для решения задачи коммивояжёра используются разные алгоритмы, один из них называется «муравьиным». Разбираемся, что он из себя представляет.
— Читать дальше «Как муравьи решают проблемы коммивояжёров»

15
Янв
2021

Механика «Тетриса» легла в основу алгоритма «идеального» заполнения гостиниц

Разработчики уже пытаются получить патент на своё «изобретение».
— Читать дальше «Механика «Тетриса» легла в основу алгоритма «идеального» заполнения гостиниц»

04
Янв
2021

🐍 Анимация градиентного спуска и ландшафта функции потерь на Python

Демонстрация работающих примеров визуализации ландшафта функции потерь и анимации процесса градиентного спуска.

Статья публикуется в переводе, автор оригинального текста Tobias Roeschl.

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

Ландшафт функции потерь сверточной нейронной сети с 56 слоями (VGG-56, <a href="https://arxiv.org/abs/1712.09913" target="_blank" rel="noopener noreferrer nofollow">источник</a>)
Ландшафт функции потерь сверточной нейронной сети с 56 слоями (VGG-56, источник)

Приведенное выше изображение демонстрирует крайне невыпуклый ландшафт функции потерь нейронной сети. Ландшафт функции потерь – это визуальное представление значений, которые принимает целевая функция на наших тренировочных данных. Поскольку наша цель – визуализация потерь в трех измерениях, мы должны выбрать два параметра, которые будут изменяться, а остальные параметры останутся неизменными. Однако стоит заметить, что существуют продвинутые техники (например, сокращение размерности или filter response normalization), которые можно использовать для аппроксимации ландшафта функции потерь в подпространстве параметров с более низкой размерностью. Трехмерное представление функции потерь нейронной сети VGG с 56 слоями изображено на рис. 1. Однако это выходит за пределы данной статьи.

Искусственная нейронная сеть, над которой мы будем работать, состоит из одного входного слоя (с 784 узлами), двух скрытых слоев (с 50 и 500 узлами соответственно) и выходного слоя (с 10 узлами). Мы будем везде использовать сигмоиду в качестве функции активации. Эта нейронная сеть не будет содержать никаких порогов. Тренировочные данные состоят из изображений размером 28*28 пикселей с рукописными цифрами от 0 до 9 из набора данных MNIST. Технически, мы могли бы выбрать любые два веса из 784*50+50*500+500*10 = 69.200 весов, используемых в нашей сети, но я произвольно решил выбрать веса w250,5 (2) и w251,5(2), соединяющие 250-й и 251-й узлы второго скрытого слоя с шестым выходным нейроном, соответственно. Шестой выходной нейрон предсказывает, можно ли на данном изображении увидеть цифру ‘5’. Следующий рисунок схематически изображает архитектуру нейронной сети, с которой мы собираемся работать. Для простоты и понятности некоторые связи между нейронами – и большинство подписей с весами – были намеренно опущены.

Рис. 2. Архитектура нейронной сети (создана автором в <a href="https://app.diagrams.net/" target="_blank" rel="noopener noreferrer nofollow">draw.io</a>)
Рис. 2. Архитектура нейронной сети (создана автором в draw.io)

На Python’е мы сначала импортируем набор данных MNIST. Поскольку рукописные цифры в этом наборе представлены в виде изображений с градациями серого цвета, мы можем нормализовать наши входные данные, преобразовав значения пикселей из диапазона 0-255 к диапазону 0-1. разделив эти значения на 255.

        # Импортируем библиотеки
import numpy as np
import gzip
from sklearn.preprocessing import OneHotEncoder
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from scipy.special import expit
import celluloid
from celluloid import Camera
from matplotlib import animation 

# Открываем файлы MNIST: 
def open_images(filename):
    with gzip.open(filename, "rb") as file:     
        data=file.read()
        return np.frombuffer(data,dtype=np.uint8, offset=16).reshape(-1,28,28).astype(np.float32) 

def open_labels(filename):
    with gzip.open(filename,"rb") as file:
        data = file.read()
        return np.frombuffer(data,dtype=np.uint8, offset=8).astype(np.float32) 
    
X_train=open_images("C:\\Users\\tobia\\train-images-idx3-ubyte.gz").reshape(-1,784).astype(np.float32) 
X_train=X_train/255 # rescale pixel values to 0-1

y_train=open_labels("C:\\Users\\tobia\\train-labels-idx1-ubyte.gz")
oh=OneHotEncoder(categories='auto') 
y_train_oh=oh.fit_transform(y_train.reshape(-1,1)).toarray() # one-hot-encoding of y-values
    

Чтобы создать ландшафты потерь, мы собираемся нарисовать трехмерный график потерь по отношению к двум упомянутым выше весам w250_5(2) и w251_5(2). Чтобы это сделать, мы должны определить функцию потерь среднеквадратичной ошибки по отношению к весам w_a и w_b. Потери нашей модели равны средней сумме квадратичных ошибок между предсказаниями модели и истинными значениями для каждого из 10 выходных нейронов. Для N примеров эта функция будет выглядеть так:

J(y,pred)=1N∑i=1N(∑k=110(yi,k−predi,k)2)

Здесь y и pred представляют, соответственно, матрицы актуальных и предсказанных значений y. Предсказанные значения рассчитываются прямым проходом входных данных по нейронной сети до выходного слоя. Выход каждого слоя служит входом для следующего слоя. Входная матрица умножается на матрицу весов соответствующего слоя. После этого применяется функция сигмоиды для получения выхода данного конкретного слоя. Эти матрицы весов инициализируются небольшими случайными числами с помощью генератора псевдо-случайных чисел numpy. Используя инициализацию (seed), мы можем обеспечить воспроизводимость данных. После этого мы заменяем два веса, которым разрешено изменяться, аргументами w_a и w_b. На Python мы можем реализовать функцию потерь следующим образом:

        hidden_0=50 # количество узлов первого скрытого слоя 
hidden_1=500 # количество узлов второго скрытого слоя 

# Зададим функцию потерь:
def costs(x,y,w_a,w_b,seed_):  
        np.random.seed(seed_) # задаем инициализатор генератора случайных чисел 
        w0=np.random.randn(hidden_0,784)  # матрица весов 1-го скрытого слоя
        w1=np.random.randn(hidden_1,hidden_0) # матрица весов 2-го скрытого слоя
        w2=np.random.randn(10,hidden_1) # матрица весов выходного слоя
        w2[5][250] = w_a # задаем значение веса w_250,5(2)
        w2[5][251] = w_b # задаем значение веса w_251,5(2)
        a0 = expit(w0 @ x.T)  # выход 1-го скрытого слоя 
        a1=expit(w1 @ a0)  # выход 2-го скрытого слоя 
        pred= expit(w2 @ a1) # выход последнего слоя 
        return np.mean(np.sum((y-pred)**2,axis=0)) # потери w.r.t. w_a и w_b
    

Чтобы создать картинку, мы определяем диапазон значений наших весов и строим ячеистую сеть для получения всех возможных комбинаций значений весов w_a и w_b. Для каждой пары w_a и w_b нашей сети мы рассчитываем потери с помощью нашей функции потерь. После этого мы, наконец, можем создать ландшафт функции потерь:

        # Зададим набор значений для ячеистой сети: 
m1s = np.linspace(-15, 17, 40)   
m2s = np.linspace(-15, 18, 40)  
M1, M2 = np.meshgrid(m1s, m2s) # создаем ячеистую сеть  

# Определим потери для каждой координаты ячеистой сети: 
zs_100 = np.array([costs(X_train[0:100],y_train_oh[0:100].T  
                               ,np.array([[mp1]]), np.array([[mp2]]),135)  
                        for mp1, mp2 in zip(np.ravel(M1), np.ravel(M2))])
Z_100 = zs_100.reshape(M1.shape) # Значения z для N=100

zs_10000 = np.array([costs(X_train[0:10000],y_train_oh[0:10000].T  
                               ,np.array([[mp1]]), np.array([[mp2]]),135)  
                       for mp1, mp2 in zip(np.ravel(M1), np.ravel(M2))])
Z_10000 = zs_10000.reshape(M1.shape) # Значения z для N=10,000


# Рисуем ландшафты функции потерь: 
fig = plt.figure(figsize=(10,7.5)) # создаем фигуру
ax0 = fig.add_subplot(121, projection='3d' )
ax1 = fig.add_subplot(122, projection='3d' )

fontsize_=20 # задаем размер шрифта для меток осей 
labelsize_=12 # задаем размер меток делений 

# Настраиваем дочерние рисунки (subplots): 
ax0.view_init(elev=30, azim=-20)
ax0.set_xlabel(r'$w_a$', fontsize=fontsize_, labelpad=9)
ax0.set_ylabel(r'$w_b$', fontsize=fontsize_, labelpad=-5)
ax0.set_zlabel("costs", fontsize=fontsize_, labelpad=-30)
ax0.tick_params(axis='x', pad=5, which='major', labelsize=labelsize_)
ax0.tick_params(axis='y', pad=-5, which='major', labelsize=labelsize_)
ax0.tick_params(axis='z', pad=5, which='major', labelsize=labelsize_)
ax0.set_title('N:100',y=0.85,fontsize=15) # задаем заголовок дочернего рисунка

ax1.view_init(elev=30, azim=-30)
ax1.set_xlabel(r'$w_a$', fontsize=fontsize_, labelpad=9)
ax1.set_ylabel(r'$w_b$', fontsize=fontsize_, labelpad=-5)
ax1.set_zlabel("costs", fontsize=fontsize_, labelpad=-30)
ax1.tick_params(axis='y', pad=-5, which='major', labelsize=labelsize_)
ax1.tick_params(axis='x', pad=5, which='major', labelsize=labelsize_)
ax1.tick_params(axis='z', pad=5, which='major', labelsize=labelsize_)
ax1.set_title('N:10,000',y=0.85,fontsize=15)

# Поверхностные графики потерь (= ландшафты функции потерь):  
ax0.plot_surface(M1, M2, Z_100, cmap='terrain', #поверхностный график
                             antialiased=True,cstride=1,rstride=1, alpha=0.75)
ax1.plot_surface(M1, M2, Z_10000, cmap='terrain', #поверхностный график
                             antialiased=True,cstride=1,rstride=1, alpha=0.75)
plt.tight_layout()
plt.show()
    
Рис. 3. Ландшафты функции потерь для разных размеров тренировочного набора (изображение автора)
Рис. 3. Ландшафты функции потерь для разных размеров тренировочного набора (изображение автора)

Рисунок 3 изображает два примера ландшафтов функции потерь для одних и тех же весов (w250_5(2) и w251_5(2)) и одинаковых начальных значений всех весов. Левый ландшафт был построен на первых 100 изображениях из набора данных MNIST, а правый – на первых 10.000 изображениях. При ближайшем рассмотрении левого графика там можно увидеть типичные особенности невыпуклых поверхностей: локальные минимумы, плато, хребты (иногда называемые “седловыми точками”) и “глобальный” минимум. Однако термин “минимум” следует использовать осторожно, поскольку мы видели лишь небольшой набор значений, и не проводили анализ производной.

Рис. 4 (создан автором с помощью <a href="https://app.diagrams.net/" target="_blank" rel="noopener noreferrer nofollow">draw.io</a>)
Рис. 4 (создан автором с помощью draw.io)

Градиентный спуск

Эти “географические барьеры” – полная противоположность выпуклым и гладким ландшафтам функции потерь, которые можно увидеть для линейной регрессии или логистической регрессии. Считается, что эти “барьеры” замедляют или даже препятствуют достижению глобального минимума методом градиентного спуска, и, следовательно, оказывают негативное влияние на качество модели. Чтобы исследовать это явление, я решил анимировать градиентный спуск для данного ландшафта функции потерь из трех различных “стартовых позиций”. Градиентный спуск, в целом, заключается в обновлении параметров модели (в данном случае – весов) в соответствии со следующим уравнением:

we+1=we−αΔJ(we)

Здесь Delta J представляет градиент функции потерь, w – веса всей модели, e представляет текущую эпоху обучения, а aplha – скорость обучения.

Поскольку оба веса в нашем примере соединяются с выходным слоем нейронной сети, достаточно получить частные производные по этим весам для последнего слоя. Чтобы сделать это, мы применяем цепное правило и получаем следующее:

∂J∂wij(2)=∂J∂outi(2)∂outi(2)∂ini(2)∂ini(2)∂wij(2)

Здесь wij определяется как вес между j-м узлом предыдущего слоя и i-м узлом текущего слоя, которым в нашем случае является выходной слой. Вход i-го нейрона выходного слоя обозначен просто как ini(2), что эквивалентно сумме активаций предыдущего слоя, умноженных на соответствующие веса связей, ведущих к этому узлу. Выход i-го нейрона выходного слоя обозначен как outi(2), что соответствует сигмоиде(ini(2)). Решая приведенное выше уравнение, мы получаем:

∂J∂wij(2)=(outi(2)−targeti)⋅outi(2)⋅(1−outi(2))⋅outj(1)

Здесь outj(1) соответствует активации j-го узла предыдущего слоя, соединенного с i-м нейроном выходного слоя связью с весом wij. Переменная targeti соответствует целевому выводу каждого из 10 нейронов выходного слоя. Возвращаясь к Рис. 2, outj(1) будет соответствовать активации h250 или h251, в зависимости от веса, по которому мы хотим рассчитать частную производную. Прекрасное объяснение обратного распространения (backpropagation), включая математические детали дифференцирования, можно найти здесь.

Поскольку выход нейронов выходного слоя эквивалентен предсказаниям всей нашей нейронной сети, мы используем удобное сокращение pred в следующем коде. Поскольку концентрация на одном конкретном узле может привести к коду, сводящему с толку, мы будем придерживаться уже взятого принципа использовать матрицы весов и перемножение матриц для одновременного обновления всех весов выходного слоя. Наконец, мы будем обновлять только те два веса выходного слоя, которые собирались обновлять с самого начала. На Python’е мы реализуем наш алгоритм градиентного спуска только для двух весов следующим образом:

        # Сохраняем значения потерь и весов в списках: 
weights_2_5_250=[] 
weights_2_5_251=[] 
costs=[] 

seed_= 135 # для инициализации генератора случайных чисел
N=100 # размер выборки 

# Задаем нейронную сеть: 
class NeuralNetwork(object):
    def __init__(self, lr=0.01):
        self.lr=lr
        np.random.seed(seed_) # Инициализируем генератор случайных чисел
        # Инициализируем матрицы весов: 
        self.w0=np.random.randn(hidden_0,784)  
        self.w1=np.random.randn(hidden_1,hidden_0)
        self.w2=np.random.randn(10,hidden_1)
        self.w2[5][250] = start_a # задать стартовое значение для w_a
        self.w2[5][251] = start_b # задать стартовое значение для w_b
    
    def train(self, X,y):
        a0 = expit(self.w0 @ X.T)  
        a1=expit(self.w1 @ a0)  
        pred= expit(self.w2 @ a1)
        # Частные производные функции потерь w.r.t. весов выходного слоя: 
        dw2= (pred - y.T)*pred*(1-pred)  @ a1.T / len(X)   # ... среднее по выборке
        # Обновляем веса: 
        self.w2[5][250]=self.w2[5][250] - self.lr * dw2[5][250] 
        self.w2[5][251]=self.w2[5][251] - self.lr * dw2[5][251] 
        costs.append(self.cost(pred,y)) # дописываем значения потерь в список
    
    def cost(self, pred, y):
        return np.mean(np.sum((y.T-pred)**2,axis=0))
    
# Начальные значения w_a/w_b: 
starting_points = [  (-9,15),(-10.1,15),(-11,15)] 

for j in starting_points:
    start_a,start_b=j
    model=NeuralNetwork(10) # установить скорость обучения в 10
    for i in range(10000):  # 10,000 эпох           
        model.train(X_train[0:N], y_train_oh[0:N]) 
        weights_2_5_250.append(model.w2[5][250]) # дописываем значения весов в список
        weights_2_5_251.append(model.w2[5][251]) # дописываем значения весов в список

# Create sublists of costs and weight values for each starting point: 
costs = np.split(np.array(costs),3) 
weights_2_5_250 = np.split(np.array(weights_2_5_250),3)
weights_2_5_251 = np.split(np.array(weights_2_5_251),3)
    

Поскольку мы обновляем только два веса из многих тысяч весов модели, потери будут падать лишь незначительно, несмотря на сравнительно высокую скорость обучения alpha=10. Это также является причиной того, что веса, которые мы собирались изменять, существенно меняются, тогда как остальные веса меняются лишь незначительно при обновлении весов всей модели. Теперь мы можем анимировать три траектории градиентного спуска для трех различных начальных точек.

        fig = plt.figure(figsize=(10,10)) # создаем фигуру
ax = fig.add_subplot(111,projection='3d' ) 
line_style=["dashed", "dashdot", "dotted"] # стили линий
fontsize_=27 # задаем размер шрифта для меток осей 
labelsize_=17 # задаем размер шрифта для меток делений
ax.view_init(elev=30, azim=-10)
ax.set_xlabel(r'$w_a$', fontsize=fontsize_, labelpad=17)
ax.set_ylabel(r'$w_b$', fontsize=fontsize_, labelpad=5)
ax.set_zlabel("costs", fontsize=fontsize_, labelpad=-35)
ax.tick_params(axis='x', pad=12, which='major', labelsize=labelsize_)
ax.tick_params(axis='y', pad=0, which='major', labelsize=labelsize_)
ax.tick_params(axis='z', pad=8, which='major', labelsize=labelsize_)
ax.set_zlim(4.75,4.802) # задаем диапазон значений по z в графике

# Определяем, график каких эпох рисовать:
p1=list(np.arange(0,200,20))
p2=list(np.arange(200,9000,100))
points_=p1+p2

camera=Camera(fig) # создаем объект Camera
for i in points_:
    # Рисуем три траектории градиентного спуска...
    #... каждая начинается из своей начальной точки
    #... и имеет собственный уникальный стиль линии:
    for j in range(3): 
        ax.plot(weights_2_5_250[j][0:i],weights_2_5_251[j][0:i],costs[j][0:i],
                linestyle=line_style[j],linewidth=2,
                color="black", label=str(i))
        ax.scatter(weights_2_5_250[j][i],weights_2_5_251[j][i],costs[j][i],
                   marker='o', s=15**2,
               color="black", alpha=1.0)
    # Surface plot (= loss landscape):
    ax.plot_surface(M1, M2, Z_100, cmap='terrain', 
                             antialiased=True,cstride=1,rstride=1, alpha=0.75)
    ax.legend([f'epochs: {i}'], loc=(0.25, 0.8),fontsize=17) # позиция надписи
    plt.tight_layout() 
    camera.snap() # сделать снимок после каждой итерации
    
animation = camera.animate(interval = 5, # интервал между фреймами в миллисекундах
                          repeat = False,
                          repeat_delay = 0)
animation.save('gd_1.gif', writer = 'imagemagick', dpi=100)  # сохраним анимацию  
    
Рис. 5. Траектории градиентного спуска (создано автором)
Рис. 5. Траектории градиентного спуска (создано автором)

Как и ожидалось, невыпуклость ландшафта функции потерь делает возможными различные пути градиентного спуска в зависимости от начальных значений наших двух весов. Это приводит к различным значениям функции потерь после заданного количества эпох, и, следовательно, разному качеству моделей. Контурный график предлагает другой взгляд на ту же функцию потерь.

        fig = plt.figure(figsize=(10,10)) # создаем фигуру
ax0=fig.add_subplot(2, 1, 1) 
ax1=fig.add_subplot(2, 1, 2) 

# Задаем параметры дочерних рисунков (subplots): 
ax0.set_xlabel(r'$w_a$', fontsize=25, labelpad=0)
ax0.set_ylabel(r'$w_b$', fontsize=25, labelpad=-20)
ax0.tick_params(axis='both', which='major', labelsize=17)
ax1.set_xlabel("epochs", fontsize=22, labelpad=5)
ax1.set_ylabel("costs", fontsize=25, labelpad=7)
ax1.tick_params(axis='both', which='major', labelsize=17)

contours_=21 # задаем количество контурных линий
points_=np.arange(0,9000,100) # определяем, какие эпохи рисовать

camera = Camera(fig) # создаем объект Camera
for i in points_:
    cf=ax0.contour(M1, M2, Z_100,contours_, colors='black', # контурный график
                     linestyles='dashed', linewidths=1)
    ax0.contourf(M1, M2, Z_100, alpha=0.85,cmap='terrain') # контурные графики с заливкой 
    
    for j in range(3):
        ax0.scatter(weights_2_5_250[j][i],weights_2_5_251[j][i],marker='o', s=13**2,
               color="black", alpha=1.0)
        ax0.plot(weights_2_5_250[j][0:i],weights_2_5_251[j][0:i],
                linestyle=line_style[j],linewidth=2,
                color="black", label=str(i))
        
        ax1.plot(costs[j][0:i], color="black", linestyle=line_style[j])
    plt.tight_layout()
    camera.snap()
    
animation = camera.animate(interval = 5,
                          repeat = True, repeat_delay = 0)  # создаем анимацию 
animation.save('gd_2.gif', writer = 'imagemagick')  # сохраняем анимацию в gif
    
Рис.6. Траектории градиентного спуска в 2D (создано автором)
Рис.6. Траектории градиентного спуска в 2D (создано автором)

Обе анимации иллюстрируют, что при невыпуклом ландшафте функции потерь градиентный спуск может “зависнуть” на локальном минимуме, седловой точке или плато. Для преодоления некоторых из этих проблем было изобретено множество вариантов градиентного спуска (ADAGRAD, Adam и т.д.) Однако я хочу разъяснить, что не все ландшафты функции потерь сильно невыпуклые в заданном диапазоне значений w_a и w_b. Выпуклость функции потерь зависит, среди прочего, от количества скрытых слоев – у глубоких нейронных сетей ландшафт функции потерь обычно сильно невыпуклый.

Я решил создать несколько произвольных ландшафтов функции потерь путем изменения числа, инициализирующего генератор случайных чисел. На этот раз веса, которым разрешено меняться, находятся на втором скрытом слое (код). Репрезентативная выборка ландшафтов функции потерь, которые я встретил, применяя этот подход, показана ниже. Размеры выборки и индексы весов, обозначенных как w_a и w_b, указаны в подписях рисунков.

Рис. 7. N=500, w200-30(1), w200-31(1). Создано автором (<a href="https://gist.github.com/dbc60bb7c6ef0b8ae3f8ceab8c334b57.git" target="_blank" rel="noopener noreferrer nofollow">код</a>)
Рис. 7. N=500, w200-30(1), w200-31(1). Создано автором (код)
Рис. 8 N=1000, w5_5(1), w5_6(1). Создано автором (<a href="https://gist.github.com/4f87869ae3e94eb6331fb9e213e9f343.git" target="_blank" rel="noopener noreferrer nofollow">код</a>).
Рис. 8 N=1000, w5_5(1), w5_6(1). Создано автором (код).

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

Полный блокнот с исходными текстами визуализации можно найти в моем GitHub’е.

Ссылки

База рукописных цифр MNIST (Янн ЛеКун, Коринна Кортес и Крис Буржс).

  1. Ли Хао и др. “Визуализация ландшафтов функции потерь нейронных сетей”. Достижения нейронных систем обработки информации, 2018.
  2. https://machinelearningmastery.com/how-to-normalize-center-and-standardize-images-with-the-imagedatagenerator-in-keras/
  3. https://machinelearningmastery.com/why-training-a-neural-network-is-hard/
  4. https://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/
  5. Мэттью Стэйб, Сашанк Дж. Редди, Сэтьен Кэйл, Санджив Кумар, Суврит Сра. “Избежание седловых точек адаптивными градиентными методами” (2019).
  6. Ян Дофин и др. “Обнаружение и уничтожение проблемы седловых точек при невыпуклой оптимизации в пространстве с большим количеством измерений”. NIPS (2014).
  7. А. Хороманска, М. Хенафф, М. Матье, Г.Б. Аруз и Я. ЛеКун. “Ландшафты функции потерь нейронных сетей со множеством слоев”. Журнал исследований машинного обучения, 38, 192-204.

Приложение

Демонстрационное изображение (создано автором)
Демонстрационное изображение (создано автором)
25
Дек
2020

Как работает лифт в небоскребах? Алгоритмы + задачи с собеседований

Алгоритм по которому работает лифт в высотном здании должен учитывать множество факторов. Он сложнее чем у обычного лифта.
— Читать дальше «Как работает лифт в небоскребах? Алгоритмы + задачи с собеседований»

08
Дек
2020

На GitHub опубликовали алгоритм для расшифровки «пикселизированных» изображений

Очень часто объекты, которые пытаются сделать анонимными, скрывают за пиксельной сеткой. Что-то похожее можно получить, открыв картинку с низким разрешением на полный экран. И вот, судя по всему, начался процесс заката данного способа шифрования.
— Чит…

30
Ноя
2020

Хакатон Code Battle Online: Tetris

Игровой мини-хакатон для начинающих IT-специалистов с базовыми навыками в C#, Java, JavaScript, Python или C++.
— Читать дальше «Хакатон Code Battle Online: Tetris»

24
Ноя
2020

Стоит прочитать: обзор книги Кормена и Лейзерсона «Алгоритмы. Построение и анализ»

В книге охватывается основной спектр современных алгоритмов: сортировки, графовые алгоритмы, динамическое программирование и тому подобное.
— Читать дальше «Стоит прочитать: обзор книги Кормена и Лейзерсона «Алгоритмы. Построение и анализ»»

03
Ноя
2020

🐍Сложность алгоритмов и операций на примере Python

Определить вычислительную сложность отдельных операций просто, но как вычислить сложность целой функции? Попробуем ответить на этот вопрос в небольшой статье.

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

Такой тип анализа называется статическим, так как не требует запуска программы, – в противовес динамическому, или эмпирическому, анализу, при котором проводятся измерения параметров работающего кода.

Классы сложности операций в Python

Самое базовое понятие статического анализа – O(1). Этот класс сложности имеют операции, которые выполняются за константное время, например, создание переменной или сложение небольших чисел.

Время выполнения большинства операций зависит от количества элементов, с которыми приходится работать, например, от размера списка. Например, класс сложности O(N) описывает линейную зависимость. Если размер списка увеличится в два раза, то операция также будет выполняться в два раза дольше.

Параметр N, который вы встретите далее, – это размер структуры данных – len(data_structure).

Рассмотрим основные операции некоторых структур данных в Python.

Списки (lists)

Операция Пример Сложность Примечания
Получение элемента l[i] O(1)
Сохранение элемента l[i] = 0 O(1)
Размер списка len(l) O(1)
Добавление элемента в конец списка l.append(5) O(1)
Удаление последнего элемента (pop) l.pop() O(1) То же, что и l.pop(-1)
Очищение списка l.clear() O(1) То же, что и l = []
Получение среза l[a:b] O(b-a) l[1:5] => O(1), l[:] => O(len(l) – 0) = O(N)
Расширение l.extend(...) O(len(…)) Зависит от размера расширения
Создание list(...) O(len(…)) Зависит от размера итерируемой структуры (…)
Сравнение списков (==, !=) l1 == l2 O(N)
Вставка l[a:b] = ... O(N)
Удаление элемента (del) del l[i] O(N) Зависит от i. O(N) – в худшем случае
Проверка наличия x in/not in l O(N) Линейный поиск в списке
Копирование l.copy() O(N) То же, что и l[:]
Удаление значения (remove) l.remove(...) O(N)
Удаление элемента (pop) l.pop(i) O(N) O(N-i). Для l.pop(0) => O(N)
Получение минимального/максимального значения min(l)/max(l) O(N) Линейный поиск в списке
Разворачивание списка l.reverse() O(N)
Перебор for v in l: O(N) В худшем случае, без прерывания цикла (return/break)
Сортировка l.sort() O(N Log N)
Умножение k*l O(k N) 5*l => O(N), len(l)*l => O(N2)

Кортежи (tuples) поддерживают все операции, которые не изменяют структуру данных – и они имеют такие же классы сложности, как у списков.

Множества (sets)

Операция Пример Сложность Примечания
Размер множества len(s) O(1)
Добавление элемента s.add(5) O(1)
Проверка наличия значения x in/not in s O(1) Для списков и кортежей => O(N)
Удаление значения (remove) s.remove(..) O(1) Для списков и кортежей => O(N)
Удаление значения (discard) s.discard(..) O(1)
Удаление значения (pop) s.pop() O(1) Удаляемое значение выбирается “рандомно”
Очищение множества s.clear() O(1) То же, что и s = set()
Создание set(...) O(len(…)) Зависит от размера итерируемой структуры (…)
Сравнение множеств (==, !=) s != t O(len(s)) То же, что и len(t)
Сравнение множеств (<=/<) s <= t O(len(s)) issubset
Сравнение множеств (>=/>) s >= t O(len(t)) issuperset s <= t == t >= s
Объединение (union) s | t O(len(s)+len(t))
Пересечение (intersection) s & t O(len(s)+len(t))
Разность (difference) s – t O(len(s)+len(t))
Симметричная разность s ^ t O(len(s)+len(t))
Перебор множества for v in s: O(N) В худшем случае, без прерывания цикла (return/break)
Копирование s.copy() O(N)

Ряд операций со множествами имеет сложность O(1), в отличие от аналогичных операций со списками и кортежами. Более быстрая реализация обусловлена тем, что множествам не требуется хранить информацию о порядке элементов.

Неизменяемые множества (frozen sets) поддерживают все операции, которые не изменяют структуру данных – и они имеют такие же классы сложности, как у обычных множеств.

Словари (dict и defaultdict)

Операция Пример Сложность Примечания
Получение элемента d[k] O(1)
Сохранение элемента d[k] = v O(1)
Размер словаря len(d) O(1)
Удаление элемента (del) del d[k] O(1)
get/setdefault d.get(k) O(1)
Удаление (pop) d.pop(k) O(1)
Удаление (popitem) d.popitem() O(1) Удаляемое значение выбирается “рандомно”
Очищение словаря d.clear() O(1) То же, что и s = {} или s = dict()
Получение ключей d.keys() O(1) То же для d.values()
Создание словаря dict(...) O(len(…))
Перебор элементов for k in d: O(N) Для всех типов: keys, values, items. В худшем случае, без прерывания цикла

Как видно, большинство операций со словарями имеют сложность O(1).

Тип defaultdict поддерживает все эти операции с теми же классами сложности. Таким образом, вызов конструктора в том случае, если значения не найдены в defaultdict, имеет сложность O(1).

Тонкости анализа

Обратите внимание, что операция for i in range(...) имеет сложность O(len(...)). Для for i in range(1, 10) она равна O(1).

Если len(alist) – это N, тогда for i in range(len(alist)) будет иметь сложность O(N), так как цикл выполняется N раз.

При этом for i in range(len(alist)/2) также имеет сложность O(N). В этом случае цикл выполняется N/2 раз, и мы можем отбросить константу 1/2. При увеличении размера списка вдвое выполняемая работа также удваивается.

Точно так же for i in range(len(alist)/1000000) имеет сложность O(N). Это важно понять, так как нас интересует, что происходит, когда N стремится к бесконечности.

***

При сравнении двух списков на равенство, класс сложности должен быть O(N), как указано в таблице выше. Однако в реальности это значение нужно умножить на O==(…), где O==(…) это класс сложности для операции сравнения (==) двух значений в списке. Если мы работаем с целыми числами (int), то сложность сравнения будет равна O(1), если со строками (string), то в худшем случае мы получим O(len(string)).

Эта проблема возникает при любом сравнении, однако мы в дальнейших расчетах будем предполагать, что эта операция имеет сложность O(1) – например, для чисел и строк малой/фиксированной длины.

Составные классы сложности

Разобравшись со сложностью отдельных операций мы переходим к их комбинированию.

Закон сложения для O-нотации

O(f(n))+O(g(n))=O(f(n)+g(n))

При сложении двух классов сложности складываются функции этих классов. В конечном счете, O(f(n) + g(n)) приводит нас к большему из двух исходных классов – так как меньший член выражения просто отбрасывается.

Таким образом,

O(N)+O(log⁡N)=O(N+log⁡N)=O(N)

так какN растет быстрее, чем log N:

limx→∞log⁡NN=0

Это правило позволяет вычислить класс сложности для последовательности операций. Например, сначала мы выполняем выражение со сложностью O(f(n)), а следом за ним – O(g(n)). Тогда выполнение обоих выражений (одно за другим) будет иметь сложность O(f(n)) + O(g(n)), то есть O(f(n) + g(n)).

Пример

Вызов функции f(...) имеет сложность O(N), а вызов g(...)O (N * log N). Вызываем эти функции друг за другом:

        f(...)
g(...)
    

Сложность этого действия будет равна:

O(N)+O(Nlog⁡N)=O(N+Nlog⁡N)=O(Nlog⁡N)

Если мы вызовем функцию f(...) дважды:

        f(...)
f(...)
    

то получим:

O(N)+O(N)=O(N+N)=O(2N)=O(N)

Константа 2 в вычислениях отбрасывается.

Условия

Отдельно разберем исполнение условий (if). Сначала выполняется само условие, а затем один из блоков (if или else).

        if test:
  block 1
else:
  block 2
    

Предположим, что вычисление условия test имеет сложность O(T), блока block 1O(B1), а блока block 2O(B2).

Тогда сложность всего кода будет равна:

O(T)+max(O(B1),O(B2))

test выполняется всегда, а один из блоков следом за ним – то есть последовательно. В худшем случае будет выполнен блок с наивысшей сложностью.

Подставим реальные значения:

  • testO(N),
  • block 1O(N2),
  • block 2O(N).

и вычислим сложность кода:

O(N)+max(O(N2),O(N))=
O(N)+O(N2)=O(N+N2)=O(N2)

Если бы операция test имела класс сложности O(N3), то общая сложность кода составила бы O(N3).

O(N3)+max(O(N2),O(N))=
O(N3)+O(N2)=O(N3+N2)=O(N3)

Фактически, общий класс сложности для if-условий можно записать еще проще:

O(T)+O(B1)+O(B2)

Для первого примера в этом случае получим:

O(N)+O(N2)+O(N)=O(N2)

В O-нотации мы всегда отбрасываем менее значимые элементы – по сути это аналогично работе функции max. Запись с max лучше отражает суть вычисления, но вы можете выбрать любой удобный для вас вариант.

Закон умножения для O-нотации

O(f(n))∗O(g(n))=O(f(n)∗g(n))

Если мы повторяем O(N) раз некоторый процесс с классом сложности O(f(N)), то результирующий класс сложности будет равен:

O(N)×O(f(N))=O(N×f(N))

Предположим, некоторая функция f(...) имеет класс сложности O(N2). Выполним ее в цикле N раз:

        for i in range(N):
    f(...)
    

Сложность этого кода будет равна:

O(N)×O(N2)=O(N×N2)=O(N3)

Это правило позволяет вычислять класс сложности для выполнения некоторого повторяющегося несколько раз выражения. Необходимо умножить класс сложности количества повторений на класс сложности самого выражения.

Статический анализ на практике

Возьмем три разные функции, которые решают одну и ту же задачу – определяют, состоит ли список из уникальных значений (не имеет дубликатов). Для каждой функции вычислим класс сложности.

Для всех трех примеров размер списка обозначим как N, а сложность операции сравнения элементов примем за O(1).

Алгоритм 1

Список уникален, если каждое его значение не встречается ни в одном последующем индексе. Для значения alist[i] последующим фрагментом списка будет срез alist[i+1:].

        def is_unique1 (alist : [int]) -> bool:
  for i in range(len(alist)):             # 1
    if alist[i] in alist[i+1:]:           # 2
      return False                        # 3
  return True                             # 4
    

Определим сложность для каждой строки метода:

  1. O(N) – для каждого индекса. Создание объекта range требует выполнения трех последовательных операций: вычисления аргументов, передачу их в __init__ и выполнение тела __init__. Две последние имеют класс сложности O(1). Сложность len(alist) также O(1), поэтому общая сложность выражения range(len(alist)) – O(1) + O(1) + O(1) = O(1).
  2. O(N) – получение индекса + сложение + создание среза + проверка in: O(1) + O(1) + O(N) + O(N) = O(N)
  3. O(1) – в худшем случае никогда не выполняется, можно проигнорировать.
  4. O(1) – в худшем случае всегда выполняется.

Таким образом, класс сложности целой функции is_unique1 равен:

O(N)×O(N)+O(1)=O(N2)

Если размер списка увеличится вдвое, то выполнение функции займет в 4 раза больше времени.

***

Возможно, вы хотели написать так:

O(N)×(O(N)+O(1))+O(1)

ведь выражение if cостоит из вычисления самого условия (O(N)) и блока return False (O(1)). Но в худшем случае этот блок никогда не будет выполнен и цикл продолжится, поэтому мы не включаем его в формулу. Но даже если добавить его, то ничего не изменится, так как O(N) + O(1) – это по-прежнему O(N).

Кроме того, в худшем случае вычисляемый срез списка – это alist[1:]. Его сложность – O(N-1) = O(N). Однако, когда i == len(alist) этот срез будет пуст. Средний срез содержит N/2 значений, что по-прежнему даем нам сложность O(N).

***

Вместо срезов можно использовать вложенный цикл. Сложность функции при этом не изменится.

        def is_unique1 (alist : [int]) ->bool:
  for i in range(len(alist)):          # O(N)
    for j in range(i+1, len(alist)):   # O(N)
      if alist[i] == alist[j]          # O(1)
        return False                   # O(1)
 return True                           # O(1)
    

Класс сложности целой функции тот же:

O(N)×O(N)×O(1)+O(1)=O(N2)

Алгоритм 2

Список уникален, если после его сортировки рядом не находятся одинаковые значения.

Сначала мы копируем список, чтобы не изменять исходную структуру сортировкой – функции обычно не должны влиять на входящие параметры.

        def is_unique2 (alist : [int]) -> bool:
  copy = list(alist)             # 1
  copy.sort()                    # 2
  for i in range(len(alist)-1):  # 3
    if copy[i] == copy[i+1]:     # 4
      return False               # 5
  return True                    # 6
    

Сложность по строчкам:

  1. O(N).
  2. O(N log N) – для быстрой сортировки.
  3. O(N) – на самом деле N-1, но это то же самое. Операции получения размера списка и вычитания имеют сложность O(1).
  4. O(1) – сложение, две операции получения элемента по индексу и сравнение – все со сложностью O(1).
  5. O(1) – в худшем случае никогда не выполняется.
  6. O(1) – в худшем случае всегда выполняется.

Общий класс сложности функции is_unique2:

O(N)+O(N×log⁡N)+O(N)×O(1)+O(1)=
O(N+Nlog⁡N+O(N×1)+1)=
O(N+Nlog⁡N+N+1)=O(Nlog⁡N+2N+1)=O(Nlog⁡N)

Сложность этой реализации меньше, чем is_unique1. Для больших значений N is_unique2 будет выполняться значительно быстрее.

Наибольшую сложность имеет операция сортировки – она занимает больше всего времени. При удвоении размера списка именно сортировка займет больше половины добавившегося времени выполнения.

Класс сложности O(N log N) хуже, чем O(N), но уже значительно лучше, чем O(N2).

Фактически, в код метода можно внести одно упрощение:

        # было
copy = list(alist)    # O(N)
copy.sort()           # O(N log N)

# стало
copy = sorted(alist)  # O(N log N)
    

Функция sorted создает список с теми же значениями и возвращает его отсортированную версию. Поэтому нам не требуется явно создавать копию.

Это изменение ускорит выполнение кода, но не повлияет на его сложность, так как O(N + N log N) = O(N log N). Ускорение – это всегда хорошо, но намного важнее найти алгоритм с минимальной сложностью.

Нужно отметить, что is_unique2 работает только в том случае, если все значения в списке сравнимы между собой (для сортировки используется оператор сравнения <). Если список заполнен одновременно строками и числами, ничего не получится. В то же время is_unique1 использует только оператор ==, который может сравнивать значения разных типов без выбрасывания исключений.

Алгоритм 3

Список уникален, если при превращении в множество (set) его размер не изменяется.

        def is_unique3 (alist : [int]) -> bool:
  aset = set(alist)               # O(N)
  return len(aset) == len(alist)  # O(1)
    

Рассчитать класс сложности для всей функции очень просто:

O(N)+O(1)=O(N+1)=O(N)

Таким образом, третья реализация оказалась самой эффективной из всех с линейным временем выполнения. При увеличении размера списка в два раза, время выполнения функции is_unique3 увеличится всего в два раза.

Тело функции можно записать в одну строчку:

        return len(set(alist)) == len(alist)
    

Сложность при этом не изменится.

В отличие от is_unique2, эта реализация может работать и со смешанными списками (числа и строки). В то же время требуется, чтобы все значения были хешируемыми/неизменяемыми. Например, is_unique3 не будет работать для списка списков.

***

Одну проблему можно решить разными способами, из которых одни могут быть эффективнее других. Статический анализ (без запуска кода) позволяет оценить сложность выполнения алгоритмов и функций. Это имеет большое значение для работы с большими наборами данных – чем больше размер входных данных, тем больше выигрыш.

В то же время для небольших объемов данных классы сложности неэффективны. Чтобы найти лучший алгоритм в этом случае, необходимо учитывать константы и термины низшего порядка. Также хорошо работает эмпирический, или динамический, анализ.

Кроме того, при анализе важно учитывать дополнительные ограничения реализации (например, типы данных).

Приоритетные очереди

Рассмотрим еще один важный пример зависимости вычислительной сложности от реализации алгоритма – приоритетные очереди.

Этот тип данных поддерживает две операции:

  • добавление значения;
  • извлечение значения с самым высоким приоритетом из оставшихся.

Разные реализации приоритетных очередей имеют разные классы сложности этих операций:

add remove
Реализация 1 O(1) O(N)
Реализация 2 O(N) O(1)
Реализация 3 O(log N) O(log N)

Реализация 1

Новое значение добавляется в конец списка (list) или в начала связного списка (linked list) – O(1).

Чтобы найти приоритетное значение для удаления осуществляется поиск по списку – O(N).

Легко добавить, но трудно удалить.

Реализация 2

Для нового значения определяется правильное место – для этого перебираются элементы списка (или связного списка) – O(N).

Зато самое приоритетное значение всегда находится в конце списка (или в начале связного списка) – O(1).

Легко удалить, но трудно добавить.

Реализация 3

Используется двоичная куча, которая позволяет реализовать обе операции со “средней” сложностью O(log N), что для больших значений ближе к O(1), чем к O(N).

Теперь проведем анализ этих реализаций на реальных задачах.

Сортировка

Чтобы отсортировать N значений с помощью приоритетной очереди, нужно сначала добавить все значения в очередь, а затем удалить их все.

Реализация 1

N×O(1)+N×O(N)=O(N)+O(N2)=O(N2)

Реализация 2

N×O(N)+N×O(1)=O(N2)+O(N)=O(N2)

Реализация 3

N×O(log⁡N)+N×O(log⁡N)=
O(Nlog⁡N)+O(Nlog⁡N)=O(Nlog⁡N)

Примечание: N * O(…) – это то же самое, что и O(N) * O(…).

Первая и вторая реализации выполняют одну операцию быстро, а другую медленно. В итоге общий класс сложности определяет самая медленная операция.

Третья реализация оказывается быстрее всех, так как ее среднее время O(N log N) ближе к O(1), чем к O(N).

10 максимальных значений

Теперь найдем с помощью приоритетной очереди 10 максимальных значений. Для этого в очередь помещаются N элементов, а извлекаются только 10.

Реализация 1

N×O(1)+10×O(N)=O(N)+O(N)=O(N)

Реализация 2

N×O(N)+10×O(1)=O(N2)+O(1)=O(N2)

Реализация 3

N×O(log⁡N)+10×O(log⁡N)=
O(Nlog⁡N)+O(log⁡N)=O(Nlog⁡N)

Теперь первая реализация оказывается самой эффективной, так как операция добавления элемента у нее очень дешевая по времени.

***

Мораль этого примера заключается в том, что иногда не существует “самой лучшей реализации”. В зависимости от задачи оптимальными могут быть разные варианты.

А чтобы найти лучшее решение, важно понимать, что такое вычислительная сложность и как ее определить 🙂

09
Сен
2020

Краткое описание десяти основных алгоритмов на графах с визуализацией графов и примерами использования алгоритмов на практике.

Графы стали мощным средством моделирования и представ…

18
Авг
2020

Какой самый сложный алгоритм вы использовали в своей работе — рассказывают эксперты

Помимо привычных задач порой попадаются алгоритмы, которые надолго запоминаешь. Спросили у экспертов о таких алгоритмах.
— Читать дальше «Какой самый сложный алгоритм вы использовали в своей работе — рассказывают эксперты»