Skip to content

Archive

Archive for Listopad, 2017

data from kaggle

Data were obtained from kaggle: https://www.kaggle.com/gregorut/videogamesales. The dataset contains a list of video games with sales greater than 100,000 copies. It was generated by a scrape of vgchartz.com. Fields include:

  • Rank – Ranking of overall sales
  • Name – The games name
  • Platform – Platform of the games release (i.e. PC,PS4, etc.)
  • Year – Year of the game’s release
  • Genre – Genre of the game
  • Publisher – Publisher of the game
  • NA_Sales – Sales in North America (in millions)
  • EU_Sales – Sales in Europe (in millions)
  • JP_Sales – Sales in Japan (in millions)
  • Other_Sales – Sales in the rest of the world (in millions)
  • Global_Sales – Total worldwide sales.

Global sales

Global Sales by Year_trends

Looking at how the total global sales differed by years, it can be noted that since 1980 sales were continously increasing. But  huge decrease can be observed in last 7 years.

Sales by regions

Global Sales by Region

Looking at the sales by regions, we can see that North America region had the biggest contribution to global sales – almost 50%. NA and EU regions together had over 75%  contribution to global sales.

Sales by regions timeseries

Here we can see how sales in the regions varied over time. In 1995 North America became the biggest market. In 2008 the sales began to decrease in all regions. The biggest relative fall was in North America.

Number of releases

Number of releases by Year

Here we can see how the number of new games releases was changing. It kept growing up to the 2009, when it started to drop rapidly.

Who released the most?

This image shows top publishers by the number of releases. Two companies that made the most releases were: Electronic Arts and Activision.

Releases by Years

Top Publishers by Releases by Years

Here we can see how the releases looked in the time. The top publisher – Electronic Arts – entered the market in 1992 and made the most releases in years: 2005-2009.

Who made the sales?

Top Publishers by Total Global Sales

Electronic Arts and Activision made most releases, but looking at the sales we can see that Nintendo made the best Total Global Sales. Electronic Arts and Activision are right behing Nintendo.

How did the sales look like?

Top Publishers by Global Sales by Years

This image shows how did the sales look in time for different publishers.

Platforms

Releases by Platforms

Here we can see the number of releases for different platforms. Two top platforms were DS and PS2.

Time marks of release dates for all platforms

Platforms by Years legend

This image shows how the distribution of releases for different platform look like. Most releases for DS were in years 2004-2014, and for PS2 in years: 2000-2011. Typical release time window for main platforms lasts ca 10 years. PC had the largest release window.

Number of releases for platforms

Genres by Platforms

The number of releases in different genres for platforms. The top 5 platforms had the most releases in Action category. The most releases were made for PS2 in Sports category.

Number of releases by genres

Number of Releases by Genres

Here we can see number of releases by genres. Action Games had 20% contribution to total number of games released. Just Action and Sport games were 1/3 of all the released games.

Releases by Genres by Years

This plot shows the moving average of releases in years. In 2004 Action games detronized Sport games. Sport games had the biggest relative fall (since 2010). Action games were released the most, but after 2011 also falling.

Global sales by genres

Global Sales by Genres

Action games are top selling category.

Global Sales by Genres by Years

This plot shows the moving average of sales over time. The biggest falls can be observed for two top genres: Action and Sports.

Sales by genres in regions

Sales by Genres by Areas

Sales by Genres by Areas tab

In Japan the most popular genre was Role-Playing (Pokemon series?). In other regions the most popular genre was Action.

Top games by global sales

Top Games by Global Sells

This image shows the best selling games. The top one is Wii Sports. GTA 5 is in the second place.

Top games by global sales in regions

Top Games by Sells

Looking on sales by regions we can see that top game – Wii Sports sales were mostly in North America. GTA 5 was almost 50:50 in EU/NA. In Japan: Pokemon games significantly outperformed other titles in sales.

Final notes

  • Over last few years there is decrease in sales and in numer of releases
  • NA and EU regions had over 75% contribution to global sales
  • Electronic Arts and Activision were the top most releasing publishers
  • Top most selling publisher was Nintendo
  • Most popular genres were: Action and Sports (34.5% of total sales)
  • Wii Sports, GTA 5 and Super Mario Bros and were best selling games

