서브메뉴
검색
Statistical Spectral Algorithms for Learning From Discrete Data
Statistical Spectral Algorithms for Learning From Discrete Data
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20250211151051
- ISBN
- 9798382830148
- DDC
- 004
- 서명/저자
- Statistical Spectral Algorithms for Learning From Discrete Data
- 발행사항
- [Sl] : University of Pennsylvania, 2024
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2024
- 형태사항
- 227 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 85-12, Section: A.
- 주기사항
- Advisor: Zhang, Anderson.
- 학위논문주기
- Thesis (Ph.D.)--University of Pennsylvania, 2024.
- 초록/해제
- 요약In recent decades, the interaction between computer systems and human users has generated a substantial volume of data. A significant portion of this data takes on a discrete form. Notable examples include choice data where a user selects an item from a list, binary response data where users vote either yes or no on an item, and ranking data where users provide a complete ordering of items based on preference. The development of efficient, robust, and accurate algorithms tailored to handle discrete data has become a focal point of interest across various applications, including recommendation systems, the social sciences, and psychometrics, among others.The present thesis contributes to this dynamic and evolving field. We focus on a class of efficient and powerful statistical algorithms known as spectral algorithms. We introduce novel, efficient and provably accurate spectral algorithms, and analyse the theoretical performance guarantees of classical spectral algorithms when applied to discrete data.For binary and ordered response data, we design novel spectral algorithms that are not only provably accurate but, under reasonable assumptions, also achieve the optimal sample complexity. This is particularly significant for the Rasch model, a fundamental model in psychometrics. Beyond binary response data, we introduce a generalized spectral algorithm designed to yield precise estimates under the Partial Credits model, which extends the Rasch model to encompass discrete ordered responses and ratings data. Our proposed spectral algorithms outperform other popular algorithms in terms of both accuracy and efficiency.In the domain of ranking data, we present novel spectral algorithms that address two well known problems in computer science. Firstly, we tackle the challenge of inference under a mixture of Plackett-Luce models by introducing a novel two-step algorithm. We propose an initialization algorithm based on spectral clustering, which offers provable guarantees. Furthermore, by recognizing the connection between the M-step of the EM algorithm and Markov chain analysis, we introduce a novel EM algorithm that surpasses the accuracy and time efficiency of previously proposed algorithms in the literature. Secondly, we delve into the permutation synchronization problem, which holds a broad range of applications in computer vision. We address a subtle yet critical limitation of previously proposed spectral algorithms, thereby introducing an innovative spectral algorithm designed specifically for this problem. The resulting algorithm enjoys information-theoretic optimal guarantee and performs significantly better than the previous approaches.
- 일반주제명
- Computer science
- 일반주제명
- Statistics
- 일반주제명
- Information science
- 키워드
- Discrete data
- 키워드
- Ranking
- 키워드
- Spectral method
- 기타저자
- University of Pennsylvania Computer and Information Science
- 기본자료저록
- Dissertations Abstracts International. 85-12A.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008250123s2024 us c eng d■001000017160625
■00520250211151051
■006m o d
■007cr#unu||||||||
■020 ▼a9798382830148
■035 ▼a(MiAaPQ)AAI31141413
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aNguyen, Manh Duc.
■24510▼aStatistical Spectral Algorithms for Learning From Discrete Data
■260 ▼a[Sl]▼bUniversity of Pennsylvania▼c2024
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2024
■300 ▼a227 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 85-12, Section: A.
■500 ▼aAdvisor: Zhang, Anderson.
■5021 ▼aThesis (Ph.D.)--University of Pennsylvania, 2024.
■520 ▼aIn recent decades, the interaction between computer systems and human users has generated a substantial volume of data. A significant portion of this data takes on a discrete form. Notable examples include choice data where a user selects an item from a list, binary response data where users vote either yes or no on an item, and ranking data where users provide a complete ordering of items based on preference. The development of efficient, robust, and accurate algorithms tailored to handle discrete data has become a focal point of interest across various applications, including recommendation systems, the social sciences, and psychometrics, among others.The present thesis contributes to this dynamic and evolving field. We focus on a class of efficient and powerful statistical algorithms known as spectral algorithms. We introduce novel, efficient and provably accurate spectral algorithms, and analyse the theoretical performance guarantees of classical spectral algorithms when applied to discrete data.For binary and ordered response data, we design novel spectral algorithms that are not only provably accurate but, under reasonable assumptions, also achieve the optimal sample complexity. This is particularly significant for the Rasch model, a fundamental model in psychometrics. Beyond binary response data, we introduce a generalized spectral algorithm designed to yield precise estimates under the Partial Credits model, which extends the Rasch model to encompass discrete ordered responses and ratings data. Our proposed spectral algorithms outperform other popular algorithms in terms of both accuracy and efficiency.In the domain of ranking data, we present novel spectral algorithms that address two well known problems in computer science. Firstly, we tackle the challenge of inference under a mixture of Plackett-Luce models by introducing a novel two-step algorithm. We propose an initialization algorithm based on spectral clustering, which offers provable guarantees. Furthermore, by recognizing the connection between the M-step of the EM algorithm and Markov chain analysis, we introduce a novel EM algorithm that surpasses the accuracy and time efficiency of previously proposed algorithms in the literature. Secondly, we delve into the permutation synchronization problem, which holds a broad range of applications in computer vision. We address a subtle yet critical limitation of previously proposed spectral algorithms, thereby introducing an innovative spectral algorithm designed specifically for this problem. The resulting algorithm enjoys information-theoretic optimal guarantee and performs significantly better than the previous approaches.
■590 ▼aSchool code: 0175.
■650 4▼aComputer science
■650 4▼aStatistics
■650 4▼aInformation science
■653 ▼aDiscrete data
■653 ▼aItem response theory
■653 ▼aPermutation synchronization
■653 ▼aRanking
■653 ▼aSpectral method
■690 ▼a0984
■690 ▼a0723
■690 ▼a0463
■71020▼aUniversity of Pennsylvania▼bComputer and Information Science.
■7730 ▼tDissertations Abstracts International▼g85-12A.
■790 ▼a0175
■791 ▼aPh.D.
■792 ▼a2024
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17160625▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
