서브메뉴
검색
On Proofs and Translation
On Proofs and Translation
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260202103604
- ISBN
- 9798288865190
- DDC
- 004
- 저자명
- Paradise, Orr.
- 서명/저자
- On Proofs and Translation
- 발행사항
- [Sl] : University of California, Berkeley, 2025
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2025
- 형태사항
- 222 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 87-01, Section: B.
- 주기사항
- Advisor: Goldwasser, Shafi;Tal, Avishay.
- 학위논문주기
- Thesis (Ph.D.)--University of California, Berkeley, 2025.
- 초록/해제
- 요약This dissertation examines proof systems and translation methods, addressing both theoretical foundations and practical considerations in each domain.The first part, on Proofs, introduces rectangular probabilistically checkable proofs (rectangular PCPs), wherein proofs are thought of as square matrices, and the verifier's randomness can be split into two independent parts, one determining the row of each query and the other determining the column. We construct rectangular PCPs and use them to show that proofs for hard languages are rigid---extending and strengthening recent rigid matrix constructions.We then propose Self-Proving models: learned models that prove the correctness of their output to a verification algorithm via an Interactive Proof. We devise a generic method for learning Self-Proving models, and prove its convergence under certain assumptions. We empirically examine our methods by training a Self-Proving transformer to compute the GCD of two integers, and prove correctness of its output. We also introduce Pseudointelligence, a complexity-theoretic framework of model evaluation cast as an interactive proof between a model and a learned evaluator.The second part, on Translation, explores unsupervised machine translation (UMT) without shared linguistic structure. We develop a theoretical framework for analyzing this setting, and prove sample complexity bounds in stylized yet informative settings. The results show that translation quality improves with language complexity, informing feasibility of animal communication translation. Finally, we present WhAM, a transformer-based model for generating synthetic sperm whale codas. WhAM is trained on real acoustic data and generates audio that approaches the statistical and perceptual properties of whale communication as evaluated by domain experts. Its learned representations also perform well on classification tasks, contributing to our understanding of non-human communication systems.
- 일반주제명
- Computer science
- 키워드
- Machine learning
- 키워드
- Sperm whales
- 기타저자
- University of California, Berkeley Electrical Engineering & Computer Sciences
- 기본자료저록
- Dissertations Abstracts International. 87-01B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260126s2025 us c eng d■001000017357817
■00520260202103604
■006m o d
■007cr#unu||||||||
■020 ▼a9798288865190
■035 ▼a(MiAaPQ)AAI32042662
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aParadise, Orr.
■24510▼aOn Proofs and Translation
■260 ▼a[Sl]▼bUniversity of California, Berkeley▼c2025
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a222 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 87-01, Section: B.
■500 ▼aAdvisor: Goldwasser, Shafi;Tal, Avishay.
■5021 ▼aThesis (Ph.D.)--University of California, Berkeley, 2025.
■520 ▼aThis dissertation examines proof systems and translation methods, addressing both theoretical foundations and practical considerations in each domain.The first part, on Proofs, introduces rectangular probabilistically checkable proofs (rectangular PCPs), wherein proofs are thought of as square matrices, and the verifier's randomness can be split into two independent parts, one determining the row of each query and the other determining the column. We construct rectangular PCPs and use them to show that proofs for hard languages are rigid---extending and strengthening recent rigid matrix constructions.We then propose Self-Proving models: learned models that prove the correctness of their output to a verification algorithm via an Interactive Proof. We devise a generic method for learning Self-Proving models, and prove its convergence under certain assumptions. We empirically examine our methods by training a Self-Proving transformer to compute the GCD of two integers, and prove correctness of its output. We also introduce Pseudointelligence, a complexity-theoretic framework of model evaluation cast as an interactive proof between a model and a learned evaluator.The second part, on Translation, explores unsupervised machine translation (UMT) without shared linguistic structure. We develop a theoretical framework for analyzing this setting, and prove sample complexity bounds in stylized yet informative settings. The results show that translation quality improves with language complexity, informing feasibility of animal communication translation. Finally, we present WhAM, a transformer-based model for generating synthetic sperm whale codas. WhAM is trained on real acoustic data and generates audio that approaches the statistical and perceptual properties of whale communication as evaluated by domain experts. Its learned representations also perform well on classification tasks, contributing to our understanding of non-human communication systems.
■590 ▼aSchool code: 0028.
■650 4▼aComputer science
■653 ▼aComputational complexity
■653 ▼aMachine learning
■653 ▼aProbabilistic proof systems
■653 ▼aSperm whales
■690 ▼a0984
■690 ▼a0800
■71020▼aUniversity of California, Berkeley▼bElectrical Engineering & Computer Sciences.
■7730 ▼tDissertations Abstracts International▼g87-01B.
■790 ▼a0028
■791 ▼aPh.D.
■792 ▼a2025
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17357817▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