Termin Multilayer Kernel Machines (MKMs) został wprowadzony w 2012 roku w pracy doktorskiej Youngmin Cho pisanej pod kierunkiem Prof. Lawrenca Saul (1). Autor zaproponował nowy model hierarchiczny oparty o przekształcenia jądrowe, czerpiący z wcześniejszych badań nad rodziną jąder arc-cosinusowych (2). Ideą badań i rozwoju MKMs była chęć obejścia słabości maszyn wektorów nośnych (ang. Support Wektor Machines, SVM) oraz wykorzystania zalet systemów głębokich. Realizacja MKMs bazowała na koncepcji połączenia technik nienadzorowanej redukcji wymiarowości i nadzorowanego wyboru cech z  wielowarstwowymi jądrami arc-cosinusowymi. Indywidualne kroki w tej procedurze korzystają z dobrze znanych i szeroko stosowanych metod, jednak ich połączenie w zaproponowanej metodzie tworzenia MKMs było nowatorskie.

 

Zasada działania i uczenia się Multilayer Kernel Machines

Multilayer Kernel Machines są trenowane przy wykorzystaniu kombinacji metod uczenia nadzorowanego i nienadzorowanego. U podstaw ich działania leży rekursywnie przeprowadzana iteracja trzech procesów:

  • „trik jądrowy” polegający na nieliniowej transformacji (najlepiej przez jądra arc-cosinusowe)
  • nienadzorowaną redukcję wymiaru poprzez jądrową analizę składowych głównych Kernel Principal Component Analysis (KPCA)
  • oraz nadzorowany wybór cech.

Cykl ten jest wielokrotnie powtarzany w celu skonstruowania MKM.


Z pracy: (1)

Powyższy schemat przedstawia podstawową koncepcję konstrukcji Multilayer Kernel Machines. Dane wejściowe X są filtrowane w procesie nadzorowanej selekcji cech w ten sposób, aby zawierały wyłącznie cechy powiązane z informacją klasyfikowaną. Otrzymane dane X’ są poddawane przetwarzaniu przez jądra arc-cosinusowe tworzące nieskończenie wymiarową reprezentację Φ(X’). W kolejnym kroku następuje nienadzorowana redukcja wymiarowości Φ(X’) w przestrzeni cech i otrzymywana jest skończeniewymiarowa reprezentacja Ψ(X’). Następnie Ψ(X’) podawane jest na wejście i cały cykl powtarzany jest wielokrotnie np. L razy w celu utworzenia L –warstwowej MKM. Na samym końcu procedury, cechy ostatniej warstwy podawane są na wejście jakiegoś klasyfikatora (jak np. k-NN lub SVM) w celu podjęcia końcowej decyzji.

Procedurę uczenia Multilayer Kernel Machines opisuje następujący pseudokod:

 multilayer kernel machine learning pseudocode

 

Nienadzorowana redukcja wymiarowości – Kernel Principal Components Analysis (KPCA)

W Multilayer Kernel Machines głębokie uczenie realizowane jest przez iteracyjne powtarzanie na kolejnych warstwach procedury KPCA, przedstawionej w 1998 w pracy (3). Dane wyjściowe (cechy w postaci składowych głównych) z KPCA z jednej warstwy stanowią wejście do KPCA w warstwie następnej. Składowe te nie są jednak przenoszone bezpośrednio. Usuwane są składowe, które zostały uznane za nieinformacyjne, czyli niezwiązane z informacją wpływającą na klasyfikację. W zasadzie wszystkie nieliniowe jądra mogą zostać użyte przy analizie składowych głównych w MKMs, ale rdzenie arc-cosinusowe wydają się być najlepszym wyborem ponieważ odzwierciedlają obliczenia w wielkich sieciach neuronowych.

Analiza składowych głównych (PCA) jest ortogonalną transformacją systemu współrzędnych opisującego dane. Często wykonywana jest poprzez rozwiązanie równania znajdującego wartości i wektory własne, a czasami przy wykorzystaniu algorytmów iteracyjnych. W przypadku dużej (lub nieskończonej jak w przypadku MKM) wymiarowości danych rozwiązaniem może być wykorzystanie jąder w metodzie Kernel Principal Components Analysis KPCA.

KPCA przebiega zgodnie z następującym algorytmem. Na początku utworzona zostaje macierz Kij=(k(xi,xj))ij. Następnie rozwiązywane jest równanie własne poprzez diagonalizację macierzy K i normalizowane są współczynniki rozwinięcia αn wektorów własnych poprzez wiąz: λnn·αn )=1, gdzie λ oznacza wartości własne macierzy K. W celu wydobycia składowych głównych (odpowiednich dla jądra k) wektora x, obliczane są jego rzuty na wektory własne:

