생성 AI가 컴퓨터 과학의 가장 큰 미해결 문제를 해결할 수 있을까요?

질문 - P=NP인가요? -- 거대한 이론적 도전이다. 과학자들은 답을 찾기 위해 GPT-4에 아이디어를 숟가락으로 먹이는 접근 방식을 취했습니다.

컴퓨터 과학자들은 솔루션을 계산하는 데 필요한 시간이 가장 어려운 문제에 도달할 수 없는지 여부를 고려합니다. P=NP인가? 이제 GPT-4 언어 모델을 사용하는 다중 프롬프트 세션으로 처리됩니다. 작업의 가장 큰 통찰력은 토론을 유지하기 위해 과거 채팅 세션을 정리하는 방법일 수 있습니다.

컴퓨터 과학자들이 칵테일 파티에 놀 때 무엇보다도 컴퓨터 과학에서 해결되지 않은 가장 중요한 문제인 P=NP인가요라는 질문에 관해 이야기를 나누는 경향이 있습니다.

거의 50년 전에 공식화된 P와 NP가 같은가라는 질문은 컴퓨터로 궁극적으로 무엇을 달성할 수 있는지에 대한 깊은 숙고입니다. 암호화 및 양자 컴퓨팅과 같은 분야에 영향을 미치는 이 질문은 수십 년간의 집중적인 연구에도 불구하고 설득력 있는 답변을 얻지 못했습니다. 이제 이러한 노력에는 생성 AI의 도움이 포함되었습니다.

'과학을 위한 대규모 언어 모델: P 대 NP에 대한 연구'라는 제목의 논문에서 수석 저자인 Qingxiu Dong과 동료들은 소크라테스 방법(Socratetic Method)이라고 부르는 방식을 사용하여 OpenAI의 GPT-4 대규모 언어 모델을 프로그래밍합니다. GPT와의 프롬프트를 통해 몇 차례 채팅이 이루어집니다. -4. (이 논문은 Microsoft, Peking University, 베이징 Beihang University, Beijing Technology and Business University의 과학자들이 이번 달 arXiv 사전 인쇄 서버에 게시했습니다.)

팀의 방법은 이전 논문의 주장을 취하여 이를 GPT-4에 숟가락으로 제공하여 유용한 응답을 유도하는 것입니다.

Dong과 팀은 GPT-4가 P가 실제로 NP와 동일하지 않다는 결론을 내리는 주장을 보여준다는 점을 관찰했습니다. 그리고 그들은 이 작업이 대규모 언어 모델이 방대한 양의 텍스트를 뱉어내는 것 이상의 일을 할 수 있다는 것을 보여주고 있으며, "과학적 발견"으로 이어질 수 있는 "새로운 통찰력"을 발견할 수도 있다고 주장하며, 이를 "과학을 위한 LLM"이라고 명명했습니다.

저자가 무엇을 하고 있는지 파악하려면 P=NP 문제에 대해 조금 알아야 합니다.

1970년대 컴퓨터 과학자인 스티븐 쿡(Stephen Cook)과 레오니드 레빈(Leonid Levin)이 독립적으로 공식화한 P 대 NP 문제(또는 종종 언급되는 "P=NP")는 주어진 문제를 해결하는 것이 얼마나 쉬운지에 대한 질문입니다. 컴퓨터로. 문자 P는 해결 가능한 것으로 확인된 문제를 나타냅니다. 즉, 솔루션을 계산하는 데 걸리는 시간이 멀지 않았음을 의미합니다. 그리고 검증도 쉬운 해결책, 즉 답이 맞는지 확인하는 것입니다.

대조적으로 문자 NP는 P와 마찬가지로 답을 확인하기가 상대적으로 쉽지만 해를 계산하는 쉬운 방법이 없는 문제를 나타냅니다. NP의 예로 스도쿠 게임을 인용하는 것이 일반적입니다. 채워진 스도쿠 게임은 정확성을 쉽게 확인할 수 있지만, 게임 그리드가 커짐에 따라 솔루션을 찾는 작업에 필요한 시간이 기하급수적으로 늘어납니다. (P=NP의 이론적 세부 사항을 자세히 알아보려면 문제에 대한 Cook의 2000년 논문을 참조하세요.)

그렇다면 문제는 P=NP인가? 우리가 해결하기 어렵다고 생각하는 NP 문제가 P 문제처럼 실제로는 쉽게 확인되고 쉽게 해결될 수 있는지 묻습니다.

P가 NP와 같지 않다는 부정적인 대답은 엄청난 컴퓨팅 예산을 들여도 컴퓨터의 능력을 넘어서는 일부 문제, 즉 컴퓨팅의 상한선을 넘어서는 문제를 의미합니다. 일부 암호화를 해독하는 것과 같은 도전은 컴퓨팅의 범위를 넘어서 더욱 어려워 보일 것입니다.

P=NP 문제를 해결하기 위해 Dong과 팀은 지난 몇 년간 대규모 언어 모델을 사용한 "추론" 추세를 바탕으로 구축했습니다. 코지마 다케시(Takeshi Kojima)와 도쿄대학교 및 Google Research 팀의 2022년 작업에서 예시된 것처럼, 시작 부분에 "단계적으로 생각해보자"라는 문구를 추가하는 것만으로 특정 작업에 대한 대규모 언어 모델의 능력을 향상시킬 수 있습니다. 프롬프트와 예시 답변이 함께 제공됩니다. 그들은 그 문구가 언어 모델 부분에서 "생각의 사슬" 단계를 유도하기에 충분하다는 것을 발견했습니다.

