P-split formulation for neural networks

No Thumbnail Available

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.

Date

2024-06-26

Department

Major/Subject

Matematiikka ja systeemitieteet

Mcode

SCI3029

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

en

Pages

19

Series

Abstract

Deep neural networks (DNNs) have become highly popular machine learning (ML) models. Multiple factors have accelerated their rise in popularity. First of all, DNNs have proven to be powerful tools in various tasks across a variety of fields, including natural language processing, which is currently in high demand. In addition, the structure and functionality of the neural networks are inspired by the human brain, thus making them naturally intriguing for people. This popularity has led to extensive research and development of the DNNs. The mathematical optimization of trained neural networks is an area of research that has provoked significant interest due to its promising applications. However, as a result of their non-linear nature, DNNs are challenging to optimize. Therefore, different mathematical formulations that exactly model the structure and behavior of DNNs are employed. Beyond the classic use of the 0-1 mixed-integer linear programming (0-1 MILP) formulation, a new and promising class of formulations, known as the P-split formulations, has been proposed. P-split formulations make use of disjunctive programming, which is the combination of linear programming with disjunctive constraints arising from the need to model logical conditions. This thesis expands the research focusing on P-split formulations by conducting a series of computational experiments to assess the efficiency of P-split formulations in optimizing neural networks with a more general architecture. In the computational experiments, the solution times and linear relaxations of the P-split formulations are compared against those of the classic 0-1 MILP formulation. The results show that the P-split formulations do not consistently offer computational efficiency advantages over the 0-1 MILP formulation. However, they provide tighter relaxations, demonstrating the potential of the formulations. These findings suggest that further research is needed to develop better-performing formulations for a broader range of network structures.

Syväoppivat neuroverkot ovat saavuttaneet suuren suosion koneoppimismalleista kiinnostuneiden keskuudessa. Tämän suuren suosion kehittymiseen ovat vaikuttaneet lukuisat eri tekijät. Syväoppivat neuroverkot ovat ensinnäkin osoittaneet tehokkuutensa monipuolisissa käyttökohteissa useilla eri aloilla, kuten luonnollisen kielen käsittelyjärjestelmissä, joiden kysyntä on erityisen suurta tällä hetkellä. Lisäksi ihmisen luonnollista mielenkiintoa neuroverkoja kohtaan lisää se, että niiden rakenne ja toiminnallisuus pohjautuvat ihmisaivoihin. Tämä edellä kuvattu suuri suosio on johtanut neuroverkkojen laajamittaiseen tutkimiseen ja kehittämiseen. Koulutettujen neuroverkkojen matemaattinen optimointi on tieteenala, joka on herättänyt erityistä mielenkiintoa sen lupaavien sovelluskohteiden vuoksi. Neuroverkkojen epälineaarisen rakenteen takia niiden optimointi on kuitenkin haastavaa. Tämän vuoksi optimoinnissa usein käytetään neuroverkkojen sijaan matemaattisia malleja, jotka kuvaavat tarkasti niiden rakennetta ja käyttäytymistä. Klassisen lineaarisen sekalukuoptimointimallin lisäksi on kehitetty uusi ja lupaava kategoria matemaattisia malleja nimeltään P-split-mallit. P-split-mallit hyödyntävät disjunktiivista ohjelmointia (engl. disjunctive programming). Disjunktiivisessa ohjelmoinnissa mallinnetaan rajoitteita, jotka johtuvat tarpeesta mallintaa loogisia ehtoja, kuten "joko-tai". Tämä kandidaatintyö pyrkii jatkamaan P-split-malleihin kohdistuvaa tutkimustyötä tarkastelemalla niiden tehokkuutta rakenteeltaan yleisluontoisempien neuroverkkojen optimoinnissa. Laskennallisten tutkimusten perusteella selvitettiin, kuinka P-split-mallit vertautuvat klassiseen lineaariseen sekalukuoptimointimalliin tutkittaessa mallien pohjalta luotujen optimointiongelmien ratkaisuaikoja sekä lineaarisia relaksaatioita (engl. linear relaxations). Tuloksista voitiin huomata, että P-split-mallit eivät ole selvästi klassista mallia nopeampia ratkaista. Toisaalta P-split-mallit osoittivat potentiaalinsa tuottamalla tiukempia lineaarisia relaksaatiota. Näiden tutkimustulosten perusteella voidaan siis todeta, että yhä on syytä jatkaa tutkimusta, jossa tarkoituksena on löytää laskennallisesti tehokkaampia ja toimivampia malleja neuroverkkojen optimointiin.

Description

Supervisor

Oliveira, Fabricio

Thesis advisor

Liu, Yu

Keywords

deep neural networks, mathematical optimization, mixed-integer linear programming, mixed-integer formulations, disjunctive programming, disjunctive constraints

Other note

Citation