KPCA

W przypadku jąder arc-cosinusowych procedura ta dokładnie odpowiada standardowej PCA w przestrzeni cech, bez konieczności wykonywania obliczeń w tej przestrzeni.

 

Wybór cech

W Multilayer Kernel Machines warstwy są uczone poprzez połączenie nadzorowanej metody wyboru cech i nienadzorowanej metody KPCA. Wybór cech ma na celu odrzucenie cech nieinformacyjnych na poziomie każdej warstwy (włączając w to także oryginalne dane wejściowe). Pozwala to skoncentrować nienadzorowane uczenie MKMs na składowych rzeczywiście zawierających informacje o oznaczeniach klas. Ograniczenie cech w każdej warstwie odbywa się w dwóch etapach: poprzez oszacowanie dla cech ich informacji wzajemnej, oraz ich okrojenie w oparciu o walidację krzyżową. Pierwszy etap realizowany jest przez dyskretyzację cech i konstrukcję histogramów warunkowego i marginalnego rozkładu dyskretnych wartości dla klas, a następnie w oparciu o te rozkłady estymowana jest dla każdej cechy informacja wzajemna z oznaczeniem klasy oraz następuje posortowanie cech zgodnie z wartością tego oszacowania (4). W drugim kroku uwzględniając wyłącznie w pierwszych cech zgodnie z tym uporządkowaniem, obliczane są wskaźniki błędu klasyfikatora k-NN (k-najbliższych sąsiadów) w oparciu o odległość Euklidesową w przestrzeni cech. Wartości błędu obliczane są na losowym zestawie walidacyjnym próbek, dla różnych wartości k i w i zapamiętywane są wartości optymalne. Optymalna wartość w określa liczbę cech o zawartości informacyjnej która będzie przekazana do następnej warstwy. Z tego wynika, że wartość w określa szerokość warstwy.

 

Klasyfikacja – nauka metryki

W pracy (1) cechy na wyjściu ostatniej warstwy klasyfikowane były przy wykorzystaniu odmiany klasyfikatora k-NN. Autor użył klasyfikacji Large Margin Nearest Neighbor (LMNN) przedstawionej w pracy (5), a jako miarę odległości wykorzystał metrykę Mahalanobisa. Odległość Mahalanobisa jest zgodnie z formalizmem matematycznym pseudometryką ponieważ spełnia wszystkie właściwości metryk z wyjątkiem warunku rozróżnialności: D(xi ,xj )=0 xi=xj. Odległość Mahalonobisa opisuje się wzorem:

Mahalanobis distance

gdzie oryginalnie macierz M jest odwrotnością macierzy kowariancji.

 

Matematyczne podstawy rdzeni arc-cosinusowych

W pracy (2) opublikowanej jako artykuł z konferencji Neural Information Processing Systems 2009, Youngmin Cho i Lawrence K. Saul zaproponowali nową rodzinę funkcji jądrowych (rdzeni) odzwierciedlających obliczenia w wielkich sieciach neuronowych oraz przedstawili metodę uczenia Multilayer Kernel Machines przy wykorzystaniu tych funkcji. Praca zawierała część materiału z pracy doktorskiej Youngmin Cho pisanej pod kierunkiem Prof. Lawrenca Saul (1).

Autorzy zaprezentowali rodzinę funkcji jądrowych (rdzeni) pozwalających na obliczenie podobieństwa dwóch wektorów x, y  Rd. Reprezentacja funkcji w postaci całkowej wygląda następująco:

kernel function via the integral representation

Heaviside step function

Analityczne oszacowanie tej całki (2) pozwala na zapis funkcji w postaci:

kernel function

czyli iloczynu składowej zależnej od modułów obu wektorów, oraz składowej Jn(θ) zależnej od kąta pomiędzy nimi w sposób:

 angular dependence - J of theta

gdzie θ oznacza kąt pomiędzy wektorami x i y:

theta angle between inputs: x and y

Zaproponowane rdzenie są nazywane zgodnie z sugestią autorów rdzeniami arcus-cosinusowymi (ang. Arc-cosine kernels) ze względu na postać rdzenia zerowego rzędu:

zeroth order kernel is arc-cosine kernel