이는 Dong과 팀이 Socratic Method를 사용하여 추구하는 것과 동일한 일련의 사고 방식입니다. 97개의 프롬프트 라운드를 통해 저자는 P=NP 수학의 핵심에 들어가는 다양한 요청으로 GPT-4를 동조하고 각 프롬프트 앞에 다음과 같이 GPT-4를 조건으로 하는 주요 진술을 추가합니다. 당신은 현명한 철학자입니다." "당신은 확률론에 능숙한 수학자입니다." 즉, GPT-4가 역할을 수행하도록 하는 게임, 또는 텍스트 생성을 스타일화하는 "페르소나"를 얻는 게임입니다.

매우 이론적인 토론의 채팅 라운드 중 하나의 샘플입니다.

그들의 전략은 먼저 P가 예제와 동일하다고 가정한 다음 예제가 무너지는 방법을 찾아 P가 실제로 NP와 같지 않음을 증명하도록 GPT-4를 유도하는 것입니다. 모순에 의한 증명으로 알려진 접근 방식.

흥미로운 점은 연구 저자 중 두 명인 Ke Xu와 Guangyan Zhou가 이번 달에 전통적인 공식 수학 용어로 P=NP를 직접적으로 추론하는 논문을 별도로 발표했다는 것입니다. 그 논문에서 그들은 P가 NP와 같지 않다고 결론을 내렸습니다.

Dong, Xu, Zhou 및 팀이 수행하는 작업은 즉각적으로 즉각적으로 자신만의 추론 언어를 통해 GPT-4를 이끌어 공식적인 수학 논문을 재구성하는 것과 유사합니다. 실제로 73페이지 분량의 논문 중 67페이지는 97개의 프롬프트 각각과 GPT-4의 완전한 응답을 인쇄한 것입니다. 이는 논쟁을 재구성하기 위한 즉각적인 엔지니어링의 거대한 연습과 같습니다.

Dong과 팀이 GPT-4를 통해 달성한 결과가 실제로 P가 NP와 동일하지 않다는 것을 증명하는지 여부는 Xu와 Zhou의 논문 자체가 매우 새롭기 때문에 말하기 어렵습니다. 논문 인용을 수집하는 Semantic Scholar 사이트에는 Dong과 팀의 자체 논문 외에는 아직 해당 논문에 대한 인용이 없습니다. AI 사이트 HuggingFace에서 관심 있는 다양한 독자들이 GPT-4 논문에 대해 토론한 내용을 확인할 수 있습니다.

그래서 세계는 아직 그들의 주장을 받아들이지 않고 있습니다.

Gen AI를 좋아하는 사람들에게 더욱 중요한 점은 저자들이 프롬프트에서의 대화를 통해 대규모 언어 모델이 단순히 인간의 텍스트 생성을 모방하는 것 이상을 수행할 수 있다는 가능성을 보여준다고 주장한다는 것입니다.

"우리의 조사는 매우 복잡하고 전문가 수준의 문제를 탐구하는 데 있어 인간과 협력할 수 있는 GPT-4의 잠재적인 능력을 강조합니다."라고 그들은 썼습니다. 67페이지에 달하는 프롬프트와 응답 전체에서 GPT-4가 내놓은 내용 중 "통찰력 있는 부분"으로 간주되는 구절을 강조합니다.

이러한 답변이 얼마나 통찰력이 있는지는 아마도 자체 조사가 필요한 주제일 것입니다. 일부 과학자들은 대규모 언어 모델이 인용과 설명을 연결하는 방식이 특히 얕다는 것을 발견했습니다.

그러나 논문 여백에 흥미로운 정보 항목이 나타납니다. 여기서 Dong과 팀은 답변의 품질에 대한 관찰을 통해 GPT-4의 답변에 주석을 달았습니다.

괄호 안의 메모 중 하나에서 저자는 GPT-4의 이전 응답 각각이 최신 프롬프트의 배경으로 통합되었다고 적었습니다. 단, 저자가 가장 많은 응답만 유지하기 위해 응답을 잘라내기로 선택한 경우는 제외입니다. 관련 비트.

"모델이 여러 솔루션을 제공하는 경우 대화 기록에 가장 가치 있는 솔루션만 포함합니다."라고 7페이지 여백에 적었습니다. "이 전략을 통해 GPT-4는 관련 정보에 집중할 수 있어 전반적인 효율성과 효과가 향상됩니다. ."

즉, GPT-4가 그릴 수 있는 모든 이전 라운드인 "컨텍스트 창"에서 과거 기록을 사용하는 방식에 대한 유용한 큐레이션이 있었습니다. Dong과 팀은 논쟁의 흐름을 통해 GPT-4를 안내하기 위해 매우 선택적이고 신속한 엔지니어링에 참여했습니다. 이는 과거 채팅 데이터를 대규모 언어 모델에 대한 새로운 입력으로 사용하려는 현재의 관심인 "검색 증강 생성" 또는 "RAG"의 관행과 관련이 있습니다.

이는 전체 연습에서 가장 중요한 기여 중 하나일 수 있습니다. P=NP 문제를 해결하든 안 하든 프롬프트 엔지니어링의 새로운 개척지는 채팅 세션에 더 깊이 있는 정보를 제공하기 위해 프로그램을 RAG에 더 가깝게 이동할 수 있습니다. . 최근에 채팅 세션 시간을 돌이켜보면 그들은 정신이 없고 종종 주제에서 벗어나 방황하는 경향이 있었습니다.

97라운드를 통해 Dong과 팀은 기계를 제 위치에 유지하는데 성공했으며 이에 대해 할 말이 있습니다.