國立虎尾科技大學 |

Algorithms and Complexity Results for Learning and Big Data.

紀錄類型:	書目-語言資料,手稿 : Monograph/item
正題名/作者:	Algorithms and Complexity Results for Learning and Big Data./
作者:	Lelkes, Adam D.
面頁冊數:	1 online resource (130 pages)
附註:	Source: Dissertation Abstracts International, Volume: 79-02(E), Section: B.
Contained By:	Dissertation Abstracts International79-02B(E).
標題:	Mathematics. -
電子資源:	click for full text (PQDT)
ISBN:	9780355279474

Algorithms and Complexity Results for Learning and Big Data.
Lelkes, Adam D.

Algorithms and Complexity Results for Learning and Big Data. - 1 online resource (130 pages)

Source: Dissertation Abstracts International, Volume: 79-02(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

This thesis focuses on problems in the theory and practice of machine learning and big data. We will explore the complexity-theoretic properties of MapReduce, one of the most ubiquitous distributed computing frameworks for big data, give new algorithms and prove computational hardness results for a model of clustering, and study fairness in machine learning applications.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355279474Subjects--Topical Terms:

527692
Mathematics.
Index Terms--Genre/Form:

554714
Electronic books.

Algorithms and Complexity Results for Learning and Big Data.
LDR:03708ntm a2200385Ki 4500 001 909060
005 20180419104825.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355279474
035 $a (MiAaPQ)AAI10662763
035 $a (MiAaPQ)0799vireo:244Lelkes
035 $a AAI10662763
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Lelkes, Adam D. $3 1179579
245 1 0 $a Algorithms and Complexity Results for Learning and Big Data.
264 0 $c 2017
300 $a 1 online resource (130 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 79-02(E), Section: B.
500 $a Advisers: Gyorgy Turan; Lev Reyzin.
502 $a Thesis (Ph.D.) $c University of Illinois at Chicago $d 2017.
504 $a Includes bibliographical references
520 $a This thesis focuses on problems in the theory and practice of machine learning and big data. We will explore the complexity-theoretic properties of MapReduce, one of the most ubiquitous distributed computing frameworks for big data, give new algorithms and prove computational hardness results for a model of clustering, and study fairness in machine learning applications.
520 $a In our study of MapReduce, we address some of the central questions that computational complexity theory asks about models of computation. After giving a detailed and precise formalization of MapReduce as a model of computation, based on the work of Karloff et al., we compare it to classical Turing machines, and show that languages which can be decided by a Turing machine using sublogarithmic space can also be decided by a constant-round MapReduce computation. In the second half of the chapter, we turn our attention to the question of whether an increased number of rounds or an increased amount of computation time per processor leads to strictly more computational power. We answer this question in the affirmative, proving a hierarchy theorem for MapReduce computations, conditioned on the Exponential Time Hypothesis.
520 $a We will also study an interactive model of clustering introduced by Balcan and Blum. In this framework of clustering, we give algorithms for clustering linear functionals and hyperplanes, and give computational hardness results that show that other concept classes, including deterministic finite automata, constant-depth threshold circuits, and Boolean formulas, are not possible to efficiently cluster if standard cryptographic assumptions hold.
520 $a Finally, we address the issue of fairness in machine learning. We propose a novel approach for modifying three popular machine learning algorithms, AdaBoost, logistic regression, and support vector machines, to eliminate bias against a protected group. We empirically compare our method to previous approaches in the literature as well as various baseline algorithms by evaluating them on various real-world datasets, and also give theoretical justification for its performance. We also propose a new measure of fairness for machine learning classifiers, and demonstrate that it can help distinguish between naive and more sophisticated approaches even in the cases when measuring error and bias is not sufficient.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Mathematics. $3 527692
650 4 $a Computer science. $3 573171
655 7 $a Electronic books. $2 local $3 554714
690 $a 0405
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of Illinois at Chicago. $b Mathematics, Statistics, and Computer Science. $3 1179580
773 0 $t Dissertation Abstracts International $g 79-02B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10662763 $z click for full text (PQDT)