Rdzenie wyższych rzędów z tej rodziny mają bardziej skomplikowaną składową opisującą zależność kątową Jn(θ) np.:

J1(θ)=sinθ + (π − θ)cosθ  lub J2(θ)=3sinθ cosθ + (π − θ)(1 + 2cos2 θ).

Dodatkowo, ponieważ iloczyn skalarny wektorów wyjściowych f(x) i f(y) z jednowarstwowej sieci o m jednostkach wyjściowych i funkcji aktywacji postaci gn(z) = Θ(z)zn, rzędu n, opisuje się równaniem:

inner product between different outputs of the network

gdzie, wi oznacza i-ty rząd macierzy wag, a x i y to wektory cech na wejściu, to z tego powodu, można jądra arc-cosinusowe zgodnie z ich reprezentacją w formie całkowej, interpretować jako iloczyn skalarny wektorów cech przepuszczonych przez nieskończoną (w granicy m→∞) jednowarstwową sieć progową. Jest to cecha, która odróżnia jądra arc-cosinusowe od jąder wielomianowych czy RBF (gaussowskich). Rdzenie arc-cosinusowe posiadają jeszcze jedną ważną cechę, mianowicie nie mają żadnych parametrów wymagających określenia (np. na zbiorze walidacyjnym) takich jak np. szerokość w rdzeniach RBF.

Rdzenie można rozumieć jako nieliniowe mapowanie wejścia x do wektora cech Φ(x). Jednocześnie rdzeń jest iloczynem skalarnym w wytworzonej przestrzeni cech: k(x,y) = Φ(x)·Φ(y). Skoro ta funkcja odzwierciedla działanie jednowarstwowej sieci, to funkcja postaci:

