Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
원문 초록
We study the dynamic correlation clustering problem with $\textit{adaptive}$ edge label flips. In correlation clustering, we are given a $n$-vertex complete graph whose edges are labeled either $(+)$ or $(-)$, and the goal is to minimize the total number of $(+)$ edges between clusters and the number of $(-)$ edges within clusters. We consider the dynamic setting with adversarial robustness, in which the $\textit{adaptive}$ adversary could flip the label of an edge based on the current output of the algorithm. Our main result is a randomized algorithm that always maintains an $O(1)$-approximation to the optimal correlation clustering with $O(\log^{2}{n})$ amortized update time. Prior to our work, no algorithm with $O(1)$-approximation and $\text{polylog}{(n)}$ update time for the adversarially robust setting was known. We further validate our theoretical results with experiments on synthetic and real-world datasets with competitive empirical performances. Our main technical ingredient is an algorithm that maintains $\textit{sparse-dense decomposition}$ with $\text{polylog}{(n)}$ update time, which could be of independent interest.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Solving non-uniqueness in agglomerative hierarchical clustering using multidendrograms
적대적 학습된 신경망의 돌출도 맵 희소성에 대한 규명
Explaining the Saliency Map Sparsity of Adversarially-Trained Neural Networks
심층 신경망이 특정 예측을 수행하는 이유를 이해하는 것은 신경망의 안전한 배포를 위해 매우 중요합니다. 컴퓨터 비전(CV) 분야에서는 예측에 가장 큰 영향을 미치는 이미지 영역을 강조하는 돌출도 맵(saliency map)이 널리 사용되는 설명 방식으로 남아 있습니다. 한 가지 실증적 관찰 결과는 적대적 학습(adversarial training)된 신경망의 그래디언트 돌출도 맵에서 뚜렷한 희소성(sparsity)이 나타난다는 점입니다. 본 논문에서는 2개 층(layer) 렐루(ReLU) 네트워크를 대상으로 이러한 현상에 대한 이론적 설명을 제안합니다. 우리는 특정 손실 함수에서 유효한 것으로 밝혀진 적대적 학습과 가중치 감쇠(weight-decay) 페널티 및 적대적 전변동(total variation) 항이 추가된 경험적 위험 최소화 사이의 기존 동등성 관계를 기반으로 논의를 전개합니다. 데이터 포인트 수와 뉴런 수가 증가하고 정규화 매개변수가 적절한 비율로 0으로 수렴함에 따라, 최소화기(minimizer)가 최소 그래디언트 및 배런 노름(Barron norm)을 갖는 베이즈 분류기(Bayes classifier)로 수렴함을 증명합니다. $\ell_\infty$ 공격을 사용하는 적대적 학습의 경우 그래디언트 노름이 비등방적(anisotropic)이며 축에 정렬된/희소한 그래디언트를 선호하기 때문에 이러한 희소성이 나타납니다. 우리는 자연 학습된 모델과 적대적 학습된 모델의 그래디언트 $\ell_1$-노름 및 임계화된 희소성을 평가하여 이론적 발견을 실험적으로 제시합니다.
건설적·협력적 멀티태스킹을 위한 의미 인식 태스크 클러스터링
Semantic-Aware Task Clustering for Constructive and Cooperative Multi-Tasking
협력적 멀티태스크 의미 통신(cooperative multi-task semantic communication, CMT-SemCom)은 공유 표현을 활용하여 태스크 실행 성능을 향상시킨다. 그러나 [1]에서 보인 바와 같이, 협력적 멀티태스킹은 태스크 간 의미적 관계에 따라 건설적일 수도 있고 파괴적일 수도 있다. 건설적 협력을 보장하기 위해, 우리는 CMT-SemCom을 위한 의미 인식 태스크 클러스터링 방법을 제안한다. 짧은 초기 학습 단계 이후 의미적으로 정렬된 태스크가 한 번 클러스터링되고, 이후 발견된 그룹 내에서만 엔드투엔드(end-to-end, E2E) 공동 학습이 수행되는 순차적 다단계 최적화 문제를 수식화했다. 구체적으로, 이 문제는 두 단계로 분해된다: (i) 계층적 밀도 기반 공간 클러스터링(hierarchical density-based spatial clustering)을 활용한 의미 클러스터링 문제, (ii) 클러스터 내 E2E CMT-SemCom 학습 문제. 시뮬레이션 결과는 제안된 프레임워크가 파괴적 협력과 부정적 전이(negative transfer)를 효과적으로 완화하며, 클러스터링되지 않은 멀티태스킹 및 개별 학습 기준선 대비 정확도 향상을 달성함을 보여준다.
LLM에서의 전문가 격리 및 비활성화를 통한 백도어 억제
Backdoor Containment via Expert Quarantine and Shutdown in LLMs
백도어가 삽입된 대규모 언어 모델(LLM)은 정상 입력에서는 정상적으로 동작하면서 숨겨진 트리거가 주어지면 공격자가 지정한 출력을 생성할 수 있다. 기존 방어 기법은 학습 이전, 학습 중, 학습 이후, 추론 시점의 네 단계에 걸쳐 있으며, 두 가지 기본 전략 중 하나를 공유한다. 하나는 (오염된 데이터를 걸러내거나 최적화 중 그 습득을 차단하여) 백도어 학습을 억제하는 것이고, 다른 하나는 완전히 백도어가 형성된 모델이 만들어진 뒤에 (모델 가중치를 복구하거나 입력을 게이팅하여) 학습한 다음 정화하는 것이다. 우리는 세 번째 전략으로 '학습하되 유도하라(learn, but channel)'를 제안한다. 이는 학습 중 백도어 형성을 허용하되, 이를 배포 시 비활성화할 수 있도록 지정된 격리 구성요소로 유도하는 것이다. 이를 위해 정규화로 유도되는 MoE 유사 환경에서 구축한 계산 효율적 격리 전략인 Quarantined Expert Shutdown(QES)을 제안한다. 구체적으로, 오염된 데이터셋이 주어지면 QES는 Transformer 기반 언어 모델에 라우팅되는 전문가별 LoRA 분기와 경량 라우터를 추가하고, 보조 라우팅 목표를 사용하여 트리거 조건부 동작을 지정된 전문가로 끌어들이면서 다른 곳에서는 정상 능력을 보존한다. 배포 시 완화는 격리된 전문가의 라우팅 가중치를 0으로 만드는 상수 시간의 단일 연산으로 귀결되며, 트리거 검사나 추가 가중치 업데이트가 필요하지 않다. 실험적으로 우리의 방법은 두 가지 과제, 세 가지 공격, 네 가지 모델 계열에 걸친 대부분의 설정에서 공격 성공률(ASR)을 100%에서 0-10%로 낮추며, 하위 과제 성능은 대체로 보존되거나 소폭만 영향을 받는다. 이러한 결과는 '학습하되 유도하라'가 생성형 LLM의 백도어 격리에서 이전에 탐구되지 않은 체제임을 확립한다.
영공간 투영을 통한 LoRA 미세조정 LLM의 백도어 정제
Backdoor Purification for LoRA-Tuned LLMs via Null-Space Projection
대규모 언어 모델(LLM)과 파라미터 효율적 미세조정(PEFT) 방법이 빠르게 채택됨에 따라 백도어 공격의 위험이 더욱 심각해졌다. 기존의 백도어 정화 방법은 일반적으로 트리거에 대한 사전 지식, 깨끗한 참조에 대한 접근, 또는 공격적인 재학습과 같은 강한 가정 중 적어도 하나에 의존하며, 포괄적인 평가가 부족한 경우가 많다. 이러한 제약은 실제 적용 가능성을 크게 제한한다. 이러한 문제를 극복하기 위해, 본 연구는 이러한 가정 없이, 심지어 의심되는 파라미터의 사후 재학습 없이 LoRA로 튜닝된 LLM을 정화하는 방법을 제안한다. 우리의 목표는 (i) 기반 모델의 일반 능력과 (ii) 어댑터를 통해 학습된 새로운 하위 과제 기술을 모두 보존하면서 공격 성공률(ASR)을 크게 낮추는 것이다. 일련의 검토를 통해 텍스트 분류 환경의 단일 레이어에서 생성 과제의 전체 파라미터 LLM에 이르기까지 접근법을 점진적으로 확장한다. 신중한 데이터 선별과 특징 근사를 통해 충실도가 높은 백도어 방향을 추출하고, 각 레이어 또는 헤드에 대해 입력 및 출력 채널 모두에서 직교 영공간(null space)을 구성하여 LoRA 업데이트를 그 위로 사영한다. 실험적으로, 우리의 영공간 사영 방법은 하위 과제 적응 중에도 기반 모델의 정상 성능과 어댑터가 학습한 능력을 보존하면서 ASR을 거의 100%에서 10% 미만으로 낮춘다.
탐지 및 억제: VLA 모델의 적대적 패치에 대한 기제론적 방어
Detect and Suppress: A Mechanistic Defense against Adversarial Patches in VLA Models
적대적 패치(adversarial patch)는 시각적 관측을 조작하여 비전-언어-행동(VLA) 모델을 교란함으로써 로봇 제어 실패를 초래할 수 있습니다. 그러나 이러한 실패의 기저에 어떤 내부 메커니즘이 존재하는지, 표적화된 개입을 통해 이를 어떻게 완화할 수 있는지는 여전히 명확히 이해되지 않았습니다. 본 연구에서는 희소 오토인코더(SAE)를 사용하여 VLA 표현을 기제론적으로 분석하고, 활성화 정도가 적대적 패치의 존재와 강하게 상관되는 특징(feature)을 식별합니다. 이 분석을 바탕으로, 선형 탐침(linear probe)이 공격을 탐지할 때에만 추론(inference) 시점에 식별된 특징을 억제합니다. 이러한 개입은 VLA를 미세조정(fine-tuning)하는 비용 없이도 견고성을 향상합니다. 저자들은 LIBERO-10에서 VLA 적대적 패치 공격에 대해 제안 방식을 평가합니다. 조건부 개입은 간헐적인 공격 상황에서 성공률을 향상하는 반면, 동일한 개입을 지속적으로 적용할 경우 정책(policy) 성능이 크게 저하됩니다. 이러한 결과는 공격 관련 내부 표현이 VLA 적대적 방어를 위한 유용한 표적이 될 수 있음을 보여주며, 정상적인 정책 동작에 대한 방해를 제한하기 위해서는 개입 시점을 제어하는 것이 중요하다는 점을 시사합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.