inner product after ` successive applications of the nonlinear mapping

odzwierciedla przetwarzanie przez wielowarstwową sieć progową. Dla rdzeni arc-cosinusowych, zgodnie z analityczną postacią oszacowania całki, będzie wyglądała następująco:

the inductive step

gdzie θn(l) jest kątem pomiędzy projekcjami x i y do przestrzeni cech wytworzonej przez l-krotne złożenie. Jest to równanie rekurencyjne o podstawie (l=0) postaci:

basis of recursion

jednak zgodnie z (1) łatwe do wyliczenia. W równaniu rekurencyjnym, autorzy dla uproszczenia przyjęli ten sam rząd n (liczbę jednostek) w każdej warstwie, jednak w praktyce można stosować różne rzędy rdzeni dla różnych warstw.

 Multilayer neural networks modeled by the composition of arc-cosine kernels

Rys. z pracy (1) pokazujący modelowanie wielowarstwowej sieci neuronowej poprzez składanie rdzeni arc‑cosinusowych.

To, że składanie jąder arc-cosinusowych prowadzi do funkcji nie będącej członkiem oryginalnej rodziny, także jest specyficzną cechą tych funkcji odróżniającą je od innych rdzeni. Np. składanie rdzeni wielomianowych prowadzi do utworzenia nowego rdzenia wielomianowego wyższego rzędu, a w składanie jąder RBF spowoduje powstanie jądra RBF, ale o innej wariancji.

W pracy (1) autorzy rozszerzyli koncepcję składania jąder arc-cosinusowych o mnożenie i uśrednianie.

Multilayer neural networks modeled by the kernel multiplication

Wielowarstwowa sieć neuronowa modelowana przez mnożenie jąder arc-cosinusowych. Φn,m oznacza m-tą cechę wprowadzaną przez jądro arc-cosinusowe stopnia n. Różne kolory w warstwach pośrednich oznaczają różne nieliniowe odwzorowania generowane przez odpowiadające im jądra.

Multilayer neural networks modeled by the kernel averaging

Wielowarstwowa sieć neuronowa modelowana przez uśrednianie. Odwzorowania nieliniowe w różnych warstwach wielowarstwowego jądra (na górze) są łączone jako reprezentacja  pojedynczej cechy (na dole) przez uśrednianie rdzeni.

 

 

Jądra arc-cosinusowe, a Multilayer Kernel Machines

Powstanie Multilayer Kernel Machines było zainspirowane badaniami nad rdzeniami arc-cosinusowymi. Poniższy schemat porównuje dwa systemy: SVM z jądrami arc-cosinusowymi i MKMs.

Support vector machines vs multilayer kernel machines

Oba modele wykorzystują rdzenie arc-cosinusowe, w każdej warstwie do przetwarzania danych na wejściu, które są następnie przekazywane do następnej warstwy, aż do końcowej reprezentacji. W przypadku wielowymiarowych jąder arc-cosinusowych końcowe cechy są podawane na wejście klasyfikatora SVM. Ale w przypadku MKMs, miejsce mają dodatkowe operacje modyfikujące cechy na poziomie każdej warstwy. Przede wszystkim MKMs redukują wymiarowość reprezentacji jądrowej, co powoduje zmniejszenie szumu i bardziej zwartą reprezentację danych. Zmiana nieskończeniewymiarowej reprezentacji w skończeniewymiarową ma dwie zalety.

  • Po pierwsze, pozwala na ocenę związku cech z informacją dotyczącą klasyfikacji, dzięki czemu część cech może być usunięta. Na powyższym schemacie usuwanie cech symbolizowane jest przez okręgi rysowane przerywaną linią. W nieskończeniewymiarowej przestrzeni jądrowej (jak w przypadku modelu „rdzenie arc-cosinusowe + SVM”, po lewej stronie) taka ocena nie byłaby możliwa.
  • Po drugie, w przypadku MKMs na ostatniej warstwie można wykorzystać jakikolwiek klasyfikator, ponieważ dzięki redukcji wymiarowości, dane nie są wyrażone w przestrzeni jądrowej cech.

 

 

Podsumowanie

Multilayer Kernel Machines są to systemy wykorzystujące architekturę głęboką (wielowarstwową) oraz przekształcenia jądrowe do przestrzeni cech przy wykorzystaniu rdzeni arc-cosinusowych. Uczenie warstw ukrytych MKMs odbywa się dzięki połączeniu w każdej warstwie (kroku iteracji) nienadzorowanej metody redukcji wymiarowości (oryginalnie KPCA) oraz nadzorowanej metody wyboru cech (składowych o zawartości informacyjnej). Na wyjściu MKMs może znajdować się jeden z powszechnie stosowanych klasyfikatorów (oryginalnie LMNN z metryką Mahalanobisa).

Multilayer Kernel Machines zostały zainspirowane wielowarstwowymi jądrami arc-cosinusowymi. Badania nad MKMs, były motywowane tym, że architektura w postaci wielowarstwowych jąder arc-cosinusowych i klasyfikatora SVM na wyjściu, nie jest optymalna ponieważ  przekształcenia jądrowe w każdej warstwie mieszają cechy informacyjne z szumem.

W przypadku MKMs, dodanie w każdej warstwie redukcji wymiaru i selekcji wyłącznie cech informacyjnych pod kątem docelowej klasyfikacji, pozwala poddawać dalszemu przetwarzaniu przez kolejną warstwę, tylko wybrane cechy mające wkład w klasyfikację. Dzięki temu w każdej warstwie zachodzi jakby filtrowanie szumu (składowych nie związanych z problemem klasyfikacyjnym rozwiązywanym przez MKM).

Zgodnie z (6), badacze z Microsoftu  przedstawili prostszy sposób implementacji MKMs do rozumienia mowy (7), jednak w tym wpisie skoncentrowałem się na oryginalnej interpretacji definiującej MKMs w oparciu o rdzenie arc-cosinusowe.

 

Bibliografia

  1. Cho, Youngmin. Kernel Methods for Deep Learning. San Diego: University of California, 2012.
  2. Kernel Methods for Deep Learning. Youngmin Cho, Lawrence K. Saul. 2009. Neural Information Processing Systems. pp. 342-350.
  3. Schölkopf, Bernhard, Alexander Smola, and Klaus-Robert Müller. Nonlinear component analysis as a kernel eigenvalue problem. Neural computation 10.5. 1998, pp. 1299-1319.
  4. Guyon, I. and Elisseeff, A. An introduction to variable and feature selection. Journal of Machine Learning Research 3. 2003, pp. 1157–1182.
  5. Weinberger, K. Q. and Saul, L. K. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 10. 2009, pp. 207–244.
  6. Wikipedia. [Online] 2017. https://en.wikipedia.org/wiki/Deep_learning#Multilayer_kernel_machine.
  7. L. Deng, G. Tur, X. He, and D. Hakkani-Tur. Use of Kernel Deep Convex Networks and End-To-End Learning for Spoken Language Understanding. Proc. IEEE Workshop on Spoken Language Technologies. 2012.